# Quantum Pseudorandomness and Classical Complexity

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2021.

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

- [A quantum tug of war between randomness and symmetries on homogeneous spaces](https://mlsanity.com/paper/2309.05253/) (2023)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

We construct a quantum oracle relative to which mathsfBQP = mathsfQMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if mathsfBQP = mathsfPP. We discuss implications of these results for cryptography, complexity theory, and shadow tomography.