Random unitaries in extremely low depth

Thomas Schuster; Jonas Haferkamp; Hsin-Yuan Huang

Source-linked AI summary

Random unitaries in extremely low depth

Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang

arXiv:2407.07754v2Jul 10, 2024quant-phcond-mat.str-elcs.CCcs.IT

TL;DR

The paper addresses how random quantum behavior can be generated without the exponential depth required by Haar-random unitaries. It glues local approximate designs or pseudorandom unitaries into global ensembles, obtaining optimal system-size scaling: log-depth designs and polylogarithmic-depth pseudorandom unitaries across circuit geometries. These constructions support applications including efficient classical shadows and quantum hardness results for topological-order recognition.

Problem
Exact Haar-random unitaries require exponential depth, while known approximate-design and pseudorandom-unitary constructions previously required depth polynomial in n.
Method
The paper glues independent local random unitaries on logarithmic-size or polylogarithmic-size patches into a global two-layer brickwork ensemble.
Results
Random circuits achieve approximate unitary designs with depth O~(k) · log(n/ε) on any geometry and pseudorandom unitaries with poly log n depth generally and poly log log n depth all-to-all, with optimal n-dependence.
Takeaways & Limitations
The constructions enable equivalent-accuracy classical shadows with 1D log-depth Clifford circuits and establish quantum hardness for recognizing topological order.
Takeaways & Limitations
The relation between n-, k-, and ε-dependence for unitary-design depth remains unresolved; the construction may not achieve the optimal combined scaling.

Abstract

from arXiv · show

We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $\log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $\text{poly}(\log n)$ depth, and in all-to-all-connected circuits in $\text{poly}(\log \log n)$ depth. In all three cases, the $n$ dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on $\log n$-sized or $\text{poly}(\log n)$-sized patches of qubits to form a global random unitary on all $n$ qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary $k$-designs, and hence also inherit an optimal scaling in $k$. In the case of PRUs, the local unitaries are drawn from existing PRU constructions. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.

1 Introduction

The paper asks how shallow random quantum circuits can reproduce Haar-random behavior, given that exact Haar-random unitaries require exponential depth. It constructs approximate designs and pseudorandom unitaries by gluing random unitaries on logarithmic-size local patches, achieving exponentially lower depth across circuit geometries.

Motivation: Approximate unitary k-designs match Haar-random behavior for experiments making at most k queries, while pseudorandom unitaries match it for efficient quantum experiments.Both notions provide efficient approximations because exact Haar-random unitaries require exponential depth in n.
Motivation: Known constructions of both approximate designs and pseudorandom unitaries previously required depth polynomial in n.
Construction: The construction glues local random unitaries on log n or poly log n qubits into global random unitaries on n qubits.The local ingredients come from existing approximate-design and pseudorandom-unitary constructions.
Main results: Approximate designs achieve depth O~(k) · log(n/ε) on any circuit geometry, while pseudorandom unitaries achieve poly log n depth generally and poly log log n depth with all-to-all connectivity.The n-dependence is optimal in all three settings.
Applications: The results support equivalent-accuracy classical shadows with 1D log-depth Clifford circuits and establish quantum hardness for recognizing topological order.Additional applications include quantum advantages for learning low-complexity dynamics and improved hardness results for random circuit sampling.
Interpretation: Low-depth circuits can reproduce Haar-random behavior despite light-cone and entanglement properties that do not reach Haar-random values at low depth.Those properties are not efficiently measurable in quantum experiments involving the random unitary, so they do not obstruct designs or pseudorandomness.

2 Main Results

The paper builds two-layer brickwork ensembles from independent local random unitaries and proves that logarithmic-size patches suffice to glue local designs or pseudorandom unitaries into global ones. This yields optimal system-size scaling, including log-depth designs and polylogarithmic-depth pseudorandom unitaries under the stated assumptions.

