An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation

Harumichi Nishimura Tomoyuki Yamakami

Published 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