Curator's Take
This article tackles a critical but often overlooked challenge in the race for quantum advantage: how the physical layout of qubits fundamentally affects computational power in noisy quantum devices. While much attention focuses on reducing gate errors and increasing qubit counts, this research reveals that sparse connectivity patterns like 2D grids can push circuits beyond the noise threshold where classical computers can still simulate them, even when the abstract quantum algorithm should theoretically provide an advantage. The findings suggest that the path to near-term quantum advantage isn't just about better qubits, but about architecting quantum processors with connectivity patterns that minimize the routing overhead that destroys quantum benefits. This work provides crucial guidance for hardware designers and could explain why some quantum advantage demonstrations succeed while others fall short of expectations.
— Mark Eatherly
Summary
Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.