Abstract
We initiate the study of quantum agnostic learning of phase states with respect to a function class C⊆ {c:{0,1}ⁿ→ {0,1}}: given copies of an unknown n-qubit state |ψ which has fidelity opt with a phase state |φ_c=1/√2ⁿΣ_x∈ {0,1}ⁿ(-1)^c(x)|x for some c∈ C, output |φ which has fidelity | φ | ψ |² ≥ opt-ε. To this end, we give agnostic learning protocols for the following classes: (i) Size-t decision trees which runs in time poly(n,t,1/ε). This also implies k-juntas can be agnostically learned in time poly(n,2^k,1/ε). (ii) s-term DNF formulas in time poly(n,(s/ε)^log log (s/ε) · log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state |φ such that | φ|ψ|²≥ opt/poly(n), into a strong learner which outputs a superposition of parity states |φ' such that | φ'|ψ|²≥ opt - ε. Using quantum agnostic boosting, we obtain a n^O(log(n/ε) · log log n)-time algorithm for ε-learning poly(n)-sized depth-3 circuits (consisting of AND, OR, NOT gates) in the uniform PAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the PAC model and our work answers this given quantum examples.