Learning depth-3 circuits via quantum agnostic boosting

We initiate the study of quantum agnostic learning of phase states with respect to a function class mathsfCsubseteq c:0,1nrightarrow 0,1: given copies of an unknown n-qubit state |psirangle which has fidelity textsfopt with a phase state |φcrangle=frac1√2nsum_x∈ 0,1n(-1)c(x)|xrangle for some c∈ mathsfC, output |φrangle which has fidelity |langle φ | psi rangle|2 ≥ textsfopt-varepsilon. To this end, we give agnostic learning protocols for the following classes: (i) Size-t decision trees which runs in time textsfpoly(n,t,1/varepsilon). This also implies k-juntas can be agnostically learned in time textsfpoly(n,2k,1/varepsilon). (ii) s-term DNF formulas in time textsfpoly(n,(s/varepsilon)log log (s/varepsilon) · log(1/varepsilon)). Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state |φrangle such that |langle φ|psirangle|2≥ textsfopt/textsfpoly(n), into a strong learner which outputs a superposition of parity states |φ'rangle such that |langle φ'|psirangle|2≥ textsfopt - varepsilon. Using quantum agnostic boosting, we obtain a nO(log(n/varepsilon) · log log n)-time algorithm for varepsilon-learning textsfpoly(n)-sized depth-3 circuits (consisting of textsfAND, textsfOR, textsfNOT gates) in the uniform textsfPAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the textsfPAC model and our work answers this given quantum examples.