Non-Haar random circuits form unitary designs as fast as Haar random circuits

This paper proves that general non-Haar random circuits form unitary designs at rates comparable to Haar random circuits, with required depths upper-bounded by a constant factor independent of system size across diverse architectures, thereby enabling more flexible and robust randomness generation for quantum applications.

The Gist

The Big Picture: Shuffling a Deck of Cards

Imagine you have a deck of cards (representing a quantum system). You want to shuffle it so thoroughly that the order is completely random, like if you had picked a card arrangement out of a hat containing every possible order in the universe. In physics, this "perfect randomness" is called a Haar random state.

However, creating a perfect random shuffle takes an impossible amount of time and effort for a large deck. Instead, scientists are happy with a "good enough" shuffle. They call this a Unitary Design. It's a shuffle that looks random enough for any test you might run on it, even if it's not mathematically perfect.

For a long time, researchers knew exactly how many shuffles (circuit depth) it took to get a "good enough" shuffle if you used a perfect randomizer (like a truly fair, continuous spinner to decide which cards to swap). This is the "Haar random" scenario.

The Problem: In real-world experiments, we can't use perfect spinners. We are forced to use imperfect, discrete tools (like a standard deck of cards where you can only swap specific pairs, or a digital random number generator with limited options). The big question was: Does using these "imperfect" tools make the shuffling process take much longer? Do we need to shuffle way more times to get the same result?

The Discovery: The "Imperfect" Tools Are Just as Fast

This paper proves a surprising and comforting fact: No, you don't need to shuffle much longer.

The authors show that even if you use "imperfect" local randomizers (non-Haar circuits), you can still create a "good enough" random state in essentially the same amount of time as if you were using perfect tools. The only difference is a tiny, constant multiplier (like needing 2 or 3 extra shuffles instead of 1), but this number does not grow as your system gets bigger.

If you have a small system or a massive system, the "penalty" for using imperfect tools stays the same.

The Three Types of "Shuffling Machines"

The researchers tested this idea on three different ways of organizing the shuffling process, proving it works for all of them:

1. The Single-Layer Mixer (Single-layer-connected):

   • Analogy: Imagine a row of people holding hands. In one round, you randomly pick one pair of neighbors to swap places. Then you pick another pair.
   • Result: Even if the rule for picking the pair isn't perfectly random, the whole line gets shuffled just as fast as if it were.

2. The Brickwork Mixer (Multilayer-connected):

   • Analogy: Think of a brick wall. You can't swap every brick at once because they are stacked. You have to swap bricks in one layer, then the next layer, like laying bricks in a pattern.
   • Result: This is harder to analyze because the layers depend on each other. The authors developed a new mathematical "glue" to prove that even with these fixed, rigid patterns, imperfect tools work just as fast as perfect ones.

3. The Patchwork Quilt (Patchwork circuit):

   • Analogy: Imagine you have a giant quilt. Instead of shuffling the whole thing at once, you make many small, perfectly shuffled squares (patches) and sew them together.
   • Result: This is the fastest method (very shallow depth). The paper proves that even if the small squares are made with "imperfect" tools, the whole quilt still becomes random incredibly fast.

Why This Matters (According to the Paper)

The authors highlight three specific areas where this finding is useful, based strictly on their text:

• Real-World Experiments: In actual quantum computers, we often make small mistakes (coherent errors) or are limited to specific sets of gates (discrete sets). This paper says: "Don't worry." Your experiment will still generate global randomness at the same speed as the ideal theory predicts, even with these flaws.
• Randomized Benchmarking: This is a test used to check if a quantum computer is working correctly. The paper suggests this test is more flexible than we thought; you can use different, imperfect gate sets without ruining the test's speed or accuracy.
• Random Circuit Sampling: This is a task used to prove "Quantum Advantage" (showing a quantum computer is faster than a classical one). The paper confirms that even with imperfect local gates, these circuits still produce the necessary "anti-concentration" (a specific type of randomness) very quickly, validating real-world quantum supremacy experiments.

The Bottom Line

Think of the "Haar random" circuit as a master chef using a perfect, infinite set of spices to make a soup. The "Non-Haar" circuit is a home cook using a limited spice rack.

This paper proves that the home cook can make a soup that tastes just as "random" and complex as the master chef's, and they can do it in the same amount of time. The only difference is the home cook might need to stir the pot a few extra times (a constant factor), but that extra effort doesn't get worse just because the pot gets bigger.

This gives scientists confidence that they can build robust, fast, and flexible quantum systems using the imperfect tools they actually have in the lab, without waiting forever for the results to "randomize."

Technical Summary

Technical Summary: Non-Haar Random Circuits Form Unitary Designs as Fast as Haar Random Circuits

