Quantum DNF Learnability Revisited.
Jeffrey C. JacksonChristino TamonTomoyuki YamakamiPublished in: COCOON (2002)
Keyphrases
- boolean functions
- uniform distribution
- membership queries
- agnostic learning
- dnf formulas
- pac learning
- pac learnable
- monotone dnf formulas
- learning algorithm
- attribute noise
- dnf formulae
- monotone dnf
- equivalence queries
- exact learning
- quantum computing
- quantum computation
- term dnf
- disjunctive normal form
- target concept
- class noise
- quantum inspired
- decision lists
- efficient learning
- pac learnability
- probability ranking principle
- efficiently learnable
- polynomial size
- quantum mechanics
- noise tolerant
- finite automata
- pattern languages
- lower bound