Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester.
Cedric Yen-Yu LinHan-Hsuan LinPublished in: Theory Comput. (2016)
Keyphrases
- query complexity
- upper bound
- concept class
- vc dimension
- lower bound
- concept classes
- membership queries
- data complexity
- upper and lower bounds
- worst case
- exact learning
- dnf formulas
- efficiently computable
- lower and upper bounds
- generalization error
- sample size
- databases
- sample complexity
- pac learning
- query processing
- database
- learning theory
- learning tasks
- statistical queries
- special case