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.
We initiate the study of quantum agnostic learning of phase states with respect to a function class C⊆{c:{0,1}n→{0,1}}: given copies of an unknown n-qubit state ∣ψ⟩ which has fidelity opt with a phase state ∣ϕc⟩=2n1∑x∈{0,1}n(−1)c(x)∣x⟩ for some c∈C, output ∣ϕ⟩ which has fidelity ∣⟨ϕ∣ψ⟩∣2≥opt−ε. To this end, we give agnostic learning protocols for the following classes: (i) Size-t decision trees which runs in time poly(n,t,1/ε). This also implies k-juntas can be agnostically learned in time poly(n,2k,1/ε). (ii) s-term DNF formulas in time poly(n,(s/ε)loglog(s/ε)⋅log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state ∣ϕ⟩ such that ∣⟨ϕ∣ψ⟩∣2≥opt/poly(n), into a strong learner which outputs a superposition of parity states ∣ϕ′⟩ such that ∣⟨ϕ′∣ψ⟩∣2≥opt−ε. Using quantum agnostic boosting, we obtain a nO(log(n/ε)⋅loglogn)-time algorithm for ε-learning poly(n)-sized depth-3 circuits (consisting of AND, OR, NOT gates) in the uniform PAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the PAC model and our work answers this given quantum examples.
We study the task of agnostic tomography: given copies of an unknown n-qubit state ρ which has fidelity τ with some state in a given class C, find a state which has fidelity ≥τ−ε with ρ. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly(n,1/ε)⋅(1/τ)O(log(1/τ)), answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Θ(n)) or required τ>cos2(π/8). States with stabilizer dimension n−t: We give a protocol that runs in time n3⋅(2t/τ)O(log(1/ε)), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where τ=1 [33, 40, 49, 66]. Discrete product states: If C=K⊗n for some μ-separated discrete set K of single-qubit states, we give a protocol that runs in time (n/μ)O((1+log(1/τ))/μ)/ε2. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time (n2/ε2)⋅(1/τ)O(log(1/τ)). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error ε in n3quasipoly(1/ε) time.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown n-qudit pure state ∣ψ⟩ that has fidelity τ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension d is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
Suppose we have a weak learning algorithm A for a Boolean-valued problem: A produces hypotheses whose bias γ is small, only slightly better than random guessing (this could, for instance, be due to implementing A on a noisy device), can we boost the performance of A so that A's output is correct on 2/3 of the inputs? Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the Gödel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a γ-weak learner for a Boolean concept class C that takes time R(C), then the time complexity of AdaBoost scales as VC(C)⋅poly(R(C),1/γ), where VC(C) is the VC-dimension of C. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a γ-weak quantum learner for a Boolean concept class C that takes time Q(C), we introduce a quantum boosting algorithm whose complexity scales as VC(C)⋅poly(Q(C),1/γ); thereby achieving a quadratic quantum improvement over classical AdaBoost in terms of VC(C).
We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state ρ, our algorithms return a state ∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩ is within ε of the optimum over the model class, without assuming that ρ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and 1/ε, together with polynomial runtime in the system size for fixed local dimension, bond dimension, and accuracy. The same framework yields proper agnostic learning of tree tensor networks on bounded-degree trees, with both copy complexity and runtime polynomial in the system size when the remaining parameters are fixed.
Characterizing a quantum system by learning its state or evolution is a fundamental problem in quantum physics and learning theory with a myriad of applications. Recently, as a new approach to this problem, the task of agnostic state tomography was defined, in which one aims to approximate an arbitrary quantum state by a simpler one in a given class. Generalizing this notion to quantum processes, we initiate the study of agnostic process tomography: given query access to an unknown quantum channel Φ and a known concept class C of channels, output a quantum channel that approximates Φ as well as any channel in the concept class C , up to some error. In this work, we propose several natural applications for this new task in quantum machine learning, quantum metrology, classical simulation, and error mitigation. In addition, we give efficient agnostic process tomography algorithms for a wide variety of concept classes, including Pauli strings, Pauli channels, quantum junta channels, low-degree channels, and a class of channels produced by Q A C 0 circuits. The main technical tool we use is Pauli spectrum analysis of operators and superoperators. We also prove that, using ancilla qubits, any agnostic state tomography algorithm can be extended to one solving agnostic process tomography for a compatible concept class of unitaries, immediately giving us efficient agnostic learning algorithms for Clifford circuits, Clifford circuits with few T gates, and circuits consisting of a tensor product of single-qubit gates. Together, our results provide insight into the conditions and new algorithms necessary to extend the learnability of a concept class from the standard tomographic setting to the agnostic one.
In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp., AC0), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., AND,OR,NOT gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (RLWE) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for TC0; and if there exists no 2O(d1/η)-time quantum algorithm to solve RLWE with dimension d=O(polylogn) (for every constant η>2), then there exists no O(nlogνn)-time quantum learning algorithm for poly(n)-sized AC0 circuits (for a constant ν>0), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning TC20 in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the LWE problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class TC20, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.