Quantum DNF Learnability Revisited

Details Quantum DNF Learnability Revisited Quantum DNF Learnability Revisited

2002-02-12

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

Proc. of Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, p595-604

Physics

Quantum Physics

Scientific paper

We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/\epsilon + s^{2}/\epsilon^{2})$, where $s$ is the size of DNF formula and $\epsilon$ is the PAC error accuracy. If $s$ and $1/\epsilon$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/\epsilon^{2})$. We also show a lower bound of $\Omega(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.

Affiliated with

Also associated with

No associations

Rating

Quantum DNF Learnability Revisited 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 Quantum DNF Learnability Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum DNF Learnability Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-621203