pith. sign in

arxiv: 2606.30281 · v1 · pith:UJLWPJENnew · submitted 2026-06-29 · 🪐 quant-ph · cs.CC· cs.CR

Quantum Lazy Sampling and Path Recording for Any Group

Ben Foxman , Alex Lombardi , Fermi Ma , Barak Nehoran , John Wright This is my paper

Pith reviewed 2026-06-30 05:48 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.CR
keywords quantum oracleslazy samplingpath recordingcompressed oraclespseudorandom unitariesgroup representationsquantum cryptography
0
0 comments X

The pith

A path-recording oracle perfectly simulates random elements of any closed subgroup of U(N) by storing input-output pairs whose updates follow the group's commutant.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a quantum analog of lazy sampling that works for arbitrary closed subgroups of the unitary group. The oracle maintains a superposition of t input-output pairs and updates them according to the commutant of the group's tensor-power representation. This construction is derived from first principles and transparently records the information learned by any quantum algorithm making queries. It enables direct comparisons between oracles for different groups and yields a simple pseudorandom unitary construction from a pseudorandom permutation and a random Clifford.

Core claim

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.

What carries the argument

The path-recording oracle stores a superposition of input-output pairs and updates them using the commutant of the group's tensor-power representation to record learned information while maintaining perfect simulation.

If this is right

  • Direct comparisons between compressed oracles for different groups become possible, such as between S_N and U(N).
  • A simpler construction of pseudorandom unitaries follows as the product of a pseudorandom permutation and a random Clifford.
  • Quantum algorithms with oracle access to random group elements can be simulated on the fly while revealing what information has been learned after t queries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same commutant-based recording technique could support lower-bound arguments in quantum query complexity for problems involving group oracles.
  • Oracle comparisons across groups may produce new pseudorandomness results for other primitives that rely on random permutations or unitaries.

Load-bearing premise

The updates to the stored input-output pairs can be described exactly in terms of the commutant of the group's tensor-power representation while still perfectly simulating the random group element for every closed subgroup of U(N).

What would settle it

Finding a closed subgroup of U(N) where no commutant-based update rule can maintain both perfect simulation of the random element and transparent recording of learned pairs after multiple queries would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.30281 by Alex Lombardi, Barak Nehoran, Ben Foxman, Fermi Ma, John Wright.