Random unitary designs: The construction partitions a 1D line into local patches and applies independent random unitaries to neighboring patches in a two-layer brickwork circuit.If each local unitary has two-qubit-gate depth d, the full construction has depth 2d.
Random unitary designs: The construction requires each local patch to contain at least logarithmically many qubits in n, k, and ε^-1.This is the key gluing condition for transferring local approximate-design behavior to the full system.
Random unitary designs: An ε-approximate unitary k-design on each 2ξ-qubit patch yields a global ε-approximate k-design when ξ ≥ log2(nk^2/ε).The resulting global circuit has depth 2d when the local circuits have depth d.
Random unitary designs: Existing local design constructions produce global designs with exponentially improved n-dependence, and the n-dependence is optimal for 1D and all-to-all architectures.The lower bound applies to approximate unitary 2-designs and extends to arbitrary ancilla counts.
Pseudorandom unitaries: A local pseudorandom unitary on 2ξ qubits with ξ = ω(log n) glues into an n-qubit pseudorandom unitary secure against polynomial-time quantum adversaries.The construction relies on local pseudorandomness against the relevant adversary class.
Pseudorandom unitaries: Under the conjecture that no subexponential-time quantum algorithm solves LWE, pseudorandom unitaries require poly log n depth in 1D and poly log log n depth in general circuits.These scalings improve exponentially over prior proposals and are optimal by circuit-learning lower bounds.
Comparison between unitary and orthogonal circuits: Orthogonal circuits remain a contrasting limitation: approximate orthogonal 2-designs require linear depth in 1D and logarithmic depth with all-to-all connectivity.The obstruction arises because low-depth real circuits preserve detectable EPR-state structure outside light cones.

3 Applications

The paper applies its shallow random-unitary constructions to classical shadows, topological-order recognition, quantum learning, time-reversal experiments, and random-circuit sampling.

Classical shadows: Log(n)-depth Clifford circuits retain essentially the same classical-shadow sample-complexity guarantees as linear-depth circuits.This addresses experimental noise limitations associated with deep Clifford circuits.
Topological order: Recognizing topological order is quantum computationally hard for depth-ℓ geometrically local circuits when ℓ = Ω(poly log n).The result applies when product and toric-code states represent trivial and non-trivial order preserved by such circuits.
Quantum learning: Shallow circuits with depth poly log n preserve quantum-classical separations for learning low-complexity physical systems.The paper includes distinguishing random unitary processes from depolarizing channels and learning entanglement structure.
Time-reversal learning: Time-reversal experiments can provide exponentially more efficient learning than conventional experiments without time-reversal.The example concerns detecting long-range couplings in a strongly interacting dynamical system.
Random circuit sampling: At depth log n, the construction yields 2D random circuits with anti-concentration and worst-case hardness for random circuit sampling.At depth poly log(n), the output distributions are far from uniform yet computationally indistinguishable from uniform.

4 Proof overview

The proof approximates Haar twirls, converts additive EPR-state error into design error, and repeatedly glues overlapping local designs. It then extends the argument to pseudorandom unitaries and establishes matching depth lower bounds.

Approximate Haar twirl: The approximate Haar twirl replaces Weingarten-matrix analysis with a delta-function approximation when k^2 ≤ 2^n.The relative error is ε = k^2/2^n.
Error conversion: An EPR-state lemma bounds the relative error of an approximate unitary k-design using its additive error relative to the approximate Haar twirl.This supplies the error conversion needed for the construction.
Gluing designs: Two approximate unitary k-designs can be glued into a larger design when their sequentially applied unitaries overlap on at least approximately log(k/ε) qubits.The formal overlap condition includes |B| ≥ log2(2k^2).
Global construction: Applying the gluing lemma from left to right produces an approximate design on all n qubits after repeatedly adding small random unitaries.The same gluing procedure extends the result to 2D circuits and other geometries.
Lower bounds: Low-depth 1D circuits require d = Ω(log n) to reproduce Haar collision probabilities, while all-to-all circuits require d = Ω(log log n).These bounds follow from light-cone growth and establish depth lower bounds for approximate unitary 2-designs.
Pseudorandom unitaries: The pseudorandom-unitary proof compares the local ensemble with a Haar-local ensemble and then compares that ensemble with the n-qubit Haar ensemble.Theorem 1 supplies the second comparison through approximate designs.

5 Discussion

The discussion emphasizes the broad significance of generating random unitaries at extremely low depth while identifying unresolved optimality questions for design constructions and random-gate architectures.

Implications: The construction combines extremely low depth with applications including classical shadows, topological phases, quantum learning, random-circuit output bounds, and time-reversal advantages.These applications span experimental protocols, many-body physics, and quantum information theory.
Open questions: The optimal joint dependence of unitary-design depth on n, k, and ε remains unknown.The paper cannot rule out O(k) + O(log(n/ε)) depth, whereas its construction requires approximately Õ(k) × O(log(n/ε)).
Open questions: It is unresolved whether independently and identically distributed Haar gates on a brickwork architecture achieve the same design depth.The construction currently uses a brickwork circuit with a small subset of gates set to identity.

Appendices

