The quantum query complexity of the hidden subgroup problem is polynomial.

Mark Ettinger Peter Høyer Emanuel Knill

Published in: Inf. Process. Lett. (2004)

Keyphrases

query complexity
membership queries
dnf formulas
equivalence queries
data complexity
exact learning
expressive power
concept class
vc dimension
efficient learning
resource consumption
conjunctive queries
uniform distribution
sample complexity
database
query answering
incomplete information
training data