Measurement-Driven Quantum Advantages in Shallow Circuits

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.