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

• URL: http://arxiv.org/abs/2604.12635v1
• Date: Tue, 14 Apr 2026 12:06:48 GMT
• Title: The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits
• Abstract summary: Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage.<n>We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions.<n>We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin.
• Score: 12.732381296045054
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Fault-Tolerant Logical Operations and Efficient State Preparation in Modular Quantum Architectures with Noisy Interfaces [0.12314765641075438]
  We show that interfaces can tolerate noise up to an order of magnitude higher than intra-QPU noise, with only a minor reduction in the fault-tolerance threshold.<n>We develop a protocol for preparing fault-tolerant logical GHZ states, reducing overhead, time, and nonlocal Bellpair consumption.<n>Our results provide quantitative evidence that distributed quantum error can enable scalable, fault-tolerant quantum computation in modular architectures.
  arXiv  Detail & Related papers  (2026-07-29T17:59:57Z)
• The Average Relative Entropy and Transpilation Depth determines the noise robustness in Variational Quantum Classifiers [1.8352113484137627]
  Variational Quantum Algorithms (VQAs) have been extensively researched for applications in Quantum Machine Learning (QML)<n>VQAs are predominantly evaluated classically due to uncertain results on noisy devices and limited resource availability.<n>We propose a relative entropy-based metric to verify whether a VQC model would perform similarly on a noisy device as it does on simulations.
  arXiv  Detail & Related papers  (2026-03-22T15:55:15Z)
• Fisher information based lower bounds on the cost of quantum phase estimation [0.0]
  Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator.<n>Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing.<n>We employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs.
  arXiv  Detail & Related papers  (2026-03-13T06:40:12Z)
• Ensemble-Based Quantum Signal Processing for Error Mitigation [3.5659159991711618]
  Noise remains a central obstacle to deploying quantum algorithms on near-term devices.<n>In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source.<n>We introduce a noise-resilient framework for Quantum Signal Processing that mitigates such coherent errors without increasing circuit depth or ancillary qubit requirements.
  arXiv  Detail & Related papers  (2026-01-27T21:35:06Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
  Quantum Neuromorphic Computing (QNC) merges quantum computation with neural computation to create scalable, noise-resilient algorithms for quantum machine learning (QML) At the core of QNC is the quantum perceptron (QP), which leverages the analog dynamics of interacting qubits to enable universal quantum computation.
  arXiv  Detail & Related papers  (2024-11-13T23:56:20Z)
• Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
  We show that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit.
  arXiv  Detail & Related papers  (2024-03-21T17:55:26Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Accurate methods for the analysis of strong-drive effects in parametric gates [94.70553167084388]
  We show how to efficiently extract gate parameters using exact numerics and a perturbative analytical approach. We identify optimal regimes of operation for different types of gates including $i$SWAP, controlled-Z, and CNOT.
  arXiv  Detail & Related papers  (2021-07-06T02:02:54Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.