The appendices place the work against prior constructions, detail exponential improvements for designs and pseudorandom unitaries, and develop applications to shadows, topological order, and output distributions.

Unitary designs: Prior unitary-design constructions required depth polynomial or linear in n, whereas this work improves the n-dependence exponentially.The paper attributes the improvement to avoiding extensive light-cones.
Pseudorandom states and unitaries: The construction provides pseudorandom states and unitaries in poly log n depth in 1D and poly log log n depth with all-to-all connectivity.These depths improve exponentially over known constructions.
Pseudorandom states and unitaries: Applying low-depth pseudorandom unitaries to low-entanglement inputs produces pseudorandom states with nearly unchanged entanglement structure.This connects shallow local circuits to pseudoentangled-state behavior.
Classical shadows: The shallow Clifford construction retains classical-shadow guarantees while reducing the required depth from linear to log n.The result resolves conjectures about logarithmic-depth Clifford circuits.
Topological order: Recognizing topological order incurs a super-polynomial overhead for moderately complex quantum states under the paper’s considered approaches.The discussion identifies exponential sample complexity for entropy-based methods and additional difficulty for Wilson-loop and renormalization-group approaches.

A.5 Quantum advantage in learning from experiments

The paper frames quantum advantage in learning as a response to prior separations relying on nonlocal correlations or exponential circuit complexity. It develops learning tasks involving geometrically local systems and strengthens time-reversal-based separations against experiments with quantum memory.

Motivation: Prior quantum-learning separations considered physical systems with highly nonlocal correlations across all n qubits.The paper identifies this as unlike many physical settings with much shorter correlation lengths.
Motivation: Existing separations also included systems with exponential circuit complexity, unlike the low-complexity systems targeted here.The paper contrasts those settings with depth poly log n.
Quantum advantage: The paper establishes a superpolynomial quantum-classical learning separation for geometrically local systems with correlation length poly log n and depth poly log n.This is presented as the first such separation for these locality and complexity conditions.
Time reversal: A prior time-reversal learning task had an exponential sample-complexity advantage but could be efficiently solved without time reversal when quantum memory was available.The limitation motivates a stronger task in the present work.
Time reversal: The new task cannot be solved by any quantum experiment querying U, including experiments with arbitrarily large quantum memories.It builds on physical intuition that time reversal can reveal new many-body properties.
Operational meaning: Lemma 6 shows that relative error for U^⊗k implies indistinguishability for adaptive quantum algorithms making k queries to U.The proof converts adaptive queries into one parallel query using Bell states, ancillas, and Bell projections.

B.3.2 Bounding the relative error with respect to the approximate Haar twirl

This section derives relative-error control for the approximate Haar twirl and uses it to glue local approximate designs into larger designs. The construction propagates local errors under a dimension condition and then bounds the resulting global error.

Relative error: Lemma 7 bounds the relative error between an ensemble twirl and an approximate Haar twirl using the additive error on an EPR state.The bound applies the relative-error comparison first to the EPR state and then to arbitrary states.
Relative error: The EPR-state relative error upper-bounds the relative error on every input state.The proof expresses the twirl of an arbitrary state through the EPR representation.
Relative error: Combining Lemma 7 with Lemma 1 yields Lemma 2, which bounds the relative error between the ensemble twirl and the Haar twirl.This establishes that the ensemble forms a unitary design under the stated error bound.
Gluing designs: Gluing two approximate designs on overlapping subsystems produces an approximate design on their union when k^2 ≤ D_B/2.The resulting error depends on the two local errors and dimension-dependent correction factors.
Gluing designs: Applying the gluing lemma patch-by-patch bounds the error of the two-layer brickwork ensemble by composing the local approximate designs.The proof then verifies that the resulting bound is at most ε under its parameter assumptions.

B.4 Proof of Corollary 1: Low-depth random unitary designs

The corollary inserts existing local design constructions into the paper’s patch-gluing framework. This yields low-depth approximate designs in 1D and all-to-all architectures, including especially short-depth constructions for Clifford-based designs.

Construction: The construction improves the n-dependence of random-unitary design depth exponentially compared with existing constructions.It does so by inserting existing designs into small random unitaries on local patches.
1D designs: 1D circuits achieve ε-approximate k-designs in depth O(log(n/ε) · k poly log(k)).This follows by using 1D local random circuits on 2ξ-qubit patches and setting ξ = log^2(nk^2/ε).
All-to-all designs: All-to-all circuits achieve ε-approximate 2- and 3-designs in depth O(log log(n/ε)) using O(n log(n/ε)) ancilla qubits.The local unitaries are random Clifford unitaries implementing exact 2- and 3-designs on the patches.
Clifford designs: For 1D circuits, Clifford constructions provide exact 3-designs on patches and yield ε-approximate 3-designs over n qubits at logarithmic depth.The section identifies this construction as particularly useful for classical shadow tomography.
Alternative constructions: An alternative local design construction has depth nearly quadratic in k and nearly linear in log(n).The stated scaling comes from inserting the explicit-constant construction into the gluing theorem.

