![[2509.14461] Learning depth-3 circuits via quantum agnostic boosting](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2509.14461] Learning depth-3 circuits via quantum agnostic boosting
Summary
This article introduces quantum agnostic learning protocols for depth-3 circuits, showcasing a quantum agnostic boosting method that enhances learning efficiency in quantum settings.
Why It Matters
The research addresses a significant challenge in computational learning theory by providing a quantum approach to learning depth-3 circuits, which has implications for both quantum computing and machine learning. This work could pave the way for more efficient algorithms in quantum machine learning, an area of growing interest and importance.
Key Takeaways
- Introduces quantum agnostic learning protocols for phase states.
- Demonstrates a quantum agnostic boosting method to enhance learning.
- Achieves efficient learning of depth-3 circuits in the PAC model.
- Provides a polynomial-time algorithm for learning decision trees and DNF formulas.
- Addresses an open question in classical learning complexity with quantum examples.
Quantum Physics arXiv:2509.14461 (quant-ph) [Submitted on 17 Sep 2025 (v1), last revised 17 Feb 2026 (this version, v3)] Title:Learning depth-3 circuits via quantum agnostic boosting Authors:Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael de Oliveira View a PDF of the paper titled Learning depth-3 circuits via quantum agnostic boosting, by Srinivasan Arunachalam and 3 other authors View PDF HTML (experimental) 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\rightarrow \{0,1\}\}$: given copies of an unknown $n$-qubit state $|\psi\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, output $|\phi\rangle$ which has fidelity $|\langle \phi | \psi \rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. (ii) $s$-term DNF formulas in time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $|\phi\rangle$ such that $|\langle \phi|\psi\...
