Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

• URL: http://arxiv.org/abs/2210.01306v5
• Date: Sat, 3 Aug 2024 14:34:36 GMT
• Title: Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
• Authors: Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo, Ren-Chu Wang, Hao-Chung Cheng, Chung-Yang Ric Huang,
• Abstract summary: 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.
• Score: 11.391158217994782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Qubit Mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this paper, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, the Limitedly-Exhausitive (LE) Search and the Shortest-Path (SP) Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm's superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t|ket>, Qiskit and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t|ket>, Qiskit, and SABRE, respectively.

Related papers

• 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)
• 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)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• 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)
• Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing [15.018468499770242]
  Near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. A quantum compiler needs to perform qubit routing to make the circuit compatible with device layout. In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should textitnot be independent on subsequent gate optimizations.
  arXiv  Detail & Related papers  (2022-05-21T13:36:44Z)
• 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)
• 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)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization. We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming. This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• Purification and Entanglement Routing on Quantum Networks [55.41644538483948]
  A quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users. We introduce effectives enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network.
  arXiv  Detail & Related papers  (2020-11-23T19:00:01Z)
• 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)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)

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.