B.5 Proof of Proposition 1: Lower bounds for unitary designs

The proposition lower-bounds the depth needed for unitary designs by analyzing collision probabilities after random product-basis measurements. Light-cone growth limits the attainable collision behavior in shallow circuits.

Collision analysis: The proof evaluates outputs of a random unitary applied to |0^n⟩ and measured in a random product basis.It averages the collision probability over both the unitary ensemble and the measurement basis.
Collision analysis: Random-basis averaging damps each Pauli contribution by 3^-ℓ, where ℓ is the Pauli weight.The damping equals the probability that the Pauli commutes with the random measurement basis.
Light cones: In 1D and all-to-all circuits, the light-cone contains at most 2d qubits after depth d.The proof uses this support bound to restrict the evolved stabilizer weights.
Lower bound: For an ε-approximate 2-design, the collision requirement is n/3^L ≤ 1 + 2ε.Here L denotes the light-cone size controlling the relevant stabilizer contribution.
Lower bound: The resulting depth lower bounds differ between 1D and all-to-all circuit architectures.The proposition states separate bounds for the two geometries after applying the light-cone constraint.

B.6 Additional lower bounds for the 𝜀-dependence of low-depth unitary designs

The paper proves lower bounds on the error dependence of low-depth unitary designs, showing logarithmic dependence in 1D and doubly logarithmic dependence for all-to-all circuits. These bounds apply while the circuit light-cone remains smaller than the system size.

The ε-dependence lower bounds are optimal for arbitrary circuit ensembles, extending earlier results restricted to independently Haar-random local gates.The paper explicitly frames this as an additional lower bound motivated by prior work.
The lower bound applies only when the circuit light-cone is smaller than the system size.This restriction is necessary because exact Clifford 3-designs exist and can be compiled in O(n) depth in 1D or O(log n) depth all-to-all.
The proof prepares one qubit in |0⟩ and the others maximally mixed, applies the circuit, and uses a SWAP test on its light-cone.The comparison is between the resulting purity signal and the Haar-random expectation, whose difference yields the depth constraint.
Ω(log(1/ε)) depth is necessary for ε-approximate 2-designs in 1D circuits under the stated low-depth regime.The bound allows arbitrary ancilla qubits and assumes depth d≤n/4.
Ω(log log(1/ε)) depth is necessary for ε-approximate 2-designs in all-to-all circuits under the stated low-depth regime.The bound assumes depth d≤log2(n/2) and a common circuit architecture across the ensemble.

C.4 Proof of Theorem 2: Gluing small pseudorandom unitaries

The proof establishes pseudorandomness by gluing small pseudorandom unitaries in a two-layer brickwork circuit and comparing the result to Haar randomness through hybrid and design arguments. With logarithmic-size patches, this yields polylogarithmic-depth constructions under the LWE assumption.

ω(log n)-qubit local patches suffice to glue small pseudorandom unitaries into an n-qubit pseudorandom unitary.The resulting brickwork ensemble is secure against polynomial-time adversaries.
The proof uses a hybrid sequence replacing local pseudorandom unitaries one at a time with Haar-random unitaries.It separately shows indistinguishability between the original and hybrid ensembles, and between the final hybrid and Haar randomness.
Polynomial-time algorithms have negligible distinguishing advantage between the Haar-based brickwork ensemble and Haar-random unitaries.The argument selects superpolynomially large design order and negligible approximation error when patch size is ω(log n).
The glued ensemble is efficiently implementable because its local pseudorandom unitaries are efficiently implementable.Combining this with the hybrid argument establishes security against polynomial-time adversaries.
Assuming subexponential-time quantum algorithms cannot solve LWE, pseudorandom unitaries are achieved in poly log n depth in 1D and poly log log n depth all-to-all.The construction uses local patches of size (log n)^(1+c) for any constant c>0.
The line-based construction extends to any geometry with only O(d) depth overhead.The extension uses Hamiltonian paths with jumps and constant-depth simulation of distance-four-neighborhood layers.

