⚛️ quantum physics

Quantum Lazy Sampling and Path Recording for Any Group

This paper introduces a general-purpose, interpretable path-recording oracle that perfectly simulates random elements of any closed subgroup of $U(N)$ by storing superposed input-output pairs, thereby enabling direct comparisons between different groups to derive new pseudorandomness results, such as a simplified construction of pseudorandom unitaries.

Original authors: Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, John Wright

Published 2026-10-01

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, John Wright

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of quantum computing, scientists often need to understand how algorithms behave when they interact with something completely random. Imagine a machine that can ask questions to a mysterious, ever-changing black box. This box might hold a random function, a random shuffle of data, or a random transformation of quantum states. To prove that a new quantum algorithm works correctly, or to prove that a secret code is unbreakable, researchers must be able to predict what the algorithm learns after asking a certain number of questions. Classically, this is done using a technique called "deferred sampling." Instead of deciding the entire contents of the random box at the very beginning, the computer waits until the algorithm asks a specific question, and only then does it pick a random answer for that specific question. This keeps the simulation efficient and manageable.

However, quantum computers are different. They can ask many questions at once, existing in a state of superposition where they are effectively querying the box with many different inputs simultaneously. This makes the classical "deferred sampling" trick impossible to use directly, because the computer cannot simply wait to see what the algorithm asks; the algorithm has already asked everything at once. For years, researchers have struggled to create a quantum version of this tool. Without it, proving the security of quantum codes or understanding the limits of quantum speed is incredibly difficult. The challenge has been to build a digital record that updates itself on the fly, keeping track of what a quantum algorithm knows without collapsing its delicate superposition, and doing so in a way that humans can actually understand and use for proofs.

A team of researchers has now solved this problem by creating a new, universal tool called a "path-recording oracle." This tool acts as a perfect simulator for any random transformation that comes from a specific mathematical family, including random functions, random shuffles, and random quantum operations. Unlike previous attempts that were either too complex to understand or only worked for specific cases, this new method works for any closed group of transformations. The core idea is to record the "history" of the algorithm's journey. Instead of just storing a list of inputs and outputs, the new oracle stores a superposition of all the possible paths the algorithm could have taken. It keeps a running tally of every input-output pair the algorithm has encountered, but it does so in a way that respects the strange rules of quantum mechanics.

The researchers showed that this new oracle is not just a theoretical curiosity; it is a practical engine for proving security. By using this tool, they were able to demonstrate that a very simple construction for a "pseudorandom unitary"—a quantum operation that looks random to any observer but is actually generated by a short, efficient process—is secure. Their construction involves taking a random shuffle of data and multiplying it by a random quantum circuit known as a Clifford circuit. Previous work had suggested that this combination needed an extra layer of random phases to be secure, but the new analysis proved that the shuffle and the circuit alone are sufficient. This finding simplifies the design of secure quantum systems significantly, removing unnecessary complexity.

The power of this new tool lies in its ability to treat different types of randomness in a unified way. Whether the random element is a simple permutation of bits or a complex rotation of a high-dimensional quantum state, the path-recording oracle handles it with the same underlying logic. It records the information the algorithm gathers as a set of Feynman paths, which are essentially the possible histories of the interaction. The researchers proved that for a wide range of scenarios, the information recorded by this oracle is indistinguishable from the information an algorithm would get from a truly random source, provided the number of questions asked is not too large compared to the size of the system. This result provides a rigorous mathematical foundation for believing that certain quantum constructions are secure against even the most powerful quantum adversaries.

One of the most significant aspects of this work is that it bridges the gap between abstract mathematics and practical application. The researchers derived their tool from first principles, meaning they built it up from the basic rules of how quantum groups behave, rather than guessing a solution and checking if it works. They showed that their method perfectly simulates the behavior of random elements in any closed subgroup of unitary matrices. This includes the unitary group, which describes all possible reversible quantum operations, as well as the symmetric group, which describes all possible shuffles. By establishing a clear, interpretable link between the algorithm's queries and the recorded data, the researchers have provided a new standard for how quantum security proofs should be conducted.

The paper also addresses the limitations of previous methods. Earlier approaches to simulating quantum queries often relied on approximations that introduced small errors, or they were so mathematically opaque that it was impossible to tell exactly what information was being stored. The new path-recording oracle avoids these pitfalls. It offers a perfect simulation for the cases it covers, and when approximations are necessary, the researchers can precisely quantify the error. This level of control is essential for cryptographic proofs, where even a tiny flaw in the simulation could mean the difference between a secure system and a broken one. The researchers demonstrated that their tool could reproduce the results of previous specialized oracles, such as those for random functions and random unitaries, but with greater clarity and generality.

In the specific application of proving the security of the "PC" construction (a random permutation followed by a random Clifford circuit), the researchers used their new tool to show that the combination is indistinguishable from a truly random unitary operation. They analyzed the "distinct, nonplussed" subspace, a specific region of the quantum state space where the algorithm is most likely to operate. They found that within this region, the behavior of the random permutation and the random unitary are statistically identical. This means that an adversary trying to break the system cannot tell the difference between the constructed operation and a truly random one, as long as they do not make an excessive number of queries. This result confirms that the simpler construction is just as secure as more complex ones that were previously thought to be necessary.

