Quantum advantage schemes probe the boundary between classically simulatable and classically intractable quantum dynamics. We explore the impact of midcircuit measurements on the computational power of quantum circuits. To this effect, we focus on quantum sampling and introduce a constant-depth measurement-driven approach for efficiently sampling from a broad class of commuting diagonal quantum circuits and associated structured phase states, previously requiring polynomial-depth unitary circuits. By interleaving midcircuit measurements with feedforward in randomized "fan-out staircases," our dynamical circuits bypass Lieb-Robinson light-cone constraints, enabling global entanglement with flexible auxiliary qubit usage on bounded-degree lattices (e.g., two-dimensional grids). The generated phase states exhibit random-matrix statistics and anticoncentration comparable to fully random architectures. We further demonstrate measurement-driven feature maps that distinguish phases of an extended Su-Schrieffer-Heeger model from random eigenstates in a quantum machine-learning benchmark (reservoir computing). Technologically, our results harness midcircuit measurements to realize quantum advantages on bounded-degree hardware with a favorable topology. Conceptually, they provide complexity-theoretic support for quantum speedups by midcircuit measurements.
Quantum advantage schemes probe the boundary between classically simulatable and classically intractable quantum dynamics. We explore the impact of midcircuit measurements on the computational power of quantum circuits. To this effect, we focus on quantum sampling and introduce a constant-depth measurement-driven approach for efficiently sampling from a broad class of commuting diagonal quantum circuits and associated structured phase states, previously requiring polynomial-depth unitary circuits. By interleaving midcircuit measurements with feedforward in randomized "fan-out staircases," our dynamical circuits bypass Lieb-Robinson light-cone constraints, enabling global entanglement with flexible auxiliary qubit usage on bounded-degree lattices (e.g., two-dimensional grids). The generated phase states exhibit random-matrix statistics and anticoncentration comparable to fully random architectures. We further demonstrate measurement-driven feature maps that distinguish phases of an extended Su-Schrieffer-Heeger model from random eigenstates in a quantum machine-learning benchmark (reservoir computing). Technologically, our results harness midcircuit measurements to realize quantum advantages on bounded-degree hardware with a favorable topology. Conceptually, they provide complexity-theoretic support for quantum speedups by midcircuit measurements.
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.
Quantum advantage is widely expected to require sufficiently deep circuits, where correlations and global computational structure can grow beyond the reach of efficient classical simulation. This expectation is especially stark for constant-depth circuits with local readout: the expectation value of any fixed local observable lies within a bounded backward lightcone and is therefore classically tractable. Here we show that measurement feedback changes this picture. We establish a strict hierarchy of computational power: at fixed coherent depth, increasing the number of feedback outcomes strictly enlarges the class of functions accessible through a local expectation value. The two ends of this hierarchy exhibit distinct computational regimes. With logarithmic feedback, local expectation values for product-state inputs are efficiently classically simulable. Polynomial feedback, by contrast, enables an explicit family of adaptive shallow circuits to encode prime-field discrete logarithm problem~(DLP) into a fixed single-qubit expectation. Assuming the standard worst-case classical hardness of DLP, estimating this expectation value is classically hard. These results reveal a feedback-driven complexity transition, with further implications for resource lower bounds on DLP and the complexity of local-observable estimation under area-law entanglement. Our results open a new route to quantum advantage with shallow quantum circuits.
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.
Reliable and scalable readout strategies are essential for quantum technologies. As quantum processors grow, extracting useful information must remain feasible without measurement circuits becoming a dominant bottleneck. Randomized measurements and classical shadows provide a powerful route, but global estimation is conventionally associated with highly random ensembles that require increasing circuit depth and hence substantial experimental overhead. In this work, we show that substantially less randomness suffices when the readout is meaningfully adapted to the quantities being estimated. We introduce shallow phase shadows, based on a sparse Clifford-IQP ensemble, and prove efficient global estimation of stabilizer-state fidelities despite the ensemble not forming an approximate relative-error design. On all-to-all architectures, the protocol admits a constant-depth implementation using mid-circuit measurements and classical feedforward, or logarithmic depth without auxiliary systems. The protocol requires only controlled-phase entangling gates and offers a tunable trade-off between circuit resources and estimation accuracy, making it particularly amenable to experimentally relevant architectures with long-range connectivity. Our results show that scalable quantum readout need not reproduce generic randomness: task-adapted randomization can enable substantially shallower global characterization protocols.
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.