Figure 1
Figure 1. Figure 1: In the two types of compressed oracles, the resulting data structures take different forms. The examples shown above correspond to the case in which the group is the unitary group. In fact, we derive both the tableau-recording oracle and the path-recording oracle together from first principles, establishing the following: • For every unitary representation ρ of a compact Lie group G, the tableau- and path-… view at source ↗
Figure 2
Figure 2. Figure 2: Example Clebsch-Gordan update for the unitary group, with the newly added box highlighted. Roughly speaking, each shape λ (Young diagram) that contains one extra box not in the original, and each valid filling (tableau) with the contents of X plus the new x value, receive some weight. In general, applying this transformation to |x, λ, X⟩ will produce a superposition of elements of the form [PITH_FULL_IMAG… view at source ↗
Figure 3
Figure 3. Figure 3: A single query can be decomposed into a Clebsch–Gordan transformation followed by the inverse dual-Clebsch-Gordan operation, though not on the same registers. The top three registers are those of the recording oracle’s data structure, while the bottom two are the algorithm’s registers. The algorithm’s multiplicity register (in cases where it exists) is not shown here since it is not touched by the update. … view at source ↗
Figure 4
Figure 4. Figure 4: When updating the tableau recording, both tableaux grow in the same way, such that the resulting shapes will always be identical. For the unitary group, this (very roughly) means that we add a box in the same place (in superposition over valid locations) for both the X and Y tableaux. In fact, rather than using direct implementations of a dual Clebsch-Gordan transform [Ngu23, GBO23], we observe a simple id… view at source ↗
Figure 5
Figure 5. Figure 5: Example complex conjugate query for the unitary group. [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example transpose query for the unitary group. [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The symmetric group algebra, C[St], the partition algebra, Pt(N), and other diagram algebras can be described in terms of a basis of partition diagrams that partition t top vertices and t bottom vertices into components. See Section 3.5 for more details. 29We remark that the recording register was previously in the image of ΩAt , so intuitively ΩAt+1 is only imposing additional symmetries involving the las… view at source ↗
Figure 8
Figure 8. Figure 8: Example of a partition diagram. Note that the connected components are important, but the specific graph connecting them is not. Definition 3.14 (Multiplication of Diagrams). Given two partition diagrams D1 and D2, the product diagram D1D2 is defined by identifying the vertices in the bottom row of D1 with the vertices in the top row of D2 (see [PITH_FULL_IMAGE:figures/full_fig_p034_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Multiplication of partition diagrams. The green component is confined to the middle layer and drops out to become an extra factor of N. Note that when D1 and D2 are permutation diagrams, where each component in the input row is connected to exactly one component in the output row, Definition 3.14 coincides with the usual composition rule for permutations in St . Definition 3.15 (Diagram Algebras [KS08]). F… view at source ↗
Figure 10
Figure 10. Figure 10: Example of a semistandard tableau with shape (4 [PITH_FULL_IMAGE:figures/full_fig_p042_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Shifting the semistandard Young tableau by a column maintains a valid order in the positive tableau. The Weyl Dimension Formula [Wey39] counts the number of semi-standard Young tableaux of a certain shape λ and thus gives the dimension of the corresponding irreducible representation. Lemma 3.27. Let λ be a Young diagram. The number of semi-standard Young tableaux of shape λ is dim  V λ U(N)  = Y N i=1 Y… view at source ↗
Figure 12
Figure 12. Figure 12: A single query can be decomposed into a Clebsch–Gordan transformation followed by an inverse dual-Clebsch–Gordan operation, though not on the same registers. The adversary’s multiplicity register is not shown since it is not touched by the update. 4.2.1 Equivalence of the uncompressed and tableau recording oracles Having defined our two recording oracles, we are ready to state the main result of this sect… view at source ↗
Figure 13
Figure 13. Figure 13: Example basis vectors in a complex conjugate query for the unitary group. [PITH_FULL_IMAGE:figures/full_fig_p051_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Example basis vectors in a transpose query for the unitary group. [PITH_FULL_IMAGE:figures/full_fig_p052_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Example basis vectors in an inverse query for the unitary group. [PITH_FULL_IMAGE:figures/full_fig_p052_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Colored permutation diagram on 6 elements with colors f1, . . . , f6 ∈ ZK attached to the strands. Diagram multiplication occurs by concatenation of the underlying permutations and summing (mod K) the colors along each merged strand. We will be interested here in the Schur representation of ZK ≀ St on (C KN ) ⊗t , which generalizes the Schur representation of St (Definition 3.16) by adding a phase of ω fi… view at source ↗
Figure 17
Figure 17. Figure 17: Colored even-partition diagram on 8 elements with colors f1, f2, f3, f4 ∈ ZK attached to the four components. 50This diagram algebra is closely related to the G-colored partition algebras studied by [Blo03]. 95 [PITH_FULL_IMAGE:figures/full_fig_p095_17.png] view at source ↗
read the original 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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript defines and analyzes a path-recording oracle that stores superpositions of t input-output pairs for any closed subgroup of U(N). Updates to these pairs are expressed via the commutant of the group's tensor-power representation, yielding a first-principles construction that perfectly simulates a uniform random group element while transparently recording the information learned by a quantum algorithm. The work extends prior compressed-oracle techniques and applies the construction to obtain a simple pseudorandom-unitary construction by comparing the oracles for S_N and U(N).

Significance. If the central derivation holds, the result supplies a general, interpretable quantum lazy-sampling tool applicable to arbitrary closed subgroups, improving on the non-interpretable general-purpose oracle of Grinko-Yoshida. The direct-comparison technique for proving pseudorandomness is a concrete methodological contribution, and the PC construction (pseudorandom permutation composed with random Clifford) is presented as simpler than the prior PFC construction.

minor comments (3)
  1. The abstract cites Grinko-Yoshida (QIP '26), Ma-Huang (STOC '25), Carolan (STOC '26), and Metger-Poremba-Sinha-Yuen (FOCS '24); the bibliography should list these works with full bibliographic details and arXiv numbers where applicable.
  2. Notation for the commutant of the tensor-power representation is introduced without an explicit reference to the standard definition in representation theory; a brief reminder or citation in the preliminaries would aid readability.
  3. The pseudorandom-unitary application is described at a high level; adding a short pseudocode or diagram contrasting the PC and PFC constructions would clarify the claimed simplification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report highlights the interpretability of the path-recording oracle and the direct-comparison technique for pseudorandom unitaries, which aligns with our goals.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines a path-recording oracle derived from first principles whose updates are expressed via the commutant of the group's tensor-power representation, enabling perfect simulation of random elements from any closed subgroup of U(N). No step reduces by construction to a fitted input, self-definition, or load-bearing self-citation; the central claim rests on the mathematical properties of the commutant rather than re-labeling or prior author results. External citations (Grinko-Yoshida, Metger et al.) are used for comparison and improvement but do not justify the core construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The construction assumes the mathematical machinery of representation theory (commutants of tensor-power representations) is available and that the group is closed in U(N); no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption The group in question is a closed subgroup of U(N).
    Explicitly stated as the setting for which the oracle perfectly simulates random elements.
  • domain assumption Updates to the stored pairs are governed by the commutant of the group's tensor-power representation.
    Central to the description of how the oracle records information.

pith-pipeline@v0.9.1-grok · 5895 in / 1316 out tokens · 21286 ms · 2026-06-30T05:48:09.207310+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 8 canonical work pages · 3 internal anchors

  1. [1]

    Pseudorandom unitaries in the haar random oracle model

    [ABGL25a] Prabhanjan Ananth, John Bostanci, Aditya Gulati, and Yao-Ting Lin. Pseudorandom unitaries in the haar random oracle model. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part II , volume 16001 of LNCS, pages 301–333. Springer, Cham, August

    2025

  2. [2]

    Pseudorandom- ness in the (inverseless) haar random oracle model

    117 [ABGL25b] Prabhanjan Ananth, John Bostanci, Aditya Gulati, and Yao-Ting Lin. Pseudorandom- ness in the (inverseless) haar random oracle model. In Serge Fehr and Pierre-Alain Fouque, editors, EUROCRYPT 2025, Part VII , volume 15607 of LNCS, pages 138–166. Springer, Cham, May

    2025

  3. [3]

    On the limitations of pseu- dorandom unitaries - or: Cryptographic applications of LOCC indistinguishability of identical versus independent haar unitaries

    [AGL25] Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. On the limitations of pseu- dorandom unitaries - or: Cryptographic applications of LOCC indistinguishability of identical versus independent haar unitaries. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025, Part III , volume 16270 of LNCS, pages 69–103. Springer, Cham, December

    2025

  4. [4]

    Unclonable Encryption in the Haar Random Oracle Model

    [BG26] James Bartusek and Eli Goldin. Unclonable encryption in the haar random oracle model. arXiv preprint arXiv:2603.11437 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    [CFHL21] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao

    Association for Computing Machinery. [CFHL21] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed- oracle technique, and post-quantum security of proofs of sequential work. In Anne Canteaut and Fran¸ cois-Xavier Standaert, editors,EUROCRYPT 2021, Part II , volume 12697 of LNCS, pages 598–629. Springer, Cham, October

    2021

  6. [6]

    Gelfand-tsetlin basis for partially transposed permutations, with applications to quantum information

    [GBO23] Dmitry Grinko, Adam Burchardt, and Maris Ozols. Gelfand-tsetlin basis for partially transposed permutations, with applications to quantum information. arXiv preprint arXiv:2310.02252,

    work page arXiv

  7. [7]

    Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms

    [GY25] Dmitry Grinko and Satoshi Yoshida. Quantum simulation of random unitaries from clebsch-gordan transforms. arXiv preprint arXiv:2509.26623 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    The NISQ complexity of collision finding

    [HLS24] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. The NISQ complexity of collision finding. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part IV , volume 14654 of LNCS, pages 3–32. Springer, Cham, May

    2024

  9. [9]

    Pseudorandom function-like states from common haar unitary

    [HY25] Minki Hhan and Shogo Yamada. Pseudorandom function-like states from common haar unitary. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025, Part III , volume 16270 of LNCS, pages 134–165. Springer, Cham, December

    2025

  10. [10]

    The compressed oracle is a worthy (multiplicative) adversary

    [JZ25] Stacey Jeffery and Sebastian Zur. The compressed oracle is a worthy (multiplicative) adversary. arXiv preprint arXiv:2509.07876 ,

    work page arXiv

  11. [11]

    On finding quantum multi-collisions

    [LZ19a] Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III , volume 11478 of LNCS, pages 189–218. Springer, Cham, May

    2019

  12. [12]

    Revisiting post-quantum Fiat-Shamir

    [LZ19b] Qipeng Liu and Mark Zhandry. Revisiting post-quantum Fiat-Shamir. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II , volume 11693 of LNCS, pages 326–355. Springer, Cham, August

    2019

  13. [13]

    The mixed schur transform: efficient quantum circuit and applications

    [Ngu23] Quynh T Nguyen. The mixed schur transform: efficient quantum circuit and applications. arXiv preprint arXiv:2310.01613 ,

    work page arXiv

  14. [14]

    On quantum query complexities of collision- finding in non-uniform random functions

    120 [PCX25] Tianci Peng, Shujiao Cao, and Rui Xue. On quantum query complexities of collision- finding in non-uniform random functions. In Goichiro Hanaoka and Bo-Yin Yang, editors, ASIACRYPT 2025, Part VIII, volume 16252 of LNCS, pages 193–223. Springer, Singapore, December

    2025

  15. [15]

    Tight bounds for inverting permutations via compressed oracle arguments

    [Ros21] Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv preprint arXiv:2103.08975 ,

    work page arXiv

  16. [16]

    Strong random unitaries and fast scrambling

    [SML+25] Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, and Hsin-Yuan Huang. Strong random unitaries and fast scrambling. arXiv preprint arXiv:2509.26310 ,

    work page arXiv

  17. [17]

    Amplitude amplification and estimation require inverses

    [TW25] Ewin Tang and John Wright. Amplitude amplification and estimation require inverses. arXiv preprint arXiv:2507.23787 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    Towards compressed permutation oracles

    [Unr23] Dominique Unruh. Towards compressed permutation oracles. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part IV , volume 14441 of LNCS, pages 369–400. Springer, Singapore, December

    2023

  19. [19]

    How to record quantum queries, and applications to quantum indiffer- entiability

    [Zha19] Mark Zhandry. How to record quantum queries, and applications to quantum indiffer- entiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 239–268. Springer, Cham, August

    2019

  20. [20]

    How to model unitary oracles

    [Zha25] Mark Zhandry. How to model unitary oracles. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part II , volume 16001 of LNCS, pages 237–268. Springer, Cham, August

    2025