Search papers, labs, and topics across Lattice.
This paper introduces a quantum analog of lazy sampling through the development of a path-recording oracle that efficiently simulates random elements from any closed subgroup of \( U(N) \). By storing input-output pairs in superposition, this oracle allows for on-the-fly simulation of quantum queries while transparently recording the information learned by the algorithm. The findings not only enhance the interpretability of quantum data structures but also provide a novel technique for proving pseudorandomness results, notably yielding a simpler construction of pseudorandom unitaries compared to previous methods.
A new path-recording oracle enables efficient simulation of quantum queries while transparently recording learned information, transforming our approach to pseudorandomness in quantum algorithms.
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).
BAIR