期刊
QUANTUM INFORMATION & COMPUTATION
卷 19, 期 15-16, 页码 1261-1278出版社
RINTON PRESS, INC
关键词
quantum learning theory; PAC model; Fourier analysis
类别
资金
- 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]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据