Learning DNFs under product distributions via mu--biased quantum Fourier sampling
| Autor: | Varun Kanade, Andrea Rocchetto, Simone Severini |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Quantum Physics
Computer Science - Machine Learning Nuclear and High Energy Physics TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES TheoryofComputation_GENERAL General Physics and Astronomy Sampling (statistics) Statistical and Nonlinear Physics Computer Science::Computational Complexity 01 natural sciences 010305 fluids & plasmas Theoretical Computer Science symbols.namesake Fourier transform Computational Theory and Mathematics Product (mathematics) 0103 physical sciences symbols Statistical physics 010306 general physics Quantum Computer Science::Databases Mathematical Physics Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | Quantum Information and Computation. 19:1261-1278 |
| ISSN: | 1533-7146 |
| DOI: | 10.26421/qic19.15-16-1 |
| Popis: | We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The best classical algorithm (without access to membership queries) 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. Comment: 17 pages; v3 based on journal version; minor corrections and clarifications |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|