We study random constant-depth quantum circuits in a two-dimensional (2D) architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this (MIE) proliferates when the circuit depth is at least a constant critical value d ∗ . For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a in the classical hardness of sampling from the output distribution. Here, we provide evidence for a quantum advantage phase transition in the setting of random circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth- d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O ( d ) . Finally, we introduce a 2D depth- 2 “coarse-grained” circuit architecture, composed of random Clifford gates acting on O ( log ( n ) ) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage.
We study random constant-depth quantum circuits in a two-dimensional (2D) architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this (MIE) proliferates when the circuit depth is at least a constant critical value d ∗ . For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a in the classical hardness of sampling from the output distribution. Here, we provide evidence for a quantum advantage phase transition in the setting of random circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth- d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O ( d ) . Finally, we introduce a 2D depth- 2 “coarse-grained” circuit architecture, composed of random Clifford gates acting on O ( log ( n ) ) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage.
We study measurement-induced entanglement (MIE) generated by column-by-column sampling of noisy 2D random circuits of size N and depth T . Focusing primarily on Clifford circuits and using the operator entanglement S op of the sampling-induced boundary state as a proxy for computational complexity, first, we reproduce in the noiseless limit a finite-depth transition from area- to volume-law scaling at a threshold depth T c = 6 . In contrast, in the presence of single-qubit depolarizing noise at any constant rate p > 0 , we find that the operator entanglement S op obeys an area law, with its maximum value scaling approximately linearly with T / p in the regime T > T c . By analyzing the spatial distribution of stabilizer generators, we observe exponential localization of stabilizer generators; these both account for the scaling of the maximal S op and imply an exponential decay of conditional mutual information across buffered tripartitions, which we also confirm numerically. Together, these results indicate that constant local noise destroys long-range MIE in 2D random Clifford circuits, and that a tensor-network-based algorithm can efficiently sample from noisy 2D random Clifford circuits (i) at sub-logarithmic depths T = o ( log N ) for any constant noise rate p = Ω ( 1 ) , and (ii) at constant depths T = O ( 1 ) for noise rates p = Ω ( log − 1 N ) . Finally, we turn to depth T = 4 Haar-random and measurement-based quantum computing-type circuits, providing evidence that MIE in noisy 2D Haar-random circuits exhibits the same qualitative behavior as in random Clifford circuits, and that noise destroys the volume-law scaling of MIE in non-Clifford circuits.
The output state of a 2D geometrically local shallow random quantum circuit does not have long range correlations due to its lightcone structure. But this changes if one measures a subset of the qubits: long-range entanglement can be induced by the measurement process, leading to conditional correlations between distant qubits. In this paper we investigate the structure of conditional dependence in these circuits and its consequences for quantum advantage. For a tripartition ABC of the qubits, we consider the ensemble of post-measurement states on A that is conditioned on a specific measurement outcome on B and ranges over all possible measurement outcomes on C. For circuit depths exceeding a constant critical value d∗, we conjecture that this ensemble is well approximated by a certain generalization of the Haar ensemble, called the Scrooge ensemble~[Jozsa \textit{et al.}, \href{https://doi.org/10.1103/PhysRevA.49.668}{Phys. Rev. A \textbf{49}, 668 (1994)}]; we also provide supporting numerical and analytical evidence. Our conjecture describes a precise sense in which the state retains its lightcone structure on the remaining unmeasured qubits, but also develops some globally random features arising from the measurement. A consequence is that n-qubit shallow random quantum circuits in two dimensions are classically efficiently simulable in the presence of a tiny depolarizing noise rate Ω(log(n)/n).
We analyze the entanglement structure of states generated by random constant-depth two-dimensional quantum circuits, followed by projective measurements of a subset of sites. By deriving a rigorous lower bound on the average entanglement entropy of such postmeasurement states, we prove that macroscopic long-ranged entanglement is generated above some constant critical depth in several natural classes of circuit architectures, which include brickwork circuits and random holographic tensor networks. This behavior had been conjectured based on previous works, which utilize nonrigorous methods such as replica theory calculations, or work in regimes where the local Hilbert space dimension grows with system size. To establish our lower bound, we develop new replica-free theoretical techniques that leverage tools from multiuser quantum information theory, which are of independent interest, allowing us to map the problem onto a statistical mechanics model of self-avoiding walks without requiring large local Hilbert space dimension. Our findings have consequences for the complexity of classically simulating sampling from random shallow circuits and of contracting tensor networks. First, we show that standard algorithms based on matrix product states which are used for both these tasks will fail above some constant depth and bond dimension, respectively. In addition, we also prove that these random constant-depth quantum circuits cannot be simulated by any classical circuit of sublogarithmic depth.
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
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.