D.2 Extension of Theorem 1 to general two-layer circuits

The paper extends the design-gluing theorem from brickwork circuits to general two-layer circuits whose overlap graph is connected. A logarithmic patch-overlap condition controls the resulting approximation error.

A connected overlap graph lets general two-layer circuits glue local ε-approximate unitary k-designs into a global ε-approximate unitary k-design.Every qubit must be acted on by at least one local unitary.
ξ≥log2(2nk^2/ε) is sufficient for the generalized gluing theorem when ε≤1.Here ξ is the minimum overlap between a first-layer and second-layer unitary connected in the overlap graph.
The proof applies the gluing lemma along a spanning tree of the overlap graph.The applications proceed in order of edge depth, extending the design across the connected circuit structure.
The total approximation error remains at most ε after summing the contributions from the tree-edge applications.The analysis uses the condition n≥(m−1)ξ together with the stated bounds on k, q, and ε.

E.1 Classical shadows with 1D log-depth Clifford circuits

The paper replaces deep random Clifford circuits in classical shadows with low-depth approximate designs. For low-rank observables, the resulting log-depth estimates have essentially the same performance as those using linear-depth random Clifford circuits.

Linear-depth random Clifford circuits are a near-term obstacle because accumulated experimental errors can make shadow-estimation fidelity decay exponentially with depth.This motivates lower-depth implementations of classical shadows.
Replacing exact random Clifford unitaries with ε-approximate unitary 3-designs reduces the depth from linear in n to logarithmic in n.The construction provides such low-depth random Clifford circuits.
Approximate designs can introduce a small estimation bias because the exact-design inverse map only approximately inverts the approximate twirl.The bias can be reduced by decreasing ε, while an exact inverse map may not be efficiently findable.
Theorem 7 gives a variance guarantee for estimating any positive observable using an ε-approximate unitary 3-design.The associated circuit depths are O(log(n/ε)) in 1D and O(log log(n/ε)) all-to-all.
For low-rank observables, ε-dependent variance terms are sub-leading relative to the variance already present with deep random Clifford unitaries.Thus log-depth and linear-depth random Clifford circuits have essentially equivalent classical-shadow performance in this regime.

E.2 Proof of Corollary 3: Quantum hardness of recognizing topological order

The paper shows that recognizing topological order is quantum computationally hard, using low-depth pseudorandom circuits to create states with different orders that efficient quantum algorithms cannot distinguish. These constructions preserve key topological properties of representative states up to small sub-leading terms.

Rigorous results on efficiently recognizing topological order were previously lacking despite extensive heuristic approaches.
Low-depth pseudorandom unitaries create pseudorandom states within any topological-order class by acting on representative states.The construction uses invariance of topological order under low-depth geometrically local circuits.
States from trivial and non-trivial topological-order ensembles cannot be distinguished by polynomial-time quantum algorithms, making recognition quantum computationally hard.The ensembles are individually indistinguishable from Haar-random states and therefore from each other.
The constructed pseudorandom toric-code states retain (√n/2 − 4√2ξ, 0)-topological order, differing from toric-code states by a small sub-leading term.
The pseudorandom toric-code states cannot be mapped to product states by local circuits of depth less than √n/4 − 2√2ξ.This matches the toric-code bound up to a small sub-leading term.
The framework also supports superpolynomial quantum advantages for learning low-complexity physical systems.Replacing Haar-random states with geometrically local poly(log n)-depth pseudorandom states preserves the separation between classical and quantum agents.

E.5 Output distributions of shallow quantum circuits

The paper analyzes output distributions generated by shallow local random circuits and shows that logarithmic-depth circuits can be far from uniform while remaining computationally indistinguishable from uniform under cryptographic assumptions. The proof combines approximate-design constructions with pseudorandom-unitary constructions.

The motivation is that output distributions must be sufficiently far from uniform to resist being mimicked by uniform sampling.
Output distributions of local random circuits with depth Ω(log n) are far from uniform with probability approaching one.This holds on any circuit geometry.
Under the assumption that no quantum algorithm solves LWE in subexponential time, poly(log n)-depth local circuits are indistinguishable from uniform using only sampled bitstrings.
The proof uses low-depth approximate unitary designs for far-from-uniformity and low-depth pseudorandom unitaries for computational indistinguishability.
A combined circuit formed by composing pseudorandom and design circuits has poly(log n) depth and is both pseudorandom and an approximate unitary k-design for k = O(1).
For Haar-random output distributions, polynomially many samples cannot distinguish them from uniform with more than negligible probability.