Quantum Lazy Sampling and Path Recording for Any Group
Ben Foxman and Alex Lombardi and Fermi Ma and Barak Nehoran and John Wright · 2026
Read Quantum Lazy Sampling and Path Recording for Any Group by Ben Foxman and Alex Lombardi and Fermi Ma and Barak Nehoran and John Wright (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30281.txt.
Introduction
Ben Foxman and four colleagues build a tool that mimics random objects for quantum algorithms. Researchers often study algorithms given oracle access to a random function, permutation or unitary. An oracle is a black box the algorithm may question but not inspect. Classically, lazy sampling answers such questions on the fly. The quantum analogue, called a compressed or recording oracle, is harder because queries can arrive in superposition.
The team define a path-recording oracle that stores superpositions of input-output pairs. This openly records what an algorithm could have learned from its queries. It simulates, perfectly, random elements drawn from any closed subgroup of the unitary group. Their update rule is described through the commutant, the operations that commute with the group's action. Comparing oracles for permutations and unitaries then yields a simple route to pseudorandom unitaries. The recipe multiplies a pseudorandom permutation by a random Clifford operation.
Catalog record
| CREATOR | Ben Foxman and Alex Lombardi and Fermi Ma and Barak Nehoran and John Wright |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 482 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30281