Curator's Take
AI Commentary
This article delivers the first efficient algorithm for agnostically learning stabilizer states in qudit systems, extending the recent qubit‑only breakthrough of Chen et al. (STOC’25) to higher‑dimensional hardware where odd‑prime dimensions are increasingly explored for their error‑resilience and gate efficiency. By adapting the stabilizer bootstrapping framework to handle the richer algebraic structure of qudits, the authors achieve a sample and runtime scaling that remains polynomial in the number of registers while only modestly exponential in the local dimension d, opening realistic pathways for state verification and fault‑tolerant code design on platforms such as trapped‑ion or photonic qudits. The result sharpens our theoretical toolkit for quantum error correction beyond binary encodings and signals that practical learning of complex quantum states is becoming tractable even under noisy, real‑world conditions.
— Mark Eatherly
Summary
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 $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, 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 $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.