We show that measuring pairs of qubits in the Bell basis can be used to obtain a simple quantum algorithm for efficiently identifying an unknown stabilizer state of n qubits. The algorithm uses O(n) copies of the input state and fails with exponentially small probability.
It is well-known that learning a pure n-qubit stabilizer state ∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩ linear in n. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/8, satisfies n+⌈log2(1/δ)⌉−3≤Lδ(n)≤n+⌈log2(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown n-qubit Clifford unitary from 2n+⌈log2(1/δ)⌉+4 queries, the n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension d>2. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for d=p prime we devise a quantum algorithm to identify an unknown stabiliser state in (Cp)⊗n that uses O(n) copies of the input state and runs in time O(n4). As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension d using O(logn/logd) auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an n-qubit stabilizer state can be learned from Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary n-qubit stabilizer state from Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with k qubits of quantum memory, the optimal testing tradeoff Θ(n−k+1/ε) at infidelity ε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most r, including states prepared by Clifford circuits with a bounded number of T gates, can be learned using O(n2r) single-copy measurements.
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.
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.
Bell sampling is a simple yet powerful tool based on measuring two copies of a quantum state in the Bell basis, and has found applications in a plethora of problems related to stabiliser states and measures of magic. However, it was not known how to generalise the procedure from qubits to d-level systems -- qudits -- for all dimensions d>2 in a useful way. Indeed, a prior work of the authors (arXiv'24) showed that the natural extension of Bell sampling to arbitrary dimensions fails to provide meaningful information about the quantum states being measured. In this paper, we overcome the difficulties encountered in previous works and develop a useful generalisation of Bell sampling to qudits of all d≥2. At the heart of our primitive is a new unitary, based on Lagrange's four-square theorem, that maps four copies of any stabiliser state ∣S⟩ to four copies of its complex conjugate ∣S∗⟩ (up to some Pauli operator), which may be of independent interest. We then demonstrate the utility of our new Bell sampling technique by lifting several known results from qubits to qudits for any d≥2: 1. Learning stabiliser states in O(n3) time with O(n) samples; 2. Solving the Hidden Stabiliser Group Problem in O~(n3/ε) time with O~(n/ε) samples; 3. Testing whether ∣ψ⟩ has stabiliser size at least dt or is ε-far from all such states in O~(n3/ε) time with O~(n/ε) samples; 4. Clifford circuits with at most n/2 single-qudit non-Clifford gates cannot prepare pseudorandom states; 5. Testing whether ∣ψ⟩ has stabiliser fidelity at least 1−ε1 or at most 1−ε2 with O(d2ε2/(ε2−ε1)2) samples if ε1=O(ε2/d2).