Problem Statement
Random quantum circuits are fundamental tools for quantum information processing (e.g., randomized benchmarking, quantum tomography) and models for nonequilibrium many-body dynamics. A central metric in this field is the rate at which a circuit generates global randomness, quantified by its ability to form a unitary $t$-design. While it is well-established that Haar-random circuits (where gates are sampled from the Haar measure) form $t$-designs in polynomial depth ($\text{poly}(N)$), and even logarithmic depth ($O(\log N)$) in specific geometries, the behavior of non-Haar random circuits remains less understood.

In experimental settings, gates are typically chosen from discrete, non-Haar sets (e.g., Clifford+$T$). Previous works addressing non-Haar ensembles provided depth upper bounds that were loose by factors of $\text{poly}(N)$ or were restricted to specific circuit structures (excluding fixed architectures like brickwork circuits). The critical open question addressed in this work is whether the circuit depth required to form a unitary $t$-design in general non-Haar random circuits is comparable to that of the corresponding Haar-random circuits, independent of the system size $N$.

Methodology
The authors analyze the formation of unitary $t$-designs by classifying circuit structures into three categories and developing specific proof techniques for each. The core of their methodology relies on bounding the spectral gap ($\Delta^{(t)}_\nu$) of the moment operator, which dictates the convergence rate to the Haar measure.

1. Single-Layer-Connected Circuits: In these circuits (e.g., 1D local random circuits), the two-qudit gates in a single layer form a connected graph covering all sites. The authors relate the spectral gap of a non-Haar ensemble $\nu$ to that of the corresponding Haar ensemble $\nu_H$. They derive a lower bound for the non-Haar spectral gap using the Cauchy-Schwarz inequality and properties of the moment operator's residual part. This improves upon previous bounds by eliminating loose $\text{poly}(N)$ factors.
2. Multilayer-Connected Circuits: For fixed architectures (e.g., 1D brickwork circuits) where a single layer does not connect all sites, the spectral gap must be evaluated over a block of multiple layers. The standard "detectability lemma," used for Haar circuits, is not directly applicable to non-Haar ensembles. The authors extend the applicability of this lemma to non-Haar circuits by deriving a generalized inequality that relates the spectral gap of a non-Haar multilayer block to the spectral gap of the corresponding Haar block, scaled by the local spectral gaps of the constituent gates.
3. Patchwork Circuits: These are special geometries constructed by gluing small patches of random circuits. The authors leverage a lemma from prior work (Schuster et al.) which states that if small patches form approximate designs, the global system does as well. They demonstrate that the depth required for each patch in a non-Haar setting is simply a constant factor larger than the Haar depth, determined by the local spectral gap.

Key Contributions and Results
The paper proves that for a wide range of circuit structures, the circuit depth $L$ required for a general non-Haar random circuit to form an $\epsilon$-approximate unitary $t$-design is upper bounded by the depth $L_H$ of the corresponding Haar-random circuit, up to a constant prefactor independent of the system size $N$.

• Single-Layer-Connected Circuits: The required depth is $L = 2(\Delta^{(t)}_{\text{loc},\nu})^{-1} L_H$, where $\Delta^{(t)}_{\text{loc},\nu}$ is the minimum spectral gap of the local two-qudit ensembles.
• Multilayer-Connected Circuits: For a fixed architecture with connection depth $l$, the required depth is $L_A = (\Delta^{(t)}_{\text{loc},\nu_A})^{-l} L^H_A$.
• Patchwork Circuits: The $O(\log N)$ depth formation achievable with Haar circuits is preserved for non-Haar circuits, with the depth scaled by a constant factor dependent on the local spectral gap.

Crucially, the prefactor depends solely on the "randomness strength" of the local two-qudit unitary ensembles (specifically, the inverse of their spectral gap). If the local ensembles contain a universal gate set (along with the identity operator), this prefactor scales at most as $\text{polylog}(t)$, indicating that the formation depth is insensitive to the specific choice of local randomizers in both $N$ and $t$.

Significance and Implications
The authors claim that their work establishes the robustness of global randomness generation rates against local gate deformations. The results imply that:

1. Experimental Flexibility: Real-world experiments using discrete gate sets can achieve unitary designs with the same depth scaling as idealized Haar-random circuits, ensuring that protocols like randomized benchmarking and random circuit sampling remain efficient even with non-Haar local gates.
2. Universality of Chaotic Phenomena: Since unitary design formation is linked to quantum chaos phenomena (information scrambling, complexity growth, thermalization), these phenomena are shown to emerge universally at the same circuit depth order, regardless of whether the local randomizers are Haar or non-Haar.
3. Anticoncentration: The results confirm that anticoncentration, a necessary condition for demonstrating quantum advantage in random circuit sampling, occurs in $O(\log N)$-depth non-Haar random circuits (specifically patchwork circuits).

The paper concludes that these findings lay a foundation for flexible randomness generation in quantum many-body systems and open avenues for future research into bosonic/fermionic systems and symmetry-constrained dynamics.