Quantum Lazy Sampling and Path Recording for Any Group
2026-06-29 • Computational Complexity
Computational ComplexityCryptography and Security
AI summaryⓘ
The authors study how to simulate quantum algorithms that query a random element from a group, like a random unitary or permutation. They build a new quantum data structure called a path-recording oracle that keeps track of all interactions with the oracle in an understandable way. This oracle perfectly mimics random group elements and helps analyze what information an algorithm has learned after multiple queries. Their method improves the understanding of pseudorandom quantum objects and leads to a simpler way to construct pseudorandom unitaries by combining pseudorandom permutations with random Clifford operators.
Quantum algorithmsOracleRandom unitaryRandom permutationLazy samplingCompressed oraclePath-recording oraclePseudorandom unitaryClifford groupGroup representation
Authors
Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, John Wright
Abstract
A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing $S_N$ and $U(N)$ yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).