We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anticoncentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes.An understanding of the conditions for anticoncentration is important for determining which quantum circuits are difficult to simulate classically, as anticoncentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation.Our definition of anticoncentration is that the expected collision probability of the distribution-that is, the probability that two independently drawn outcomes will agree-is only a constant factor larger than the collision probability for the uniform distribution.We show that when the two-local gates are each drawn from the Haar measure (or any 2-design), at least (n log(n)) gates (and thus (log(n)) circuit depth) are needed for this condition to be met on an n-qudit circuit.In both the case where the gates are nearest neighbor on a one-dimensional ring and the case where gates are long range, we show that O(n log(n)) gates are also sufficient and we precisely compute the optimal constant prefactor for the n log(n).The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical-mechanical model, which we manage to bound using stochastic and combinatorial techniques.
We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anticoncentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes.An understanding of the conditions for anticoncentration is important for determining which quantum circuits are difficult to simulate classically, as anticoncentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation.Our definition of anticoncentration is that the expected collision probability of the distribution-that is, the probability that two independently drawn outcomes will agree-is only a constant factor larger than the collision probability for the uniform distribution.We show that when the two-local gates are each drawn from the Haar measure (or any 2-design), at least (n log(n)) gates (and thus (log(n)) circuit depth) are needed for this condition to be met on an n-qudit circuit.In both the case where the gates are nearest neighbor on a one-dimensional ring and the case where gates are long range, we show that O(n log(n)) gates are also sufficient and we precisely compute the optimal constant prefactor for the n log(n).The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical-mechanical model, which we manage to bound using stochastic and combinatorial techniques.
Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary?
We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of logn/log(9/4)≈0.855log2n layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness.
At a larger logarithmic depth, we prove, in the real-RAM model, average-case #P-hardness of estimating output probabilities to additive error 2−O(nlog2n) on any fixed fraction of instances above 3/4. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite 192-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and O(nlogn) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N scale, where N=(n/2n), required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
Anticoncentrated n-bit distribution from log(n) qubits
Random circuit sampling (RCS) is a leading approach to demonstrate quantum advantage, with its believed classical hardness rooted in anticoncentration of output distributions and average-case hardness of probability estimation. Here we show that this association is not fundamental. We introduce holographic random circuit sampling (HRCS), a spatiotemporal protocol that interleaves random unitary evolution with mid-circuit measurements. We prove that n classical bits exhibiting ε-approximate anticoncentration of Haar random states can be generated using only O(logn) physical qubits and linear depth, establishing a precise space-time trade-off and indicating efficient classical simulation. Our analyses is built upon exact formulas for collision probability and higher-order power sums. Our experimental validation on IBM Quantum devices demonstrates sampling up to 200 classical bits using only 20 qubits.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
We give an efficient algorithm for learning k-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying U to the all-zero input. For a depth-d circuit on n sites with random 2ℓ-qubit gates, the algorithm learns the original circuit U with high probability in poly(n,2ℓd) time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as ℓd=O(logn). In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require ℓd=ω(logn), and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same ℓd=ω(logn) scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting.
The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.
Abstract We prove that poly(t)⋅n1/D poly ( t ) · n 1 / D -depth local random quantum circuits with two qudit nearest-neighbor gates on a D -dimensional lattice with n qudits are approximate t -designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was poly(t)⋅n poly ( t ) · n due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for D=1 D = 1 . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ( PH PH ) is infinite and that certain counting problems are #P # P -hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that O(n) O ( n ) depth suffices for anti-concentration. The proof is based on a previous construction of t -designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size O(nln2n) O ( n ln 2 n ) corresponding to depth O(ln3n) O ( ln 3 n ) . We also show a lower bound of Ω(nlnn) Ω ( n ln n )
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0, the distribution corresponding to circuits of depth O(n2m+1log(n)) is at most O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.