Learning DNFs under product distributions via μ-biased quantum Fourier sampling
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Predicting quantum channels over general product distributions
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$-qubit channel $E$ and an observable $O$, we aim to learn the mapping \begin{equation*} \rho \mapsto \…
Quantum Learning Boolean Linear Functions w.r.t. Product Distributions
The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein-Vazirani algorithm. A similar strategy can be applied in the …
Improving application performance with biased distributions of quantum states
We consider the properties of a specific distribution of mixed quantum states of arbitrary dimension that can be biased towards a specific mean purity. In particular, we analyze mixtures of Haar-random pure states with D…
Quantum State TomographyOn the Optimality of Trees Generated by ID3
Since its inception in the 1980s, ID3 has become one of the most successful and widely used algorithms for learning decision trees. However, its theoretical properties remain poorly understood. In this work, we introduce…
On Quantum Circuits for Discrete Graphical Models
Graphical models are useful tools for describing structured high-dimensional probability distributions. Development of efficient algorithms for generating unbiased and independent samples from graphical models remains an…