The implications of this work extend beyond just one specific construction. By providing a general-purpose, interpretable framework for analyzing quantum queries, the researchers have opened the door to new discoveries in quantum cryptography and complexity theory. Their method allows for direct comparisons between different types of random groups, which can lead to new techniques for proving pseudorandomness. This could help in designing better encryption schemes, understanding the limits of quantum search algorithms, and verifying the correctness of quantum protocols. The ability to simulate these interactions efficiently and accurately is a critical step forward in the development of reliable quantum technologies.

The researchers also clarified the relationship between their new tool and existing methods. They showed that their path-recording oracle is mathematically equivalent to a previously proposed "tableau-recording oracle," but with the added benefit of being much easier to interpret. The tableau method, while powerful, was difficult to visualize and understand in terms of the actual information being recorded. The path-recording method, by contrast, keeps a clear record of the input-output pairs, making it transparent what the algorithm has learned. This transparency is crucial for building trust in the security proofs and for extending the results to new and more complex scenarios.

Ultimately, this work represents a significant maturation in the field of quantum algorithm analysis. It moves the field away from ad-hoc, case-by-case solutions toward a unified, principled approach. The path-recording oracle provides a robust, efficient, and understandable way to simulate quantum interactions with random oracles. This capability is fundamental to the future of quantum cryptography, as it allows researchers to rigorously prove that their systems are secure against quantum attacks. By solving the problem of how to efficiently and interpretably simulate these interactions, the researchers have provided the community with a powerful new lens through which to view and understand the quantum world.

Technical Summary: Quantum Random Sampling and Path Recording for Any Group

1. Problem Statement

A central challenge in quantum algorithm analysis and cryptography is reasoning about algorithms that have oracle access to a random group element (e.g., a random function, permutation, or unitary). To analyze such algorithms, one must determine what information they learn after $t$ queries and whether they can distinguish the random object from a pseudorandom one.

Classically, random sampling is the standard tool for this: instead of sampling the entire random object at the beginning, the simulator samples partial information (input-output pairs) on the fly as the algorithm queries. This allows for efficient simulation and clear tracking of the algorithm's knowledge.

In the quantum setting, algorithms can query in superposition and forget information, making classical random sampling insufficient. The existing solution is compressed oracles (or recording oracles), which maintain a quantum data structure of partial information. However, prior compressed oracles suffered from significant limitations:

Lack of Generality: Most were tailored to specific groups (e.g., Zhandry for Boolean functions, Ma-Huang for Haar-random unitaries, Carolan for permutations) using ad-hoc arguments.
Lack of Interpretability: A recent general-purpose proposal by Grinko and Yoshida (the "tableau-recording oracle") was mathematically sound but lacked a clear operational interpretation of the recorded data, hindering its use in proving lower bounds or security.
Approximation Errors: Some general constructions (like Ma-Huang) only achieved approximate simulation with error $O(t^2/N)$ , rather than perfect simulation.

The paper asks: Is there a general-purpose, interpretable compressed oracle that allows for quantum random sampling for every compact Lie group?

2. Methodology

The authors develop a framework derived from first principles to construct compressed oracles for any compact Lie group $G$ acting on $N$ qubits via a unitary representation $\rho: G \to U(N)$ . The methodology proceeds in two stages:

2.1 Tableau Recording (The Algebraic Foundation)

The authors first revisit and provide a new proof for the Tableau Recording Oracle ( $Q^{\text{Tab}}_\rho$ ), originally studied by Grinko and Yoshida.

Construction: They purify the random group element $g$ into the Hilbert space $L^2(G)$ and apply the Fourier Transform (generalized Peter-Weyl theorem) to move to a basis indexed by irreducible representations (irreps) of $G$ .
Mechanism: The oracle maintains a "recording register" in the Fourier basis (or "tableau basis"). A query updates this register by applying a Clebsch-Gordan transform (to decompose the tensor product of the current irrep with the query representation) followed by an inverse dual Clebsch-Gordan transform.
Properties: This oracle perfectly simulates the random group element and is efficient if the Clebsch-Gordan transforms are efficient. However, the contents of the recording register (superpositions of irrep labels and tableau states) are difficult to interpret operationally.

2.2 Path Recording (The Interpretation Layer)

To achieve interpretability, the authors define the Path Recording Oracle ( $Q^{\text{Path}}_\rho$ ).

Transformation: They define an isometry $\Gamma_t$ that maps the tableau basis to a path basis. The path basis consists of superpositions of ordered input-output pairs $|(x_1, y_1), \dots, (x_t, y_t)\rangle$ , representing the "Feynman paths" explored by the algorithm.
Symmetrization: The key insight is that the recording register must respect the symmetries of the commutant algebra $A_t = \text{End}_G((\mathbb{C}^N)^{\otimes t})$ $A_{t} = End_{G} ((C^{N})^{\otimes t})$ . The update rule involves:
1. Reweighting: Scaling subspaces in the Schur basis based on the dimensions of the irrep and the commutant algebra.
2. Appending: Adding a new EPR pair (input-output pair) to the database.
3. Symmetrizing: Projecting the state onto the commutant EPR subspace (the image of a projector $\Omega_{A_t}$ ). This projector enforces the symmetries of the group action, effectively "forgetting" the order of queries or other redundant information, similar to how classical random sampling for permutations forgets the order of distinct inputs.
Generality: This framework applies to any compact Lie group. The specific form of the symmetrization operator $\Omega_{A_t}$ depends on the commutant algebra (e.g., the symmetric group algebra for $U(N)$ , the partition algebra for $S_N$ ).

