pith. machine review for the scientific record. sign in

arxiv: 2604.12635 · v1 · submitted 2026-04-14 · 🪐 quant-ph

Recognition: unknown

The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:13 UTC · model grok-4.3

classification 🪐 quant-ph
keywords compiledconnectivitydeptheffectivesimulatabilitysparseboundarycircuits
0
0 comments X

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.

This paper investigates how the arrangement of qubit connections influences the potential for quantum advantage in noisy Instantaneous Quantum Polynomial-time circuits. These circuits are expected to be hard for classical computers when ideal, but noise turns them simulatable past a depth threshold. Sparse connections add routing gates that increase depth, shifting the circuit toward easier simulation. By analyzing compiled depths on various real hardware topologies and estimating noise from gate errors, the work shows sparse setups need better noise control to stay in the hard regime. A sympathetic reader would care because this guides which hardware features matter most for demonstrating advantage soon.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2604.12635 by Chen-Yu Liu, Enrico Rinaldi, Keisuke Fujii, Leonardo Placidi.

Figure 1
Figure 1. Figure 1: Structure of an IQP (Instantaneous Quantum Polyno [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Percolation-based fragmentation for four IQP interaction patterns at [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Native hardware connectivity graphs used in the routing [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Phase diagrams for k=2 IQP circuits across four interaction patterns. The critical boundary D∗(p, k) = c/(p ln(k/p)) (black curve) separates the simulatable regime (teal, m(H) < 0) from the potentially hard regime (coral, m(H) > 0). Each platform is plotted at its operating point (peff(H), DH); the legend reports the ideal fully-connected depth DFC and the compiled depth DH as (DFC/DH). Reported depths are… view at source ↗
Figure 5
Figure 5. Figure 5: Compilation efficiency ηH := DFC/DH versus qubit count for four interaction patterns. Solid segments correspond to compiled data; dashed segments show per-hardware linear extrapolations beyond the measured range. Panels (a)–(c) use compiled data for n = 4–32 and extrapolate to n = 70; panel (d) shows RHG lattice instances extrapolations at the valid sizes n ∈ {18, 44, 90, 127} [PITH_FULL_IMAGE:figures/ful… view at source ↗
Figure 6
Figure 6. Figure 6: Reference connectivity graphs used as simplified [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. Define 'simulatability margin' explicitly (with formula or reference) at first use to avoid ambiguity in the quantitative comparisons.
  2. Include a table or figure summarizing the seven device models' connectivity graphs, qubit counts, and reported error rates for full reproducibility.
  3. Ensure consistent use of 'compiled depth' versus any variant terms across analytic and experimental sections.

Simulated Author's Rebuttal

3 responses · 0 unresolved

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
  1. 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

  2. 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

  3. 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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The abstract relies on standard complexity assumptions for IQP hardness and conventional noise models; no new free parameters, axioms, or invented entities are introduced.

axioms (1)
  • domain assumption IQP sampling is classically hard under standard complexity-theoretic assumptions in the ideal case
    Invoked to establish IQP as a candidate for quantum advantage before discussing noise effects.

pith-pipeline@v0.9.0 · 5593 in / 1179 out tokens · 80822 ms · 2026-05-10T15:13:32.572449+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Compositional Quantum Heuristics for Max-Clique Detection

    quant-ph 2026-05 unverdicted novelty 5.0

    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

37 extracted references · 17 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    Quantum Computing in the NISQ era and beyond,

    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

  2. [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. [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. [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

  5. [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. [6]

    Available: https://arxiv.org/abs/2602.11042

    [Online]. Available: https://arxiv.org/abs/2602.11042

  7. [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. [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. [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

  10. [10]

    Cross, Lev S

    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. [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. [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

  13. [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

  14. [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

  15. [15]

    Universal quantum simulation of 50 qubits on europes first exascale supercom- puter harnessing its heterogeneous cpu-gpu architecture,

    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. [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. [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. [18]

    Quantum Science and Technol- ogy6(1), 014003 (2020).https://doi.org/10.1088/2058-9565/ab8e92 A Notation T able 1.Notation used in the manuscript

    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. [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. [20]

    Ionq forte system performance metrics,

    IonQ, “Ionq forte system performance metrics,” IonQ, Inc., Tech. Rep.,

  21. [21]

    Available: https://ionq.com/quantum-systems/forte

    [Online]. Available: https://ionq.com/quantum-systems/forte

  22. [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

  23. [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/

  24. [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

  25. [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

  26. [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

  27. [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

  28. [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. [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

  30. [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

  31. [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

  32. [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

  33. [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

  34. [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

  35. [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. [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. [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