Apparent Universal Behavior in Second Moments of Random Quantum Circuits

Technical Summary: Apparent Universal Behavior in 2nd Moments of Random Quantum Circuits

Problem Statement
The convergence of random quantum circuit ensembles to approximate unitary designs is a central topic in quantum information theory, governing the large-depth behavior of experimentally observable properties. While it is known that certain structured architectures (e.g., censored brickworks) form $\epsilon$-approximate $t$-designs in depth $\Theta(\log n)$, the behavior of more generic, regularly-connected architectures remains less understood. Key open questions include:

1. How fast do standard "brickwork" circuits form approximate 2-designs, and does this differ from anticoncentration?
2. Do all graph-sampled architectures form 2-designs at the same asymptotic rate, or do specific topologies (e.g., those with poor connectivity) require significantly more gates?
3. What is the optimal experimental setup to distinguish a given ensemble from the Haar measure, and does the collision probability (a proxy for anticoncentration) always dictate the convergence rate?

Previous work often relied on loose upper or lower bounds derived from spectral gaps or specific circuit properties, lacking exact numerical evaluations for moderate system sizes.

Methodology
The authors introduce a strategy to explicitly determine the optimal experiment that distinguishes any given ensemble from the Haar measure, specifically for the second moment ($t=2$).

• Theoretical Reduction: They prove (Theorem 1) that for locally invariant ensembles with positive-semidefinite (PSD) vectorization, the multiplicative error $M(\Phi_\epsilon, \Phi_{Haar})$ is saturated by a specific set of states $\rho_{\vec{a}}$. These states are tensor products of singlet states ($|01\rangle - |10\rangle$) and product states ($|00\rangle$) across the $n$ sites, parameterized by a binary vector $\vec{a} \in \{0, 1\}^n$.
• Computational Algorithm: This reduction transforms the problem of finding the multiplicative error into maximizing a function over a finite set of $2^n$ possibilities. The authors express the moment operator in a permutation basis (via Schur-Weyl duality) and use tensor network methods to compute the matrix elements $v(\vec{a})^T H v(\vec{a})$ exactly. This approach reduces the computational complexity from a naive $64^n$ to $4^n$ (or $2^n$ with symmetries), enabling exact calculations for systems up to 50 qubits.
• Architectures Studied: The study covers:
  • Graph-sampled architectures (linear, circle, complete, lollipop, star, Ramanujan, hourglass, bridge).
  • 1D brickwork circuits (open and periodic boundary conditions).
  • "Fast" architectures including Parallel Complete Graph (PCG), Permuted Brickwork (PB), and Permuted Brickwork with Fixed Evens (PBFE).

Key Contributions and Results

1. Exact Multiplicative Error Calculation: The paper provides the first usable algorithm to compute the exact multiplicative error for $t=2$ in modest system sizes, moving beyond loose bounds.
2. Graph-Dependent Scrambling Rates:
   • Universal Bounds: Most graph families (linear, circle, trees, Ramanujan) form $\epsilon$-approximate 2-designs in depth proportional to $\log n$.
   • Exceptions: The authors identify specific "exceptional" architectures, such as the lollipop and bridge graphs, which require depth $\Omega(n)$ (specifically $\Omega(n^2 \log n)$ for lollipops). This answers a question from Ref. [1] in the negative, proving that not all graphs form 2-designs at the same rate.
   • Connectivity Mechanism: The slow scrambling in exceptional cases is attributed to poor connectedness, creating a separation of timescales (e.g., a "stick" in the lollipop graph thermalizes much slower than the "candy"). The authors conjecture that the linear graph is the slowest in terms of connections required, while the complete graph is the fastest in terms of total gates.
3. Brickwork Circuits:
   • For 1D brickworks, the authors derive a semi-empirical formula for the depth $d_{brickwork}$ required to reach an $\epsilon$-approximate 2-design:
     $$d_{brickwork} \approx \frac{\log(\frac{3}{\pi^2} \frac{n}{\epsilon})}{\log(5/4)} + O\left(\frac{1}{n^2}\right)$$
   • They identify that the optimal experiment for open-boundary brickworks is the "entangled boundaries" state (singlets at the ends, product states in the bulk), which converges slower than the collision probability.
4. Fast Architectures:
   • The Permuted Brickwork (PB) and PBFE architectures are shown to scramble significantly faster than graph-sampled architectures.
   • The PBFE architecture constructs an 0.01-approximate 2-design on 50 qubits with only 12 layers, suggesting the required depth is nearly independent of qubit count for these specific constructions.
   • The Parallel Complete Graph (PCG), previously suggested as the fastest anticoncentrator, is shown not to be the absolute fastest scrambler, though it is faster than any graph-sampled architecture.
5. Anticoncentration vs. 2-Designs:
   • While anticoncentration (collision probability) and 2-design formation are closely related, they are not always equivalent.
   • For the star graph, the collision probability converges much faster than the multiplicative error, demonstrating that the "optimal experiment" is not always the collision probability.
   • For 1D brickworks with open boundaries, a gap exists between the depth required for anticoncentration and the depth required for a 2-design, whereas they coincide for periodic boundaries.

Significance and Claims
The paper claims to provide a comprehensive numerical characterization of second moments in random quantum circuits, offering "everything you always wanted to know... but were too afraid to compute."

• Practical Depth: The results suggest that for realistic parameter ranges, only 10–20 layers are needed to construct an approximate 2-design for many architectures, representing a large constant-factor improvement over previous constructions.
• Connectivity Limits: The work establishes that while graph geometry influences scrambling rates, the primary bottleneck is connectedness. The authors conjecture that the linear and complete graphs represent the extremal bounds for connection counts and gate counts, respectively.
• Theoretical Limits: The paper modestly notes that while their numerical results are exact for finite $n$, they are "strongly suggestive" rather than formal proofs for $n \to \infty$. However, they provide the first rigorous proof that certain graph families (bridge/lollipop) require $\Omega(n)$ gates, refuting the idea of a universal asymptotic form for all graphs.
• Anticoncentration Gap: The authors highlight that results linking anticoncentration to state 2-designs (Ref. [15]) do not straightforwardly extend to unitary designs, as the ratio between collisional and multiplicative errors can grow arbitrarily large depending on the architecture.

The paper concludes by suggesting future directions, including extending the algorithm to $t > 2$, exploring other groups, and investigating whether simpler graph properties (like min-cut ratios) can replace the complex connectedness measures used here.