Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms

• URL: http://arxiv.org/abs/2310.09826v3
• Date: Mon, 29 Jul 2024 15:25:34 GMT
• Title: Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms
• Authors: Yanjun Ji, Xi Chen, Ilia Polian, Yue Ban,
• Abstract summary: 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.
• Score: 3.990724104767043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum algorithms implemented on near-term devices require qubit mapping due to noise and limited qubit connectivity. In this paper we propose a strategy called algorithm-oriented qubit mapping (AOQMAP) that aims to bridge the gap between exact and scalable mapping methods by utilizing the inherent structure of algorithms. While exact methods provide optimal solutions, they become intractable for large circuits. Scalable methods, like SWAP networks, offer fast solutions but lack optimality. AOQMAP bridges this gap by leveraging algorithmic features and their association with specific device substructures to achieve optimal and scalable solutions. The proposed strategy follows a two stage approach. First, it maps circuits to subtopologies to meet connectivity constraints. Second, it identifies the optimal qubits for execution using a cost function. Notably, AOQMAP provides both scalable and optimal solutions for variational quantum algorithms with fully connected two qubit interactions on common subtopologies including linear, T-, and H-shaped, minimizing circuit depth. Benchmarking experiments conducted on IBM quantum devices demonstrate significant reductions in gate count and circuit depth compared to Qiskit, Tket, and SWAP network. Specifically, AOQMAP achieves up to an 82% reduction in circuit depth and an average 138% increase in success probability. This scalable and algorithm-specific approach holds the potential to optimize a wider range of quantum algorithms.

Related papers

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