Agnostic learning of qudit stabilizer states

• URL: http://arxiv.org/abs/2607.15559v1
• Date: Fri, 17 Jul 2026 02:03:05 GMT
• Title: Agnostic learning of qudit stabilizer states
• Abstract summary: We present the first efficient quantum algorithm for learning of qudit stabilizer states.<n>As a direct agnostic, our algorithm enables efficient estimation of the magic of a quantum state.<n>We also present a streamlined algorithm for the high-fidelity regime.
• Score: 6.654420241400133
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Adiabatic Quantum Phase Estimation [47.3103723337301]
  Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $$ in Heisenberg-limited time $T= (1/)$.<n>Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware.<n>We present a simple adiabatic protocol for QPE that achieves the optimal Heisenberg-limited scaling $T = Oleft( frac1 logleft(-1right)right)$ in both the precision $$
  arXiv  Detail & Related papers  (2026-05-21T17:31:36Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  We provide a refined convergence analysis of the Single-loop Approximate Implicit Differentiation (SSAID) algorithm.<n>Our result is noteworthy in two aspects: (i) it matches the optimal $mathcalO(-2)$ rate of state-of-the-art multi-loop methods; and (ii) it provides the first explicit, fine-grained characterization of the $$-dependence.
  arXiv  Detail & Related papers  (2026-02-27T03:12:08Z)
• The non-stabilizerness cost of quantum state estimation [35.18016233072556]
  We study the non-stabilizer resources required to achieve informational completeness in single-setting quantum state estimation scenarios.<n>We prove that when only stabilizer resources are allowed, these strategies are always informationally equivalent to projective measurements in a stabilizer basis.<n>We unveil a tight connection between entanglement structure and informational power of measurements implemented with $t$-doped Clifford circuits.
  arXiv  Detail & Related papers  (2025-09-30T18:27:59Z)
• Non-stabilizerness of Neural Quantum States [41.94295877935867]
  We introduce a methodology to estimate non-stabilizerness or "magic", a key resource for quantum complexity, with Neural Quantum States (NQS)<n>We study the magic content in an ensemble of random NQS, demonstrating that neural network parametrizations of the wave function capture finite non-stabilizerness besides large entanglement.
  arXiv  Detail & Related papers  (2025-02-13T19:14:15Z)
• Improved bounds for testing low stabilizer complexity states [6.169364905804677]
  We improve the state-of-the-art parameters for the tolerant testing of stabilizer states. We also study the problem of testing low stabilizer rank states.
  arXiv  Detail & Related papers  (2024-10-31T17:56:57Z)
• Faster computation of nonstabilizerness [3.8061090528695543]
  The stabilizer extent is a useful tool to estimate the simulation cost using rank-based simulators.<n>We propose faster numerical algorithms to compute the stabilizer extent.
  arXiv  Detail & Related papers  (2024-06-24T14:28:15Z)
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications [0.5735035463793009]
  We apply stabilizer states to tackle quantum many-body ground state problems.<n>We develop an exact and linear-scaled algorithm to obtain stabilizer ground states of 1D local Hamiltonians.
  arXiv  Detail & Related papers  (2024-03-13T11:54:25Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• Bases for optimising stabiliser decompositions of quantum states [14.947570152519281]
  We introduce and study the vector space of linear dependencies of $n$-qubit stabiliser states. We construct elegant bases of linear dependencies of constant size three. We use them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques.
  arXiv  Detail & Related papers  (2023-11-29T06:30:05Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
  We study the complexity of learning quantum states in various models with respect to the stabilizer formalism. We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states. We show that a modification of the above algorithm runs in time.
  arXiv  Detail & Related papers  (2023-04-27T01:58:28Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.