{"ID":2870074,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.14461","arxiv_id":"2509.14461","title":"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\\rightarrow \\{0,1\\}\\}$: given copies of an unknown $n$-qubit state $|ψ\\rangle$ which has fidelity $\\textsf{opt}$ with a phase state $|φ_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 $|φ\\rangle$ which has fidelity $|\\langle φ| ψ\\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 $|φ\\rangle$ such that $|\\langle φ|ψ\\rangle|^2\\geq \\textsf{opt}/\\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|φ'\\rangle$ such that $|\\langle φ'|ψ\\rangle|^2\\geq \\textsf{opt} - \\varepsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\\log(n/\\varepsilon) \\cdot \\log \\log n)}$-time algorithm for $\\varepsilon$-learning $\\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\\textsf{AND}$, $\\textsf{OR}$, $\\textsf{NOT}$ gates) in the uniform $\\textsf{PAC}$ model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\\textsf{PAC}$ model and our work answers this given quantum examples.","short_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 $|ψ\\rangle$ which has fidelity $\\textsf{opt}$ with a phase state $|φ_c\\rangle=\\frac{1}{\\sqrt{2^n}}\\sum_{x\\in \\{0,1\\}^n}...","url_abs":"https://arxiv.org/abs/2509.14461","url_pdf":"https://arxiv.org/pdf/2509.14461v3","authors":"[\"Srinivasan Arunachalam\",\"Arkopal Dutt\",\"Alexandru Gheorghiu\",\"Michael de Oliveira\"]","published":"2025-09-17T22:28:29Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.LG\"]","methods":"[]","has_code":false}