Agnostic learning of qudit stabilizer states

Technical Summary: Agnostic Learning of Qudit Stabilizer States

Problem Statement
The paper addresses the fundamental task of efficiently learning a classical description of an unknown quantum state. While learning arbitrary states suffers from the curse of dimensionality, learning structured states (such as stabilizer states) is more tractable. However, existing algorithms for stabilizer states typically operate in the "realizable" setting, assuming the unknown state exactly matches a stabilizer state. In realistic scenarios, noise drives the target state away from this ideal structure. This motivates the agnostic learning problem: given copies of an unknown state $|\psi\rangle$ that has a fidelity $\tau$ with some unknown stabilizer state, the goal is to output a stabilizer state $|\phi\rangle$ such that $F(|\psi\rangle, |\phi\rangle) \ge \max_{|\phi'\rangle \in \mathcal{C}} F(|\psi\rangle, |\phi'\rangle) - \varepsilon$, where $\mathcal{C}$ is the class of stabilizer states.

While Chen et al. [STOC '25] recently resolved this for qubit systems ($d=2$) using a stabilizer bootstrapping framework, the problem for qudit systems (where the local dimension $d > 2$ is an odd prime) remained largely unexplored. Direct generalization of qubit techniques fails due to fundamental structural differences, particularly regarding the behavior of Weyl operators and the distribution of measurement outcomes.

Methodology and Key Techniques
The authors generalize the stabilizer bootstrapping framework to qudit systems by overcoming three primary technical challenges:

1. Failure of Standard Bell Difference Sampling: In qubit systems, Bell difference sampling produces samples from the Weyl distribution $q_\psi$. In qudit systems, a direct generalization yields a distorted distribution that fails to concentrate on the stabilizer group. The authors employ skewed Bell difference sampling (introduced by Allcock et al. [23] for the realizable setting). This protocol uses an entangling unitary constructed from quadratic residues modulo $d$ to process four copies of the state. To handle the complexity of the joint distribution in the agnostic setting, the authors analyze the marginal distribution $B_\psi$ of a single output string.

2. Anti-Concentration of the Marginal Distribution: A crucial requirement for bootstrapping is that the sampling distribution places sufficient mass on the stabilizer group elements outside the currently known subgroup (anti-concentration). The authors prove that for any proper subspace $T$ of the target stabilizer group $S$, the marginal distribution satisfies $\sum_{x \in S \setminus T} B_\psi(x) \ge \Omega(\tau^6)$.

   • Key Insight: The proof bypasses a complex multivariate optimization required for general $d$ by reducing the problem to a single-qudit case. They establish a lower bound on the stabilizer fidelity of any single-qudit state ($2/(d+1)$) by leveraging the fact that single-qudit stabilizer states form a complex projective 2-design and constitute $d+1$ mutually unbiased bases.

3. Non-Hermiticity of Weyl Operators: In the qubit setting, Weyl operators are Hermitian, allowing for efficient batch estimation of correlations via Bernoulli mean estimation. For qudits ($d>2$), Weyl operators are generally non-Hermitian, making $\langle \psi | W_x | \psi \rangle$ complex. The authors address this by estimating squared correlations $|\langle \psi | W_x | \psi \rangle|^2$ individually using the SWAP test, rather than relying on Hermitian observables.

Algorithmic Framework
The proposed algorithm follows an iterative stabilizer bootstrapping procedure:

1. Sampling: Perform skewed Bell difference sampling to obtain Pauli strings from the marginal distribution $B_\psi$.
2. Filtering: Estimate the squared correlation of sampled strings with the current working state. Retain "high-correlation" strings (those with correlation $> 1 - 1/(12d^2)$).
3. Basis Construction: Form a basis from the commuting high-correlation strings. If the basis is incomplete (does not generate the full stabilizer group), the anti-concentration property ensures that with probability $\Omega(\tau^6)$, a new stabilizer element outside the current span is sampled.
4. Bootstrapping: If a low-correlation stabilizer element is found, measure the state in its eigenbasis and post-select. This amplifies the fidelity with the target stabilizer state by a constant factor.
5. Iteration: Repeat the process with the amplified state until the full stabilizer group is identified.

Additionally, for the high-fidelity regime ($\tau > \cos^2(\pi/8)$), the authors present a streamlined algorithm. They prove that in this regime, the squared correlations of Weyl operators inside the stabilizer group are strictly separated from those outside. This allows for a direct threshold-based approach that bypasses the iterative bootstrapping machinery, yielding polynomial complexity.

Results and Complexity
The paper presents the first efficient quantum algorithm for agnostic learning of pure-state qudit stabilizer states ($d > 2$ prime).

• General Regime: Given an unknown $n$-qudit state with stabilizer fidelity $\tau$, the algorithm outputs a stabilizer state with fidelity at least $\tau - \varepsilon$ with high probability.

  • Sample Complexity: $O(n \log n) \cdot (d/\tau)^{O(d^2 \log(1/\tau))} + O(d/\varepsilon^2 \log^2(1/\tau))$.
  • Time Complexity: $O(n^3/\varepsilon^2) \cdot (d/\tau)^{O(d^2 \log(1/\tau))}$.
  • The complexity is quasi-polynomial when $\tau = 1/\text{poly}(n)$, matching the best-known results for qubits.

• High-Fidelity Regime ($\tau > \cos^2(\pi/8) + \gamma$):

  • Sample Complexity: $O(d^4 n \log n / \gamma^2)$.
  • Time Complexity: $O(n^3 + n^2 d^4 \log n / \gamma^2)$.
  • This regime admits a polynomial-time solution.

• Corollaries:

  • Magic Estimation: The algorithm enables efficient estimation of the "magic" of a quantum state (quantified by stabilizer fidelity) with additive error $\varepsilon$.
  • List-Decoding: The method can be extended to output a list of all stabilizer states with fidelity $\ge \tau$.

Significance and Claims
The authors claim this work completes the picture of agnostic learning for stabilizer states by extending the qubit results to qudits. The significance lies in:

1. Bridging the Gap: Providing the first efficient solution for agnostic learning in the qudit setting, which was previously open due to structural obstructions in generalizing Bell difference sampling.
2. Robustness: The algorithm is designed to handle noise (agnostic setting), making it applicable to realistic quantum systems where states are not perfect stabilizers.
3. Foundational Tools: The paper establishes new anti-concentration bounds for skewed Bell difference sampling and proves lower bounds on single-qudit stabilizer fidelity using 2-design properties, which may have independent utility.
4. Magic Quantification: By enabling efficient estimation of stabilizer fidelity, the work provides a practical tool for quantifying quantum magic, a key resource for quantum advantage.

The authors note that their results are currently restricted to odd prime dimensions and that extending to composite dimensions or mixed states remains an open challenge. They also highlight that the quasi-polynomial dependence on $1/\tau$ is a limitation shared with qubit algorithms, and improving this to polynomial time while maintaining polynomial dependence on $n$ and $1/\varepsilon$ is a major open problem.