# Learning depth-3 circuits via quantum agnostic boosting

arXiv: https://arxiv.org/abs/2509.14461 · HTML: https://mlsanity.com/paper/2509.14461/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 50 references that are in the map.
- First posted on arXiv 17 Sep 2025.

## Builds on (most cited first, 4 of 4)

- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Interactive proofs for verifying (quantum) learning and testing](https://mlsanity.com/paper/2410.23969/) (2024)

## Abstract (arXiv)

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.