Technical Summary: Reconquering Bell Sampling on Qudits

1. Problem Statement

Bell sampling is a fundamental primitive in quantum information, particularly for analyzing stabilizer states and measuring "magic" (non-stabilizer resources). In the qubit case ($d=2$), Bell sampling (measuring two copies of a state in the Bell basis) and its variant, Bell difference sampling, allow for the efficient learning of unknown stabilizer states, testing stabilizer properties, and distinguishing pseudorandom states from Haar-random ones.

However, generalizing these techniques to qudits (systems of dimension $d \geq 2$) has proven difficult. A prior work by the authors (arXiv'24) demonstrated that the "natural" extension of Bell sampling to arbitrary dimensions fails: measuring two copies of a stabilizer state in the generalized Bell basis can yield a completely random output, providing no information about the underlying stabilizer group. This failure stems from the fact that the transpose map (complex conjugation) is not completely positive, and for $d > 2$, a stabilizer state $|S\rangle$ and its complex conjugate $|S^*\rangle$ are not necessarily related by a simple Pauli operator, unlike in the qubit case where $|S^*\rangle = W_z |S\rangle$.

The central problem addressed in this paper is to develop a useful generalization of Bell sampling to qudits of all dimensions $d \geq 2$ that retains the powerful properties of the qubit case, specifically the ability to sample generators of the stabilizer group.

2. Methodology and Core Primitive

The authors propose a new subroutine, Skewed Bell Difference Sampling, which overcomes the limitations of the natural extension. The core innovation is a specific unitary transformation based on Lagrange's four-square theorem.

The $B_R$ Unitary

The method relies on a unitary operator $B_R$ acting on four copies of a stabilizer state $|S\rangle^{\otimes 4}$. The unitary is defined by a matrix $R \in \mathbb{Z}_d^{4 \times 4}$ constructed from non-negative integers $a_1, a_2, a_3, a_4$ such that $a_1^2 + a_2^2 + a_3^2 + a_4^2 = d-1$.
The matrix $R$ is constructed such that $R J R = -I \pmod d$, where $J$ is the involution map on the symplectic module.

Key Property: For any stabilizer state $|S\rangle$, the unitary $B_R$ maps the four copies to their complex conjugates (up to a Pauli operator):
$$B_R |S\rangle^{\otimes 4} = P(S) |S^*\rangle^{\otimes 4}$$
where $P(S)$ is a Pauli operator dependent on $|S\rangle$. This transformation effectively "mixes" the states to align the stabilizer group with its complex conjugate, a necessary condition for successful sampling.

Note: For specific dimensions (e.g., prime $d$ where $-1$ is a quadratic residue), fewer than four copies may suffice (e.g., 2 copies or even 1 copy if $d \equiv 1 \pmod 4$).

The Sampling Procedure

The full Skewed Bell Difference Sampling algorithm proceeds as follows:

1. Prepare 8 copies of the state $|\psi\rangle$.
2. Apply the unitary $B_R$ to 4 of the copies to transform them into $|S^*\rangle^{\otimes 4}$ (up to Paulis).
3. Pair the transformed copies with the original 4 copies.
4. Perform standard Bell sampling on each pair $(|S\rangle, |S^*\rangle)$.
5. Compute the differences between the outcomes.

The resulting distribution, denoted $\hat{p}_\psi$, is shown to be supported on the orthogonal complement of the unsigned stabilizer group $Weyl(|\psi\rangle)$. If $|\psi\rangle$ is a stabilizer state, the samples are uniformly distributed over the stabilizer group itself.

3. Key Contributions and Results

The paper demonstrates that this new primitive allows for the lifting of several major qubit-based results to qudits for all $d \geq 2$.

A. Stabilizer State Learning and Hidden Stabilizer Group Problem

• Problem: Identify an unknown stabilizer state $|S\rangle$ or the hidden stabilizer group $Weyl(|\psi\rangle)$ given copies of the state.
• Result: The authors provide a quantum algorithm that identifies the stabilizer group with high probability using $O(n)$ samples and $O(n^3)$ time.
• Improvement: This improves upon the sample complexity of the recent Fourier sampling approach by Hinsche, Eisert, and Carrasco [HEC26], which required $O(n \log d \max\{d, \epsilon^{-1}\})$ samples. The new method acts on at most 8 copies at a time (4 for prime dimensions), whereas previous methods required $D$ copies (where $D$ can be $2d$), making it more feasible for large $d$.

B. Stabilizer Size Property Testing

• Problem: Test whether a state has a stabilizer size (cardinality of the unsigned stabilizer group) of at least $d^t$ or is $\epsilon$-far from any such state.
• Result: An algorithm distinguishes these cases in $O(n^3/\epsilon)$ time using $O(n/\epsilon)$ samples.
• Significance: This generalizes the qubit result by Grewal et al. [GIKL25] to arbitrary dimensions. The analysis involves submodules over rings $\mathbb{Z}_d$ rather than vector spaces over fields, requiring the use of Smith normal forms to analyze the span of samples.

C. Testing Doped Clifford Circuits and Pseudorandomness

• Problem: Distinguish between a Haar-random state and the output of a $t$-doped Clifford circuit (a Clifford circuit with $t$ non-Clifford gates).
• Result: The authors prove that any $t$-doped Clifford circuit with $t < n/2$ cannot generate pseudorandom states.
• Improvement: This establishes a lower bound of $n/2$ non-Clifford gates required for pseudorandomness on qudits. This is an exponential improvement over previous qudit-specific bounds (which were $O(\log_d n)$) and matches the best-known bound for qubits. The algorithm distinguishes the two cases in $O(n^3)$ time using $O(n)$ samples.

D. Tolerant Stabilizer Testing

• Problem: Decide if a state has stabilizer fidelity at least $1-\epsilon_1$ or at most $1-\epsilon_2$ (where $\epsilon_1 < \epsilon_2$).
• Result: The paper proposes two algorithms:
  1. POVM-based: An extension of the Gross-Nezami-Walter (GNW) protocol using a specific POVM $\Pi_r^+$.
  2. Bell-sampling-based: A protocol using skewed Bell difference sampling followed by specific measurements.
• Complexity: Both algorithms achieve sample complexities of roughly $O(d^2 \epsilon_2 / (\epsilon_2 - \epsilon_1)^2)$. The Bell-sampling approach requires fewer copies (8) compared to the POVM approach (which requires $2r$ copies, where $r$ can be large), though the POVM approach may offer a wider range of valid parameters for certain dimensions.

4. Significance and Claims

The paper claims to "reconquer" Bell sampling on qudits by providing a non-trivial yet simple generalization that preserves the utility of the qubit case.

• Theoretical Breakthrough: The construction of the unitary $B_R$ based on Lagrange's four-square theorem is presented as a primitive of independent interest, solving the fundamental obstruction of mapping stabilizer states to their complex conjugates in higher dimensions.
• Unification: The work unifies the theory of stabilizer states across all dimensions $d \geq 2$, moving beyond the prime-dimension restrictions of previous works.
• Efficiency: The algorithms maintain polynomial time and sample complexities ($O(n^3)$ and $O(n)$) comparable to the qubit case, despite the increased algebraic complexity of working with modules over $\mathbb{Z}_d$.
• Pseudorandomness Bounds: The result that $n/2$ non-Clifford gates are necessary for pseudorandomness on qudits is highlighted as a significant tightening of previous bounds, closing the gap between qubit and qudit theories in this domain.

The authors emphasize that their results are derived strictly from the properties of the new sampling distribution $\hat{p}_\psi$ and do not rely on unproven conjectures. They explicitly note that while the sample complexity for tolerant testing is slightly worse than the best qubit results by a factor of $d^2$, it represents the first successful extension of these tolerant testing protocols to general qudits.