3. Key Contributions

3.1 A General Path-Recording Oracle

The paper defines and analyzes a path-recording oracle that:

Perfectly Simulates: It provides an exact simulation of Haar-random elements for any closed subgroup of $U(N)$ , eliminating the $O(t^2/N)$ simulation error found in previous general constructions.
Is Interpretable: The recording register explicitly stores superpositions of input-output pairs, making the information learned by the algorithm transparent.
Is Efficient: The update rule is expressed in terms of the commutant algebra and Clebsch-Gordan transforms, which are efficiently implementable for many groups of interest (e.g., $U(N)$ , $S_N$ ).

3.2 Unification of Prior Work

The authors demonstrate that their framework naturally recovers and unifies existing compressed oracles:

Zhandry's Oracle: Recovered as the path-recording oracle for the group $\mathbb{Z}_2^N$ (Boolean functions).
Ma-Huang Oracle: Recovered as an approximation of the path-recording oracle for $U(N)$ , where the subspace reweighting operators are approximated by scalars and the distinctness constraint is enforced.
Permutation Oracles: Recovered for the symmetric group $S_N$ .

3.3 New Pseudorandom Unitary Construction

The primary application of this framework is a new, simplified construction of Pseudorandom Unitaries (PRUs).

The Construction: The product $PC$ , where $P$ is a random (or pseudorandom) permutation and $C$ is a circuit sampled from a unitary 2-design (e.g., a random Clifford circuit).
The Result: The authors prove that $PC$ is indistinguishable from a Haar-random unitary to any adversary making $t$ queries, with a distinguishing advantage of $O(t^2/N)$ .
Improvement: This improves upon the previous "PFC" construction (Permutation + Phase + Clifford) by showing the random phase $F$ is unnecessary. It yields the simplest known PRU construction analyzed to date.

4. Results

4.1 Theoretical Guarantees

Theorem 1.5 (Informal): For any compact Lie group $G$ , there exists an isometry $Q^{\text{Path}}_\rho$ that perfectly simulates query access to a Haar-random $\rho(g)$ . The update rule involves reweighting, appending, and symmetrizing with respect to the commutant algebra $A_t$ .
Theorem 1.6: For a uniformly random in-place permutation $P$ and a unitary 2-design $C$ , the ensemble $P \cdot C$ is $O(t^2/N)$ -indistinguishable from a Haar-random unitary.
Theorem 1.7: If $P$ is sampled from a family of $(t, \epsilon)$ -secure post-quantum pseudorandom permutations, then $P \cdot C$ is an $\epsilon + O(t^2/N)$ approximate $t$ -design.

4.2 Technical Mechanisms for the PRU Proof

The proof of the PRU security relies on analyzing the path-recording oracles for both $S_N$ (permutations) and $U(N)$ (unitaries) on a specific subspace:

Distinct Nonplussed Subspace ( $DNP$ ): The intersection of the "distinct" subspace (no repeated inputs) and the "nonplussed" subspace (orthogonal to the uniform superposition $|+\rangle$ ).
Equivalence on $DNP$ : The authors prove that on the $DNP$ subspace, the commutant EPR projectors for the symmetric group ( $\Omega_{S_N}$ ) and the unitary group ( $\Omega_{U(N)}$ ) are effectively identical.
2-Design Property: A random 2-design $C$ maps almost all states into the $DNP$ subspace with high probability ( $1 - O(t^2/N)$ ).
Conclusion: Since the oracles behave identically on the subspace where the adversary's state resides (after applying $C$ ), the adversary cannot distinguish the permutation-based construction from the Haar-random unitary.

5. Significance and Claims

The paper claims that the path-recording oracle provides a powerful, general-purpose tool for quantum query complexity and cryptography. Its significance lies in:

Interpretability: Unlike previous general oracles, it records information in a way that directly corresponds to the algorithm's query history (input-output pairs), facilitating proofs of lower bounds and security.
Unification: It offers a single mathematical framework that explains and generalizes disparate results for functions, permutations, and unitaries.
Simplicity in Cryptography: It enables a simpler proof for the security of pseudorandom unitaries, removing the need for random phases in the construction and relying only on permutations and 2-designs.
Foundational Insight: It clarifies the relationship between the algebraic structure of the commutant algebra and the operational behavior of quantum oracles, showing that "forgetting" information in random sampling corresponds to projecting onto the commutant EPR subspace.

The authors emphasize that their work does not propose new experimental setups but rather provides a rigorous theoretical toolset for analyzing quantum algorithms and cryptographic primitives in the random oracle model.