Quantum Lazy Sampling and Path Recording for Any Group

• URL: http://arxiv.org/abs/2606.30281v1
• Date: Mon, 29 Jun 2026 13:23:17 GMT
• Title: Quantum Lazy Sampling and Path Recording for Any Group
• Abstract summary: We study a quantum analog of lazy sampling: compressed oracles (or recording oracles)<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.<n>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.
• Score: 3.495214699450807
• License: http://creativecommons.org/licenses/by/4.0/
• 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).

Related papers

• Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
  We introduce a new quantum query lower bound framework.<n>We show how this framework behaves on the problem of finding equal elements in the input string.<n>In particular, we demonstrate its power by proving a first tight quantum query lower bound for the k-Distinctness problem.
  arXiv  Detail & Related papers  (2026-04-06T19:52:58Z)
• Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms [0.0]
  We present a general method for simulating an action of $t$ copies of a Haar random unitary for arbitrary compact groups.<n>It is conceptually simple, exact and utilizes Clebsch-Gordan transforms as main building blocks.
  arXiv  Detail & Related papers  (2025-09-30T17:57:08Z)
• Compressed Permutation Oracles [0.6768558752130311]
  We develop and prove soundness of a compressed permutation oracle.<n>We re-prove essentially all known quantum query lower bounds in the random permutation model.
  arXiv  Detail & Related papers  (2025-09-23T03:13:48Z)
• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs. We show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model.
  arXiv  Detail & Related papers  (2024-07-12T19:27:13Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles.<n>We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
  arXiv  Detail & Related papers  (2024-01-25T17:13:51Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
  arXiv  Detail & Related papers  (2021-03-16T11:05:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.