The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits
Leonardo Placidi 1 3 , Enrico Rinaldi 2 , Keisuke Fujii 3 , Chen-Yu Liu 2 · 2026
Read The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits by Leonardo Placidi 1 3 , Enrico Rinaldi 2 , Keisuke Fujii 3 , Chen-Yu Liu 2 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12635.txt.
Introduction
Leonardo Placidi and three colleagues link qubit connectivity to quantum advantage in noisy IQP circuits. IQP sampling is classically hard in ideal theory. Noise erases that hardness once depth passes a critical threshold. Sparse hardware needs extra routing, deepening compiled circuits. Different graphs thus shift a circuit's place against the simulatability boundary. The team pairs depth estimates with tests on seven device models. Sparse designs tolerate less noise for the same margin. The work tests when experiments stay outside classical simulatability.
Catalog record
| CREATOR | Leonardo Placidi 1 3 , Enrico Rinaldi 2 , Keisuke Fujii 3 , Chen-Yu Liu 2 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49084 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12635
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits Leonardo Placidi 1 3 , Enrico Rinaldi 2 , Keisuke Fujii 3 , Chen-Yu Liu 2 Abstract 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. I Introduction Demonstrating quantum advantage in the near term remains challenging because candidate circuits must satisfy two requirements: they should be believed to be classically hard to simulate in the ideal theoretical setting, and they must also remain outside the classically simulatable regime after the effects of noise, limited connectivity, and compilation overhead are taken into account [ 25 ] . One of the most studied proposals is Instantaneous Quantum Polynomial-time (IQP) circuits, whose sampling task is believed to be classically intractable in the ideal theoretical setting under standard complexity-theoretic assumptions (for example, the polynomial-hierarchy-collapse consequences if an efficient classical simulation of IQP were possible) [ 4 , 5 ] . In the idealized setting, IQP circuit sampling plays a central role in theoretical proposals for near-term quantum advantage [ 21 , 32 ] . Fig. 1 : Structure of an IQP (Instantaneous Quantum Polynomial) circuit. The circuit applies Hadamards to create superposition, then a diagonal unitary D(\theta)=e^{i\sum_{S}\theta_{S}Z_{S}} with k -local interactions (single-qubit R_{Z} , two-qubit ZZ, three-qubit ZZZ, etc.), followed by Hadamards and measurement. The diagonal gates commute and can be applied in any order, but compilation to sparse hardware requires decomposition into native gates and SWAP insertion. Despite these ideal-case hardness results, a growing body of theory shows that sufficiently strong hardware noise can destroy the complexity-theoretic evidence for hardness and render IQP circuits efficiently classically simulatable in relevant noisy models [ 17 , 6 , 26 ] . In particular, recent work identifies an efficiently classically simulatable regime, or ‘easy phase,’ for noisy IQP circuits [ 26 ] : when physical noise is interleaved throughout the circuit at sufficient strength, or when circuit depth is sufficiently large relative to the noise level, the resulting output distributions admit polynomial-time classical simulation. Intuitively, noise suppresses quantum correlations and fragments the effective interaction structure of the circuit, so that the computation reduces to small connected components that can be handled classically. This reframes the central question from “Is sampling from the output distribution of an IQP circuit classically hard?” to “Under what hardware-level conditions does an IQP implementation remain in a regime with complexity-theoretic evidence for hardness?” Most discussions of noisy-to-easy transitions treat “noise strength” as an intrinsic device property, e.g., a per-gate Pauli error rate or a per-circuit-depth dephasing rate, and analyze hardness as a function of that parameter and circuit depth. But hardware connectivity introduces an additional, often dominant, effect: the same abstract IQP circuit does not compile to the same physical circuit across architectures. This dependence of implemented circuits on device topology is already reflected in benchmarking approaches such as quantum volume, where connectivity and compilation directly influence the largest circuit size that can be successfully realized [ 12 ] . In the context of IQP sampling, however, the implications of this architectural dependence for noisy-to-easy transitions have not been explicitly analyzed. In connectivity-limited platforms (e.g. planar superconducting layouts), implementing nonlocal two-qubit interactions requires routing, typically realized through SWAP networks and additional entangling operations [ 11 ] . Even when the abstract circuit is shallow and structured, routing can increase the two-qubit gate count and circuit depth. In contrast, architectures with near all-to-all or dynamically reconfigurable long-range connectivity, most notably trapped-ion and neutral-atom platforms, can often implement the same interaction pattern with substantially less routing overhead than fixed nearest-neighbor layouts [ 15 , 16 ] . Consequently, compilation overhead induced by limited connectivity can move an implementation closer to regimes where noisy IQP circuits become efficiently classically simulatable. This paper develops a connectivity-aware framework for analyzing noisy IQP implementations under a proxy effective-noise model and a known noisy-IQP simulatability criterion. Rather than treating noise as a single scalar independent of hardware architecture, we connect architecture to effective noise and compiled depth through compilation. The objective is not to re-prove IQP hardness or introduce a new advantage model, but to formulate precisely and evaluate quantitatively the claim that connectivity is a critical resource for keeping noisy IQP implementations outside the known efficiently simulatable regime. We frame this as a shift in the simulatability phase diagram: for a fixed abstract IQP circuit family, different hardware graphs yield different compiled depths and different effective noise parameters, thereby moving the physical experiment along the axis controlling known simulatability thresholds. Concretely, for each hardware graph, we study the compiled depth, routing-induced overhead, and resulting simulatability margin, which measures the signed distance between the compiled implementation and the noisy-IQP critical-depth boundary. This makes explicit how hardware-dependent compilation can shift a fixed abstract IQP instance toward the efficiently simulatable regime. We summarize the paper’s main contributions as follows: 1. Connectivity-aware framework for simulatability shifts in noisy IQP circuits. We identify qubit connectivity and routing overhead as key variables in the noisy-to-easy transition for compiled IQP implementations. 2. Quantitative theory for simulatability shifts. We relate hardware graph, compiled depth, and effective noise to the noisy-IQP phase boundary, and derive connectivity-dependent depth and noise-budget relations across architectures. 3. Native-gateset-aware study on seven hardware-grounded experimental models. Using models derived from publicly available topologies and error-rate proxies, we show empirically how sparse connectivity increases routing overhead, inflates depth, and pushes implementations toward the classically simulatable regime. While compilation overhead is widely recognized as a practical concern of quantum utility, we argue it can be computationally decisive for assessing whether a noisy IQP experiment operates in the hard regime or the simulatable regime. II Polynomial-Time Simulation of Noisy IQP Circuits We summarize the key theoretical mechanism underlying the “easy phase” of IQP sampling under physically motivated noise, following the recent