We consider the task of learning a structured stabilizer decomposition of an arbitrary n-qubit quantum state |ψ⟩: for every ε > 0, output a succinctly describable state |φ⟩ with stabilizer-rank poly(1/ε) such that |ψ⟩=|φ⟩+|φ′⟩ where |φ′⟩ has stabilizer fidelity at most ε. We firstly show the existence of such decompositions using the inverse theorem for the Gowers-3 norm of quantum states that was recently established by our prior work [AD, STOC’25].
We consider the task of learning a structured stabilizer decomposition of an arbitrary n-qubit quantum state |ψ⟩: for every ε > 0, output a succinctly describable state |φ⟩ with stabilizer-rank poly(1/ε) such that |ψ⟩=|φ⟩+|φ′⟩ where |φ′⟩ has stabilizer fidelity at most ε. We firstly show the existence of such decompositions using the inverse theorem for the Gowers-3 norm of quantum states that was recently established by our prior work [AD, STOC’25].
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.
We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state ∣ψ⟩ promised (i)∣ψ⟩ is ε1-close to a stabilizer state in fidelity or (ii)∣ψ⟩ is ε2-far from all stabilizer states, decide which is the case. We show that for every ε1>0 and ε2≤ε1C, there is a poly(1/ε1)-sample and n⋅poly(1/ε1)-time algorithm that decides which is the case (where C>1 is a universal constant). 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 structured subsets of Paulis using results in additive combinatorics.
In this note, we consider tomography of n-qubit quantum states ∣ψ⟩ that are promised to have stabilizer rank k i.e., admit a stabilizer decomposition of ∣ψ⟩=∑i=1kci∣φi⟩ where each ∣φi⟩ is a stabilizer state. We give a tomography protocol for such states up to trace distance ε>0 running in poly(n,2k,1/ε) time and thus can handle k=O(logn) efficiently. This follows from first showing that the stabilizer extent ξ(∣ψ⟩), which is the minimal ℓ1 norm over the coefficients {ci} of any stabilizer decomposition of ∣ψ⟩, can be bounded as ξ(∣ψ⟩)≤2O(k) and improving upon the previous best bound of kO(k). The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .
We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(klog(k+1)), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2−O(klog(k+1)), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/logn) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states.
As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/logn) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((logn)2/loglogn), respectively, a logn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2O(klog(k+1)) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
We show an improved inverse theorem for the Gowers-3 norm of n-qubit quantum states ∣ψ⟩ which states that: for every γ≥0, if the Gowers(∣ψ⟩,3)8≥γ then the stabilizer fidelity of ∣ψ⟩ is at least γC for some constant C>1. This implies a constant-sample polynomial-time tolerant testing algorithm for stabilizer states which accepts if an unknown state is ε1-close to a stabilizer state in fidelity and rejects when ∣ψ⟩ is ε2≤ε1C-far from all stabilizer states, promised one of them is the case.