Recognition: unknown
The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits
Pith reviewed 2026-05-10 15:13 UTC · model grok-4.3
The pith
Qubit connectivity determines the noise threshold for quantum advantage in noisy IQP circuits.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For any fixed IQP circuit, hardware with sparse qubit connectivity produces longer compiled circuits due to the need for routing swaps or additional gates to realize distant interactions. This increased depth moves the noisy implementation closer to the boundary where classical simulation becomes feasible. Using both analytic depth formulas for grid-like architectures and actual compilation runs on seven device models, the paper quantifies how much lower the effective noise must be on sparse graphs to maintain the same distance from the simulatability limit as on denser graphs.
What carries the argument
Connectivity-aware compilation that calculates the depth overhead from routing on sparse graphs and the resulting shift in the position relative to the noisy IQP simulatability boundary.
Where Pith is reading between the lines
- Hardware designers might prioritize adding more connections even at the cost of other resources to enable deeper useful circuits.
- The approach could be applied to other near-term quantum tasks where circuit depth is a limiting factor.
- Future work could incorporate more detailed noise models beyond two-qubit errors to refine these predictions.
Load-bearing premise
That the boundary for classical simulability of noisy IQP circuits depends mainly on the total compiled depth and the average two-qubit gate error rate.
What would settle it
Compiling an IQP circuit to two different connectivities, running it on hardware or a noise model, and checking whether the output distribution hardness transitions at the depth predicted by the analysis.
Figures
read the original 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that for a fixed abstract IQP instance, different qubit connectivity graphs on hardware lead to different compiled circuit depths due to routing overhead, thereby shifting the circuits' positions relative to the noisy-IQP simulatability boundary. Using analytic depth estimates for sparse geometries (e.g., 2D grids) and native-gateset compilation experiments on seven hardware-derived device models, with effective noise approximated primarily from two-qubit gate error rates, it concludes that sparse architectures require lower effective noise levels than denser ones to maintain the same margin against classical simulability.
Significance. If substantiated, the work supplies a practical quantitative framework for experimentalists to assess architecture-dependent prospects for noisy IQP advantage, by explicitly linking connectivity-induced depth overhead to the simulatability threshold. It extends prior noisy IQP analyses with device-grounded comparisons and analytic estimates, providing a tool to rank hardware topologies for this task. The combination of analytic depth calculations and multi-device experiments is a methodological strength that could aid reproducible evaluations.
major comments (3)
- [Abstract / unified empirical framework] Abstract and unified empirical framework: The simulatability boundary is positioned via compiled depth plus an effective noise proxy derived primarily from reported two-qubit gate error rates. However, without sensitivity checks or bounds on contributions from single-qubit errors, readout noise, or idle errors during routing/SWAP layers, the claimed architecture-dependent margin shifts (sparse vs. dense) rest on an incomplete noise model that may mis-rank the devices. This approximation is load-bearing for the central quantitative conclusion.
- [native-gateset-aware compilation experiments] Native-gateset-aware compilation experiments: For the seven device models, the paper must detail the exact compilation procedure, including how routing overhead is quantified in depth and whether non-uniform error propagation from extra SWAPs is folded into the effective noise or boundary calculation. Absent this, the depth-to-margin mapping for a fixed IQP instance cannot be verified as robust.
- [analytic depth estimates] Analytic depth estimates for sparse geometries: The translation from 2D-grid (and other) connectivity overhead to simulatability margin assumes the boundary depends primarily on total depth and the scalar noise proxy. The paper should provide the explicit functional form or reference used for the boundary and test whether the overhead formula holds under the paper's own noise approximation.
minor comments (3)
- Define 'simulatability margin' explicitly (with formula or reference) at first use to avoid ambiguity in the quantitative comparisons.
- Include a table or figure summarizing the seven device models' connectivity graphs, qubit counts, and reported error rates for full reproducibility.
- Ensure consistent use of 'compiled depth' versus any variant terms across analytic and experimental sections.
Simulated Author's Rebuttal
We thank the referee for the thorough and constructive report. The comments highlight important aspects of our noise modeling and methodological details. We address each major comment below and will revise the manuscript to incorporate clarifications, additional details, and sensitivity discussions where feasible.
read point-by-point responses
-
Referee: [Abstract / unified empirical framework] Abstract and unified empirical framework: The simulatability boundary is positioned via compiled depth plus an effective noise proxy derived primarily from reported two-qubit gate error rates. However, without sensitivity checks or bounds on contributions from single-qubit errors, readout noise, or idle errors during routing/SWAP layers, the claimed architecture-dependent margin shifts (sparse vs. dense) rest on an incomplete noise model that may mis-rank the devices. This approximation is load-bearing for the central quantitative conclusion.
Authors: We agree that the effective noise proxy, derived primarily from two-qubit gate error rates, is a simplification. While two-qubit errors dominate in current superconducting and trapped-ion devices, we will add a dedicated subsection in the revised manuscript providing bounds on the relative contributions of single-qubit, readout, and idle errors during routing. This will include a sensitivity analysis showing that the architecture-dependent ranking of margins remains qualitatively robust under reasonable variations in these terms, as the additional noise sources scale similarly across the compared device models. revision: yes
-
Referee: [native-gateset-aware compilation experiments] Native-gateset-aware compilation experiments: For the seven device models, the paper must detail the exact compilation procedure, including how routing overhead is quantified in depth and whether non-uniform error propagation from extra SWAPs is folded into the effective noise or boundary calculation. Absent this, the depth-to-margin mapping for a fixed IQP instance cannot be verified as robust.
Authors: We will expand the Methods and Supplementary Information sections to provide the precise compilation workflow, including the routing algorithm employed, the metric used to quantify depth overhead (total two-qubit gate count after decomposition), and the handling of SWAP layers. Our effective noise proxy applies the reported average two-qubit error rate uniformly to all two-qubit operations, including those arising from routing; we will explicitly state this approximation and note that non-uniform propagation is not modeled at the gate level but is captured at the aggregate depth level. revision: yes
-
Referee: [analytic depth estimates] Analytic depth estimates for sparse geometries: The translation from 2D-grid (and other) connectivity overhead to simulatability margin assumes the boundary depends primarily on total depth and the scalar noise proxy. The paper should provide the explicit functional form or reference used for the boundary and test whether the overhead formula holds under the paper's own noise approximation.
Authors: The simulatability boundary follows the depth-dependent threshold derived in the noisy IQP literature (specifically the exponential decay of the output distribution's total variation distance with depth under local noise). We will insert the explicit functional form, together with the relevant reference, into the main text. We will also add a short verification subsection confirming that the analytic overhead formula for 2D grids and other sparse graphs remains consistent when evaluated under the same effective noise proxy used for the device models. revision: yes
Circularity Check
No circularity: analysis uses external topologies and reported error rates as independent inputs
full rationale
The paper derives architecture-dependent shifts in compiled IQP depth and position relative to the noisy simulatability boundary via analytic estimates for sparse graphs plus native-gate compilation experiments on seven publicly documented device topologies. Effective noise is approximated directly from reported two-qubit gate error rates (external data) rather than fitted within the paper. No equation or claim reduces by construction to a self-defined quantity, a fitted parameter renamed as prediction, or a load-bearing self-citation; the simulatability boundary itself is invoked as an external benchmark. The derivation therefore remains self-contained against independent hardware data.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption IQP sampling is classically hard under standard complexity-theoretic assumptions in the ideal case
Forward citations
Cited by 1 Pith paper
-
Compositional Quantum Heuristics for Max-Clique Detection
Compositional quantum circuits with symmetry-induced invariant losses produce trainable equivariant quantum GNNs that generalize on max-clique problems and improve hybrid recursive search accuracy and scalability.
Reference graph
Works this paper leans on
-
[1]
Quantum computing in the NISQ era and beyond.Quantum, 2:79, 2018
J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018. [Online]. Available: https: //doi.org/10.22331/q-2018-08-06-79
work page internal anchor Pith review doi:10.22331/q-2018-08-06-79 2018
-
[2]
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,
M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,”Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 467, no. 2126, pp. 459–472, Aug. 2010. [Online]. Available: https://doi.org/10.1098/rspa.2010.0301
-
[3]
Average-case complexity versus approximate simulation of commuting quantum computations,
M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum computations,”Physical Review Letters, vol. 117, no. 8, Aug. 2016. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.117.080501
-
[4]
Toward Generative Quantum Utility via Correlation-Complexity Map
C.-Y . Liu, L. Placidi, E. Brunner, and E. Rinaldi, “Toward generative quantum utility via correlation-complexity map,” 2026. [Online]. Available: https://arxiv.org/abs/2603.06440
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[5]
Characterizing trainability of instantaneous quantum polynomial circuit born machines,
K. Shen, S. Pielawa, V . Dunjko, and H. Wang, “Characterizing trainability of instantaneous quantum polynomial circuit born machines,”
-
[6]
Available: https://arxiv.org/abs/2602.11042
[Online]. Available: https://arxiv.org/abs/2602.11042
-
[7]
Computational quantum-classical boundary of noisy commuting quantum circuits,
K. Fujii and S. Tamate, “Computational quantum-classical boundary of noisy commuting quantum circuits,”Scientific Reports, vol. 6, p. 25598, 2016. [Online]. Available: https://doi.org/10.1038/srep25598
-
[8]
Achieving quantum supremacy with sparse and noisy commuting quantum computations,
M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Achieving quantum supremacy with sparse and noisy commuting quantum computations,”Quantum, vol. 1, p. 8, Apr. 2017. [Online]. Available: http://dx.doi.org/10.22331/q-2017-04-25-8
-
[9]
Polynomial-time classical simulation of noisy iqp circuits with constant depth,
J. Rajakumar, J. D. Watson, and Y .-K. Liu, “Polynomial-time classical simulation of noisy iqp circuits with constant depth,” inProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2025, pp. 1037–1056
2025
-
[10]
A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta, “Validating quantum computers using randomized model circuits,”Physical Review A, vol. 100, no. 3, Sep. 2019. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.100.032328
-
[11]
On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019
A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmonset al., “On the qubit routing problem,”arXiv preprint arXiv:1902.08091, 2019
-
[12]
Com- putational power of random quantum circuits in arbitrary geometries,
M. DeCross, R. Haghshenas, M. Liu, E. Rinaldi, J. Grayet al., “Com- putational power of random quantum circuits in arbitrary geometries,” Physical Review X, vol. 15, no. 2, p. 021052, 2025
2025
-
[13]
High-fidelity parallel entangling gates on a neutral-atom quantum computer,
S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz et al., “High-fidelity parallel entangling gates on a neutral-atom quantum computer,”Nature, vol. 622, no. 7982, pp. 268–272, 2023
2023
-
[14]
Simulating quantum computation by contract- ing tensor networks,
I. L. Markov and Y . Shi, “Simulating quantum computation by contract- ing tensor networks,”SIAM Journal on Computing, vol. 38, no. 3, pp. 963–981, 2008
2008
-
[15]
H. De Raedt, J. Kraus, A. Herten, V . Mehta, M. Bodeet al., “Universal quantum simulation of 50 qubits on europes first exascale supercom- puter harnessing its heterogeneous cpu-gpu architecture,”arXiv preprint arXiv:2511.03359, 2025
-
[16]
Topological fault- tolerance in cluster state quantum computation,
R. Raussendorf, J. Harrington, and K. Goyal, “Topological fault- tolerance in cluster state quantum computation,”New Journal of Physics, vol. 9, no. 6, p. 199–199, Jun. 2007. [Online]. Available: http://dx.doi.org/10.1088/1367-2630/9/6/199
-
[17]
Qiskit: An open-source framework for quantum computing,
T. Q. D. Team, “Qiskit: An open-source framework for quantum computing,” 2023. [Online]. Available: https://arxiv.org/abs/2309.08774
-
[18]
S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgingtonet al., “t—ket〉: a retargetable compiler for nisq devices,”Quantum Science and Technology, vol. 6, no. 1, p. 014003, Nov. 2020. [Online]. Available: http://dx.doi.org/10.1088/2058-9565/ab8e92
-
[19]
Helios: A 98-qubit trapped-ion quantum computer,
A. Ransford, M. S. Allman, J. Arkinstall, J. P. C. III, S. F. Cooper et al., “Helios: A 98-qubit trapped-ion quantum computer,” 2025. [Online]. Available: https://arxiv.org/abs/2511.05465
-
[20]
Ionq forte system performance metrics,
IonQ, “Ionq forte system performance metrics,” IonQ, Inc., Tech. Rep.,
-
[21]
Available: https://ionq.com/quantum-systems/forte
[Online]. Available: https://ionq.com/quantum-systems/forte
-
[22]
Willow spec sheet,
Google Quantum AI, “Willow spec sheet,” Google Quantum AI, Tech. Rep., 2024. [Online]. Available: https://quantumai.google/static/ site-assets/downloads/willow-spec-sheet.pdf
2024
-
[23]
H. Neven. (2024) Meet willow, our state-of-the-art quantum chip. Google Quantum AI Blog. [Online]. Available: https://blog.google/ innovation-and-ai/technology/research/google-willow-quantum-chip/
2024
-
[24]
Quantum error correction below the surface code threshold,
G. Q. AI and collaborators, “Quantum error correction below the surface code threshold,”Nature, 2025. [Online]. Available: https://www.nature.com/articles/s41586-024-08449-y
2025
-
[25]
Quantum supremacy using a programmable supercon- ducting processor,
F. Aruteet al., “Quantum supremacy using a programmable supercon- ducting processor,”Nature, vol. 574, pp. 505–510, 2019
2019
-
[26]
Fakewashingtonv2 backend documentation,
IBM Quantum, “Fakewashingtonv2 backend documentation,” https://quantum.cloud.ibm.com/docs/api/qiskit/0.46/qiskit.providers. fake provider.FakeWashingtonV2, 2024, qiskit fake backend representing a 127-qubit IBM Quantum device snapshot. Accessed: 2026-03-11
2024
-
[27]
Rigetti quantum processing units (qpus),
Rigetti Computing, “Rigetti quantum processing units (qpus),” https: //qcs.rigetti.com/qpus, 2025, describes the Ankaa-class superconducting processors including Ankaa-3. Accessed: 2026-03-11
2025
-
[28]
Echo cross resonance gate error budgeting on a superconducting quantum processor,
T. Ward, R. P. Rundle, R. Bounds, N. Deak, G. Doldet al., “Echo cross resonance gate error budgeting on a superconducting quantum processor,” 2026. [Online]. Available: https://arxiv.org/abs/2601.20458
-
[29]
Efficient implementa- tion of arbitrary two-qubit gates using unified control,
Z. Chen, W. Liu, Y . Ma, W. Sun, R. Wanget al., “Efficient implementa- tion of arbitrary two-qubit gates using unified control,”Nature Physics, vol. 21, no. 9, pp. 1489–1496, 2025
2025
-
[30]
Fast quantum logic gates with trapped-ion qubits,
V . M. Sch¨afer, C. J. Ballance, K. Thirumalai, L. Stephenson, T. Ballance et al., “Fast quantum logic gates with trapped-ion qubits,”Nature, vol. 555, no. 7694, pp. 75–78, 2018
2018
-
[31]
Trapped- ion quantum computing: Progress and challenges,
C. D. Bruzewicz, J. Chiaverini, R. McConnell, and J. M. Sage, “Trapped- ion quantum computing: Progress and challenges,”Applied physics reviews, vol. 6, no. 2, 2019
2019
-
[32]
Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling,
P. Das, S. Tannu, S. Dangwal, and M. Qureshi, “Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling,” inMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, 2021, pp. 950–962
2021
-
[33]
Experimental characterization of crosstalk errors with simultaneous gate set tomography,
K. Rudinger, C. W. Hogle, R. K. Naik, A. Hashim, D. Lobseret al., “Experimental characterization of crosstalk errors with simultaneous gate set tomography,”PRX quantum, vol. 2, no. 4, p. 040338, 2021
2021
-
[34]
Mitigating measurement errors in multiqubit experiments,
S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, “Mitigating measurement errors in multiqubit experiments,”Physical Review A, vol. 103, no. 4, p. 042605, 2021
2021
-
[35]
High precision analytical description of the allowed beta spectrum shape
Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Hugginset al., “Quantum error mitigation,”Reviews of Modern Physics, vol. 95, no. 4, Dec. 2023. [Online]. Available: http://dx.doi.org/10.1103/RevModPhys. 95.045005
-
[36]
Deep learning approaches to quantum error mitigation,
L. Placidi, I. Williams, E. Rinaldi, D. Mills, C. C ˆırstoiuet al., “Deep learning approaches to quantum error mitigation,” 2026. [Online]. Available: https://arxiv.org/abs/2601.14226
-
[37]
V olumetric benchmarking of error mitigation with qermit,
C. Cirstoiu, S. Dilkes, D. Mills, S. Sivarajah, and R. Duncan, “V olumetric benchmarking of error mitigation with qermit,”Quantum, vol. 7, p. 1059, Jul. 2023. [Online]. Available: http://dx.doi.org/10. 22331/q-2023-07-13-1059
2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.