Journal
QUANTUM INFORMATION & COMPUTATION
Volume 19, Issue 15-16, Pages 1261-1278Publisher
RINTON PRESS, INC
Keywords
quantum learning theory; PAC model; Fourier analysis
Categories
Funding
- National Science Foundation [NSF PHY-1748958]
- Heising-Simons Foundation
- EPSRC DTP Scholarship
- QinetiQ Ltd.
- Simons Foundation through It from Qubit: Simons Collaboration on Quantum Fields, Gravity, and Information
- Royal Society
- EPSRC
- National Natural Science Foundation of China
- US DOD [ARO-MURI W911NF-17-1-0304]
- UK MOD [ARO-MURI W911NF-17-1-0304]
- UK EPSRC [ARO-MURI W911NF-17-1-0304]
Ask authors/readers for more resources
We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The current best classical algorithm runs in superpolynomial time. Our result extends the work by Bshouty and Jackson (1998) that proved that DNF formulae are efficiently learnable under the uniform distribution using a quantum example oracle. Our proof is based on a new quantum algorithm that efficiently samples the coefficients of a mu-biased Fourier transform.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
