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

CREATORBen Foxman and Alex Lombardi and Fermi Ma and Barak Nehoran and John Wright
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE482 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30281

Browse the full library · About the Tower of Babel