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 $\mathsf{C}\subseteq \{c:\{0,1{\}}^n\to \{0,1\}\}$: given copies of an unknown $n$-qubit state $\mathrm{\mid }\psi ⟩$ which has fidelity $\mathsf{\text{opt}}$ with a phase state $\mathrm{\mid }{\phi }_c⟩=\frac{1}{\sqrt{2^n}}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{c(x)}\mathrm{\mid }x⟩$ for some $c\in \mathsf{C}$, output $\mathrm{\mid }\phi ⟩$ which has fidelity $\mathrm{\mid }⟨\phi \mathrm{\mid }\psi ⟩{\mathrm{\mid }}^2\ge \mathsf{\text{opt}}-\epsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\mathsf{\text{poly}}(n,t,1\mathrm{/}\epsilon )$. This also implies $k$-juntas can be agnostically learned in time $\mathsf{\text{poly}}(n,2^k,1\mathrm{/}\epsilon )$. (ii) $s$-term DNF formulas in time $\mathsf{\text{poly}}(n,(s\mathrm{/}\epsilon {)}^{\log \log (s\mathrm{/}\epsilon )\cdot \log (1\mathrm{/}\epsilon )})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $\mathrm{\mid }\phi ⟩$ such that $\mathrm{\mid }⟨\phi \mathrm{\mid }\psi ⟩{\mathrm{\mid }}^2\ge \mathsf{\text{opt}}\mathrm{/}\mathsf{\text{poly}}(n)$, into a strong learner which outputs a superposition of parity states $\mathrm{\mid }{\phi }^{\mathrm{\prime }}⟩$ such that $\mathrm{\mid }⟨{\phi }^{\mathrm{\prime }}\mathrm{\mid }\psi ⟩{\mathrm{\mid }}^2\ge \mathsf{\text{opt}}-\epsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\log (n\mathrm{/}\epsilon )\cdot \log \log n)}$-time algorithm for $\epsilon$-learning $\mathsf{\text{poly}}(n)$-sized depth-$3$ circuits (consisting of $\mathsf{\text{AND}}$, $\mathsf{\text{OR}}$, $\mathsf{\text{NOT}}$ gates) in the uniform $\mathsf{\text{PAC}}$ model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\mathsf{\text{PAC}}$ model and our work answers this given quantum examples.