Algorithm-oriented qubit mapping for variational quantum algorithms

• URL: http://arxiv.org/abs/2310.09826v2
• Date: Wed, 24 Jan 2024 13:48:18 GMT
• Title: Algorithm-oriented qubit mapping for variational quantum algorithms
• Authors: Yanjun Ji, Xi Chen, Ilia Polian, Yue Ban
• Abstract summary: We present an algorithm-oriented qubit mapping (AOQMAP) that capitalizes on the inherent regular substructures within quantum algorithms. AOQMAP achieves up to 82.1% depth reduction and a 138% average increase in success probability compared to Qiskit, Tket, and SWAP network.
• Score: 4.359579392793038
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing qubit mapping is critical for the successful implementation of algorithms on near-term quantum devices. In this paper we present an algorithm-oriented qubit mapping (AOQMAP) that capitalizes on the inherent regular substructures within quantum algorithms. While exact methods provide optimal solutions, their exponential scaling renders them impractical. AOQMAP addresses this challenge through a strategic two-step approach. First, it adapts circuits onto subtopologies of the target quantum device to satisfy connectivity constraints. Optimal and scalable solutions with minimum circuit depth are provided for variational quantum algorithms with all-to-all connected interactions on linear, T-shaped, and H-shaped subtopologies. Second, it identifies the optimal mapping scheme by using a cost function based on current device noise. Demonstrations on various IBM quantum devices indicate that AOQMAP significantly reduces both gate count and circuit depth compared to traditional mapping approaches, consequently enhancing performance. Specifically, AOQMAP achieves up to 82.1% depth reduction and a 138% average increase in success probability compared to Qiskit, Tket, and SWAP network. This specialized and scalable mapping paradigm can potentially optimize broader quantum algorithm classes. Tailoring qubit mapping to leverage algorithmic features holds the promise of maximizing the performance of near-term quantum algorithms.

Related papers

• TANGO: A Robust Qubit Mapping Algorithm via Two-Stage Search and Bidirectional Look [7.064817742048067]
  Current quantum devices lack full qubit connectivity, making it difficult to directly execute logical circuits on quantum devices. We propose the TANGO algorithm, which balances the impact of qubit mapping on both mapped and unmapped nodes. We show that the algorithm achieves multi-objective co-optimization of gate count and circuit depth across various benchmarks and quantum devices.
  arXiv  Detail & Related papers  (2025-03-10T13:44:16Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods. We present an analysis of the non-asymptotic resource requirements of a quantum SDP solver.
  arXiv  Detail & Related papers  (2025-02-21T12:54:05Z)
• An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction [7.698997402561804]
  Current quantum devices support interactions only between physically adjacent qubits, preventing quantum circuits from being directly executed on these devices.<n>To minimize the insertion of additional SWAP gates, we propose HAIL, an efficient iterative qubit mapping algorithm.<n>We show that HAIL-3 reduces the number of additional gates inserted in the $mathcalB_23$ by 20.62% compared to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2025-02-11T13:21:33Z)
• A Fast and Adaptable Algorithm for Optimal Multi-Qubit Pathfinding in Quantum Circuit Compilation [0.0]
  This work focuses on multi-qubit pathfinding as a critical subroutine within the quantum circuit compilation mapping problem. We introduce an algorithm, modelled using binary integer linear programming, that navigates qubits on quantum hardware optimally with respect to circuit SWAP-gate depth. We have benchmarked the algorithm across a variety of quantum hardware layouts, assessing properties such as computational runtimes, solution SWAP depths, and accumulated SWAP-gate error rates.
  arXiv  Detail & Related papers  (2024-05-29T05:59:15Z)
• Single-Qubit Gates Matter for Optimising Quantum Circuit Depth in Qubit Mapping [4.680722019621822]
  We propose a simple and effective method that takes into account the impact of single-qubit gates on circuit depth. Our method can be combined with many existing QCT algorithms to optimise circuit depth. We demonstrate the effectiveness of our method by embedding it in SABRE, showing that it can reduce circuit depth by up to 50% and 27% on average.
  arXiv  Detail & Related papers  (2023-08-01T23:16:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits [11.391158217994782]
  Duostra is tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices. It operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates. It yields results of good quality within a reasonable runtime.
  arXiv  Detail & Related papers  (2022-10-04T01:47:11Z)
• Wide Quantum Circuit Optimization with Topology Aware Synthesis [0.8469686352132708]
  Unitary synthesis is an optimization technique that can achieve optimal multi-qubit gate counts while mapping quantum circuits to restrictive qubit topologies. We present TopAS, a topology aware synthesis tool built with the emphBQSKit framework that preconditions quantum circuits before mapping.
  arXiv  Detail & Related papers  (2022-06-27T21:59:30Z)
• 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)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• 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)

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.