# Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more

arXiv: https://arxiv.org/abs/2510.06848 · HTML: https://mlsanity.com/paper/2510.06848/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 68 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Builds on (most cited first, 19 of 19)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Improved Stabilizer Estimation via Bell Difference Sampling](https://mlsanity.com/paper/2304.13915/) (2023)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [Cryptography from Pseudorandom Quantum States](https://mlsanity.com/paper/2112.10020/) (2021)
- [Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom](https://mlsanity.com/paper/2209.14530/) (2022)
- [Pseudorandom unitaries are neither real nor sparse nor noise-robust](https://mlsanity.com/paper/2306.11677/) (2023)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [The state hidden subgroup problem and an efficient algorithm for locating unentanglement](https://mlsanity.com/paper/2410.12706/) (2024)
- [Quantum Pseudorandomness and Classical Complexity](https://mlsanity.com/paper/2103.09320/) (2021)
- [Quantum Cryptography in Algorithmica](https://mlsanity.com/paper/2212.00879/) (2022)
- [Tolerant Testing of Stabilizer States with Mixed State Inputs](https://mlsanity.com/paper/2411.08765/) (2024)
- [Quantum commitments and signatures without one-way functions](https://mlsanity.com/paper/2112.06369/) (2021)
- [Quantum Pseudoentanglement](https://mlsanity.com/paper/2211.00747/) (2022)
- [Single-copy stabilizer testing](https://mlsanity.com/paper/2410.07986/) (2024)
- [A note on polynomial-time tolerant testing stabilizer states](https://mlsanity.com/paper/2410.22220/) (2024)
- [From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments](https://mlsanity.com/paper/2210.05978/) (2022)
- [Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits](https://mlsanity.com/paper/2405.06357/) (2024)

## Abstract (arXiv)

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 |Srangle to four copies of its complex conjugate |S^astrangle (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 tildeO(n3/varepsilon) time with tildeO(n/varepsilon) samples; 3. Testing whether |psirangle has stabiliser size at least dt or is varepsilon-far from all such states in tildeO(n3/varepsilon) time with tildeO(n/varepsilon) samples; 4. Clifford circuits with at most n/2 single-qudit non-Clifford gates cannot prepare pseudorandom states; 5. Testing whether |psirangle has stabiliser fidelity at least 1-varepsilon1 or at most 1-varepsilon2 with O(d2varepsilon2/(varepsilon2-varepsilon1)2) samples if varepsilon1 = O(varepsilon2/d2).