Efficiently learning depth-3 circuits via quantum agnostic boosting

We initiate the study of \emph{quantum agnostic learning} of phase states with respect to a function class $\Cc\subseteq \{c:\01^n\rightarrow \01\}$: given copies of an unknown $n$-qubit state $\ket{\psi}$ which has fidelity $\opt$ with a phase state $\ket{\phi_c}=\frac{1}{\sqrt{2^n}}\sum_{x\in \01^n}(-1)^{c(x)}\ket{x}$ for some $c\in \calC$, output $\ket{\phi}$ which has fidelity $|\langle \phi | \psi \rangle|^2 \geq \opt-\varepsilon$. To this end, we give agnostic learning protocols for the following classes:

\begin{enumerate} \item Size-$t$ decision trees which runs in time $\poly(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\poly(n,2^k,1/\varepsilon)$. \item $s$-term DNF formulas in near-polynomial time $\poly(n,(s/\varepsilon)^{\log \log s/\varepsilon})$. \end{enumerate}

Our main technical contribution is a \emph{quantum agnostic boosting} protocol which converts a weak'' agnostic learner (which outputs a \emph{parity state} $\ket{\phi}$ such that $|\langle \phi|\psi\rangle|^2\geq \opt/\poly(n)$) into a strong'' learner (which outputs a sum of parity states $\ket{\phi'}$ such that $|\langle \phi'|\psi\rangle|^2\geq \opt - \varepsilon$).

Using quantum agnostic boosting, we obtain the first ``near'' polynomial-time $n^{O(\log \log n)}$ algorithm for learning $\poly(n)$-sized depth-$3$ circuits (consisting of $\AND$, $\OR$, $\NOT$ gates) in the uniform quantum $\PAC$ model using quantum examples. Classically, the analogue of efficient learning depth-$3$ circuits (and even depth-$2$ circuits) in the uniform PAC model has been a longstanding open question in computational learning theory. Our work nearly settles this question, when the learner is given quantum examples.