{"id":"arxiv/2606.30281","url":"https://arxiv.org/abs/2606.30281","tags":["quant-ph","cs.CC","cs.CR"],"score":0,"title":"Quantum Lazy Sampling and Path Recording for Any Group","domain":"quant-ph","source":"arxiv","authors":["Ben Foxman","Alex Lombardi","Fermi Ma","Barak Nehoran","John Wright"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}