# Quantum Cryptography in Algorithmica

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2022.

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

- [How to Construct Random Unitaries](https://mlsanity.com/paper/2410.10116/) (2024)
- [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 classical oracle relative to which mathsfP = mathsfNP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of mathsfP vs. mathsfNP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which mathsfP = mathsfNP but mathsfBQP neq mathsfQCMA, based on hardness of the OR circ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against mathsfAC0 circuits. This variant may be of independent interest.