Efficiently learning depth-3 circuits via quantum agnostic boosting

• URL: http://arxiv.org/abs/2509.14461v2
• Date: Wed, 24 Sep 2025 17:54:07 GMT
• Title: Efficiently learning depth-3 circuits via quantum agnostic boosting
• Authors: Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael de Oliveira,
• Abstract summary: We study the study of quantum agnostic learning of phase states with respect to a function class $mathsfC$.<n>Our main technical contribution is a quantum boosting protocol which converts a weak learner.<n>Using quantum agnostic boosting, we obtain a $nO(log log n cdot log(1/varepsilon))$-time algorithm for learning $textsfpoly(n)$-sized depth-$3$ circuits.
• Score: 41.9957758385623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|\phi'\rangle$ such that $|\langle \phi'|\psi\rangle|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\log \log n \cdot \log(1/\varepsilon))}$-time algorithm for 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, which is near-polynomial time for constant $\varepsilon$. 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.

Related papers

• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
  We establish deterministic hardness of approximation results for the Shortest Vector Problem in $ell_p$ norm ($mathsfSVP_p$) and for Unique-SVP ($mathsfuSVP_p$)<n>For every $p > 2$, we prove constant-ratio hardness: no-time algorithm approximates $mathsfSVP_p$ or $mathsfuSVP_p$ within a ratio of $sqrt2 - o(1)$.
  arXiv  Detail & Related papers  (2025-10-19T20:17:26Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties [3.3728077347699497]
  We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties.<n>Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth.
  arXiv  Detail & Related papers  (2025-09-11T14:57:53Z)
• Learning junta distributions, quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counterparts (quantum junta states) and $mathsfQAC0$ circuits.<n>We show that $n$-qubit $mathsfQAC0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2O(log(s22a)d)log (n)$ copies of the Choi state.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• Polynomial-time tolerant testing stabilizer states [4.65004369765875]
  An algorithm is given copies of an unknown $n$-qubit quantum state $|psirangle promised $(i)$ $|psirangle$. We show that for every $varepsilon_1>0$ and $varepsilonleq varepsilon_C$, there is a $textsfpoly that decides which is the case. Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for
  arXiv  Detail & Related papers  (2024-08-12T16:56:33Z)
• Learning low-degree quantum objects [5.2373060530454625]
  We show how to learn low-degree quantum objects up to $varepsilon$-error in $ell$-distance. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely boundedpolynomials.
  arXiv  Detail & Related papers  (2024-05-17T17:36:44Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  We show that for any continuous function $f(x):[-1,1]rightarrow [-1,1]$, the quantum query complexity of computing $brai f(A) ketjpm varepsilon/4$ is lower bounded by $Omega(widetildedeg_varepsilon(f))$.
  arXiv  Detail & Related papers  (2023-11-13T00:45:41Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.