We study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state $ρ$ that either has fidelity at least $\varepsilon_1$ with some stabilizer pure state or fidelity at most $\varepsilon_2$ with all such states, where $\varepsilon_2 \leq \varepsilon_1^{O(1)}$, our algorithm distinguishes the two cases with sample complexity $\text{poly}(1/\varepsilon_1)$ and time complexity $O(n \cdot \text{poly}(1/\varepsilon_1))$.
We study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state ρ that either has fidelity at least ε1 with some stabilizer pure state or fidelity at most ε2 with all such states, where ε2≤ε1O(1), our algorithm distinguishes the two cases with sample complexity poly(1/ε1) and time complexity O(n⋅poly(1/ε1)).
We study the following quantum state identity problem: given access to copies of n unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε or some pair has fidelity at most ε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ. The second uses the Schur transform to reduce the sample complexity to O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−c, for any constant c>0, establishing that the second algorithm achieves the optimal dependence on both n and δ for fixed ε.
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.
We consider the problem of testing whether an unknown n-qubit quantum state ∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
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 study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using 6 copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that
(1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group.
(2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n2/k).
As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0<c<1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.
Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is ≥ε1 or ≤ε2, given one of them is the case, provided that ε2≤ε1O(1). This result improves the parameters in the previous work [AD24] which assumed ε2≤e−1/ε1O(1) [AD24]. Our proof technique extends the toolsets developed in [AD24] by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions [HHL19, Sam07], where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result of [GIKL22], one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random. At the same time our work was completed and posted on arXiv, two other groups [BvDH24, ABD24] independently achieved similar exponential to polynomial improvements for tolerant testing, each using a different approach.