HAIL: An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction

• URL: http://arxiv.org/abs/2502.07536v1
• Date: Tue, 11 Feb 2025 13:21:33 GMT
• Title: HAIL: An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction
• Authors: Kang Xu, Zeyang Li, Xinjian Liu, Dandan Li, Yukun Wang,
• Abstract summary: Current quantum devices only support interactions between physical qubits and a limited number of neighboring qubits. To execute the circuit, SWAP gates must be inserted to adjust the mapping relationships between qubits. This paper proposes HAIL, an efficient iterative qubit mapping algorithm to minimize additional SWAP gates.
• Score: 7.698997402561804
• License:
• Abstract: Current quantum devices only support interactions between physical qubits and a limited number of neighboring qubits, preventing quantum circuits from being executed directly on the devices. To execute the circuit, SWAP gates must be inserted to adjust the mapping relationships between qubits, which consequently increases runtime and error rates in quantum circuits. To address these challenges, this paper proposes HAIL, an efficient iterative qubit mapping algorithm to minimize additional SWAP gates. First, a layer-weight assignment method integrated with the subgraph isomorphism algorithm is introduced to establish an initial mapping. Next, we propose a SWAP sequence search combined with the post-processing function to identify the optimal SWAP sequences. Finally, the qubit mapping algorithm is refined through iterative forward and backward traversals to further reduce the number of SWAP gates. Experimental results on the IBM Q20 architecture and various benchmarks demonstrate that HAIL-3 reduces the number of additional gates inserted in the $\mathcal{B}_{23}$ by 20.62% compared to state-of-the-art algorithms. Additionally, we present a partially extended strategy based on HAIL to reduce the sequence search space, with experiments on the sparsely connected Google Sycamore architecture showing a reduction in both algorithm runtime and additional SWAP gates.

Related papers

• Joint Transmit and Pinching Beamforming for PASS: Optimization-Based or Learning-Based? [89.05848771674773]
  A novel antenna system ()-enabled downlink multi-user multiple-input single-output (MISO) framework is proposed. It consists of multiple waveguides, which equip numerous low-cost antennas, named (PAs) The positions of PAs can be reconfigured to both spanning large-scale path and space.
  arXiv  Detail & Related papers  (2025-02-12T18:54:10Z)
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms [3.990724104767043]
  Quantum algorithms implemented on near-term devices require qubit mapping due to noise and limited qubit connectivity. We propose a strategy called algorithm-oriented qubit mapping (AOQMAP) that aims to bridge the gap between exact and scalable mapping methods.
  arXiv  Detail & Related papers  (2023-10-15T13:18:06Z)
• A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates [0.8057006406834467]
  Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A good initial mapping for the swap strategy reduces the number of required swap gates. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware.
  arXiv  Detail & Related papers  (2022-12-12T02:53:45Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  Two-qubit gates are important components of quantum computing. But unwanted interactions between qubits (so-called parasitic gates) can degrade the performance of quantum applications. We present two software methods to mitigate parasitic two-qubit gate errors.
  arXiv  Detail & Related papers  (2021-11-08T17:37:27Z)
• String Abstractions for Qubit Mapping [0.0]
  We introduce a novel qubit mapping approach, string-based qubit mapping. Key insight is to prioritize the mapping of logical qubits that appear in longest repeating non-overlappings of qubit pairs accessed. We compare our new mapping scheme against two quantum compilers and two device topologies.
  arXiv  Detail & Related papers  (2021-11-05T20:07:57Z)
• Effective and Fast: A Novel Sequential Single Path Search for Mixed-Precision Quantization [45.22093693422085]
  Mixed-precision quantization model can match different quantization bit-precisions according to the sensitivity of different layers to achieve great performance. It is a difficult problem to quickly determine the quantization bit-precision of each layer in deep neural networks according to some constraints. We propose a novel sequential single path search (SSPS) method for mixed-precision quantization.
  arXiv  Detail & Related papers  (2021-03-04T09:15:08Z)
• 2D Qubit Placement of Quantum Circuits using LONGPATH [1.6631602844999722]
  Two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. Our approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
  arXiv  Detail & Related papers  (2020-07-14T04:09:52Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.