# Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2024.

## Built on by (most cited first, 1 of 1)

- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qudits of dimension d>2. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for d=p prime we devise a quantum algorithm to identify an unknown stabiliser state in (mathbbCp)otimes n that uses O(n) copies of the input state and runs in time O(n4). As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension d using O(logn/logd) auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.