Coherent-disorder-driven complexity transitions in a quantum-advantage architecture

Quantum random sampling, particularly using Instantaneous Quantum Polynomial-time (IQP) circuits, is a primary candidate for demonstrating quantum computational advantage. While the impact of incoherent noise (decoherence) on these circuits is well-studied, the effect of coherent spatial disorder—inhomogeneous miscalibrations in gate angles—remains largely unexplored. This paper investigates how such disorder affects the two pillars of sampling hardness: anticoncentration of the output distribution and the exponential complexity of tensor-network simulation.

The authors analyze a square-lattice IQP architecture using exact tensor-network contractions. They model the system as a Projected Entangled-Pair State (PEPS) and employ the Boundary Matrix Product State (BMPS) method to evaluate output probabilities for systems up to 576 qubits. By introducing quenched two-qubit gate-angle disorder, they track the evolution of the rescaled collision probability and the maximum entanglement entropy of the BMPS, using finite-size scaling (FSS) to characterize the transitions as the system size increases.

The study identifies two consecutive disorder-driven crossovers. First, as disorder strength increases, the output distribution loses its anticoncentration property, meaning the probability mass is no longer spread broadly across bitstrings. Second, the entanglement entropy of the BMPS drops from volume-law to logarithmic scaling, which allows the tensor-network contraction cost to transition from exponential to polynomial. These results suggest that coherent disorder is a significant vulnerability for IQP-based quantum advantage, as it fundamentally disrupts the interference structure required for computational hardness.

This work provides quantitative error-budget bounds for near-term quantum devices, highlighting that coherent errors are as critical as incoherent ones in maintaining quantum advantage. Unlike universal random circuits, which are somewhat robust due to their scrambling properties, IQP circuits are highly sensitive to spatial disorder. This distinction clarifies the different mechanisms of complexity in quantum architectures and provides a benchmark for evaluating the feasibility of quantum advantage in the presence of realistic hardware imperfections.