Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester.
Cedric Yen-Yu LinHan-Hsuan LinPublished in: Computational Complexity Conference (2015)
Keyphrases
- upper bound
- query complexity
- concept class
- vc dimension
- lower bound
- upper and lower bounds
- dnf formulas
- data complexity
- membership queries
- concept classes
- lower and upper bounds
- worst case
- exact learning
- sample size
- sample complexity
- generalization error
- positive and negative
- expressive power
- pac learning
- efficient learning
- statistical queries
- pac model
- np hard