Abstract: Reliable quantum computation requires certifiable bounds on the degradation of ideal circuit outputs under realistic noise. Existing fidelity estimates are typically asymptotic, hardware-specific, or require full density-matrix simulation, rendering them impractical for circuit-scale certification. We introduce a computable fidelity floor for noisy quantum circuits based on light-cone–resolved Pauli weight growth. For circuits subject to independent Markovian single-qubit noise, we prove a rigorous trace-distance bound expressed entirely in terms of circuit structure: per-qubit active times and a combinatorial backward light-cone descriptor of entangling gates. The resulting bound is computable in O(Gn) time for a circuit with Ggates on nqubits, avoiding exponential state-space simulation. We further introduce an empirically validated exponential envelope refinement that tightens the rigorous bound while remaining conservative across all tested configurations. Across more than 103 circuit instances spanning four noise heterogeneity structures (uniform, anti-correlated, spike, and random per-qubit T1/T2 rates, up to n= 8, depth 40), the envelope bound achieves 100% validity and exhibits a stable compression factor across heterogeneity modes, reaching approximately 2.6× at depth 20 relative to the combinatorial bound. The envelope remains informative within the empirically determined regime n≤ 8, depth ≤ 20, and γT ≲ 0.3. These results establish a circuit-structure–based fidelity certification framework computable at compiler timescale and identify a depth-dependent compression invariant connecting rigorous combinatorial bounds to empirically tighter envelope estimates.
Abstract: Reliable quantum computation requires certifiable bounds on the degradation of ideal circuit outputs under realistic noise. Existing fidelity estimates are typically asymptotic, hardware-specific, or require full density-matrix simulation, rendering them impractical for circuit-scale certification. We introduce a computable fidelity floor for noisy quantum circuits based on light-cone–resolved Pauli weight growth. For circuits subject to independent Markovian single-qubit noise, we prove a rigorous trace-distance bound expressed entirely in terms of circuit structure: per-qubit active times and a combinatorial backward light-cone descriptor of entangling gates. The resulting bound is computable in O(Gn) time for a circuit with Ggates on nqubits, avoiding exponential state-space simulation. We further introduce an empirically validated exponential envelope refinement that tightens the rigorous bound while remaining conservative across all tested configurations. Across more than 103 circuit instances spanning four noise heterogeneity structures (uniform, anti-correlated, spike, and random per-qubit T1/T2 rates, up to n= 8, depth 40), the envelope bound achieves 100% validity and exhibits a stable compression factor across heterogeneity modes, reaching approximately 2.6× at depth 20 relative to the combinatorial bound. The envelope remains informative within the empirically determined regime n≤ 8, depth ≤ 20, and γT ≲ 0.3. These results establish a circuit-structure–based fidelity certification framework computable at compiler timescale and identify a depth-dependent compression invariant connecting rigorous combinatorial bounds to empirically tighter envelope estimates.
Dynamic circuits, which augment unitary operations with mid-circuit measurements and classical feedforward, can generate long-range entanglement in constant depth, enabling low-depth primitives ranging from nontrivial state preparation to many-qubit entangling gates. Escaping the light-cone constraints of unitary circuits, however, comes at a cost: these primitives typically require a number of mid-circuit measurements that scales with system size and that, together with feedforward latency, can introduce errors that degrade the long-range entanglement they rely on. Here, we alleviate this tension by showing that many such primitives, when cast into a common framework, admit an error-detection scheme that trades infidelity for postselection overhead with no additional ancillas. Our framework thus unifies and upgrades a broad class of primitives including fan-out gates, multi-qubit Pauli rotations, the preparation of W and higher-weight Dicke states, and certain non-normal matrix product states. We also introduce a reduced-depth, error-detected implementation of the Hadamard test, extending the use cases of dynamic circuits to a key algorithmic primitive. Finally, we establish the practical utility of our scheme through experiments on a superconducting quantum processor. We demonstrate the error-detected preparation of a long-range entangled Bell pair spanning a 100-qubit chain with fidelity F=0.59±0.02, surpassing the entanglement-certification threshold F>0.5 that the baseline dynamic-circuit implementation fails to reach (0.39±0.01). Separately, we demonstrate constant-depth preparation of W states of up to 20 qubits by consuming GHZ states of up to 40 qubits, finding absolute fidelity improvements of ΔF≈0.2 across the largest sizes studied. Altogether, these results bring low-depth dynamic-circuit primitives within practical reach on present-day hardware.
Abstract Reliable quantum computation requires certifiable bounds on the degradation of ideal circuit outputs under realistic noise. Existing fidelity estimates are typically asymptotic, hardware-specific, or require full density-matrix simulation, rendering them impractical for circuit-scale certification. We introduce a computable fidelity floor for noisy quantum circuits based on light-cone--resolved Pauli weight growth. For circuits subject to independent Markovian single-qubit noise, we prove a rigorous trace-distance bound expressed entirely in terms of circuit structure: per-qubit active times and a combinatorial backward light-cone descriptor of entangling gates. The resulting bound is computable in O(Gn) time for a circuit with G gates on n qubits, avoiding exponential state-space simulation. We further introduce an empirically validated exponential envelope refinement that tightens the rigorous bound while remaining conservative across all tested configurations. Across more than 103 circuit instances spanning four noise heterogeneity structures (uniform, anti-correlated, spike, and random per-qubit T1/T2 rates, up to n=8, depth~40), the envelope bound achieves 100\% validity and exhibits a stable compression factor across heterogeneity modes, reaching approximately 2.6× at depth~20 relative to the combinatorial bound. The envelope remains informative within the empirically determined regime n≤8, depth~≤20, and γT≲0.3. These results establish a circuit-structure--based fidelity certification framework computable at compiler timescale and identify a depth-dependent compression invariant connecting rigorous combinatorial bounds to empirically tighter envelope estimates.
Abstract Quantum noise in real-world devices poses a significant challenge in achieving practical quantum advantage, since accurately compiled and executed circuits are typically deep and highly susceptible to decoherence. To facilitate the implementation of complex quantum algorithms on noisy hardware, we propose an approximate method for compiling target quantum circuits into brick-wall layouts. This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers, in conjunction with optimized one-qubit gates, to approximate the essential dynamics of the original circuit while significantly reducing its depth. Our approach is evaluated through numerical simulations of time-evolution circuits for the critical Ising model, quantum Fourier transformation, and Haar-random quantum circuits, as well as experiments on IBM quantum platforms. By accounting for compilation error and circuit noise, we demonstrate that time evolution and quantum Fourier transformation circuits achieve high compression rates, while random quantum circuits are less compressible. The degree of compression is related to the rate of entanglement accumulation in the target circuit. In particular, experiments on IBM platforms achieve a compression rate of 12.5 for N=12, significantly extending the application of current quantum devices. Furthermore, large-scale numerical simulations for system sizes up to N=30 reveal that the optimal depth dmax to achieve maximal overall fidelity is independent of system size N, suggesting the scalability of our method for large quantum devices in terms of quantum resources.
Sampling-based proposals are prominent candidates for demonstrating quantum computations beyond the reach of classical supercomputers. However, it has been difficult to combine their complexity-theoretic hardness with two capabilities needed for scalable quantum computing more generally: suppressing hardware errors, and verifying the quantum computation itself. Here we address both issues by introducing structured circuits, which, in addition to provable hardness guarantees, admit an encoding in a quantum code. This allows us to simultaneously reach high fidelities at high circuit depths, and to certify an experimental fidelity via the circuit structure and measurement of code syndromes. The resulting certificate is device dependent, but requires substantially weaker noise assumptions than existing fidelity proxy benchmarks. We demonstrate our proposal with a 64-qubit, depth-73 Clifford circuit, doped with 314T gates. We use a total of 76 physical qubits to encode this computation in spacetime codes, effectively suppressing gate error rates by 10× after syndrome post-selection, and yielding a state with a fidelity lower bound of 0.349 with 95% confidence. Our construction is a systematic method for promoting a stabilizer state to a magic state while keeping an error-detected fidelity certificate.
As quantum devices grow in size while remaining affected by noise, a key challenge is to determine when and how they can surpass classical computation on practical tasks. This requires the development of highly efficient classical simulation algorithms. Pauli backpropagation algorithms are among the most promising, having shown efficiency in simulating certain classes of parameterized quantum circuits, strong candidates for near‑term quantum advantage, under random circuit assumptions and depolarizing noise. However, their efficiency had not been demonstrated for more realistic nonunital noise models, such as amplitude damping, which better capture the behaviour of current hardware. We close this gap by adapting Pauli backpropagation to most single‑qubit noise channels, including nonunital noise, and proving that it remains efficient under these conditions. Our algorithm is parallelizable, memory‑efficient, and requires no assumptions on the locality of the observable, the geometry of the hardware, or the depth of the circuit. While hardware noise can strongly affect computational power in highly structured, fault‑tolerant circuits, our findings indicate little difference for most near‑term variational architectures. This establishes Pauli backpropagation as an efficient method for simulating noisy quantum devices under realistic noise assumptions.While these advances improve our ability to reproduce noisy expectation values of observables, many practical applications, including combinatorial optimization, require direct access to the bitstrings output by quantum circuits, as these encode candidate solutions. Classical replication of such noisy samples has so far been limited beyond the random circuit setting. To bridge this gap, we first focus on problems whose objective functions depend only on two‑body correlations, such as Max‑Cut, and apply Gaussian randomized rounding to the circuit's two‑qubit marginals. This produces classical samples whose expected cost is provably close to that of the noisy quantum device. Large‑scale simulations and experiments on IBMQ hardware confirm that the rounded samples reproduce the full energy distribution, with similar behaviour under various noise models. Coupled with Pauli backpropagation for efficiently estimating noisy marginals, this yields an end‑to‑end classical sampler operating in polynomial time for a broad class of variational circuits. Our results therefore show that sufficiently noisy quantum circuits for combinatorial optimization can be sampled from classically, clarifying where near‑term hardware may or may not outperform classical algorithms.Finally , we go beyond one and two‑body marginals and present an algorithm that samples valid bitstrings directly from a maximum‑entropy distribution matching the given expectation values of the quantum circuit. This method does not rely on the locality or sparsity of the problem's Hamiltonian and performs well across a variety of quantum circuits, including deep circuits on many qubits. When combined with Pauli propagation or error mitigation, it provides a practical pipeline for obtaining samples from quantum circuits in the near term, where full error correction might not yet be available.
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on n qubits, initialized in an arbitrary product state, with nearest-neighbor gates in O(1) spatial dimensions and interspersed depolarizing noise of any constant strength p. Our first result is that when the depth exceeds a threshold d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its n-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds Θ~(p−1).