A Quantum Computational Learning Algorithm

Details A Quantum Computational Learning Algorithm A Quantum Computational Learning Algorithm

1998-07-18

arxiv.org/abs/quant-ph/9807052v1

Physics

Quantum Physics

This is a reworked and improved version of a paper originally entitled "Quantum Harmonic Sieve: Learning DNF Using a Classical

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Quantum Computational Learning Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Quantum Computational Learning Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quantum Computational Learning Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649001