A Quantum Computational Learning Algorithm
| dc.creator | Ventura, Dan | |
| dc.creator | Martinez, Tony | |
| dc.date | 1998-07-18 | |
| dc.date.accessioned | 2026-07-07T06:15:19Z | |
| dc.date.available | 2026-07-07T06:15:19Z | |
| dc.description | An interesting classical result due to Jackson allows polynomial-time learning of the function class DNF using membership queries. Since in most practical learning situations access to a membership oracle is unrealistic, this paper explores the possibility that quantum computation might allow a learning algorithm for DNF that relies only on example queries. A natural extension of Fourier-based learning into the quantum domain is presented. The algorithm requires only an example oracle, and it runs in O(sqrt(2^n)) time, a result that appears to be classically impossible. The algorithm is unique among quantum algorithms in that it does not assume a priori knowledge of a function and does not operate on a superposition that includes all possible states. | |
| dc.description | This is a reworked and improved version of a paper originally entitled "Quantum Harmonic Sieve: Learning DNF Using a Classical Example Oracle" | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9807052 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9807052 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93758 | |
| dc.subject | Quantum Physics | |
| dc.title | A Quantum Computational Learning Algorithm | |
| dc.type | text |