Learning depth-3 circuits via quantum agnostic boosting

Abstract

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

53 pages; Typos fixed for depth-3 circuits result