An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation
Harumichi NishimuraTomoyuki YamakamiPublished in: CoRR (2003)
Keyphrases
- query complexity
- quantum computation
- lower bound
- concept class
- vc dimension
- upper bound
- membership queries
- concept classes
- learning theory
- dnf formulas
- data complexity
- equivalence queries
- exact learning
- concept learning
- np hard
- sample size
- worst case
- lower and upper bounds
- efficient learning
- sample complexity
- uniform distribution
- optimal solution
- target concept
- statistical queries
- pac learning
- databases
- image compression
- machine learning