Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
2210.01306
0
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.
Get summaries of the top AI research delivered straight to your inbox:
Overview
- This paper presents a new algorithm called Duostra for mapping quantum circuits to real hardware devices with limited connectivity.
- The algorithm aims to address the challenges of implementing large-scale quantum circuits on current hardware, which can have hundreds of qubits.
- Duostra efficiently determines optimal paths for double-qubit gates and inserts SWAP gates to enable their implementation on real devices.
- The paper also introduces two heuristic scheduling algorithms, Limitedly-Exhaustive (LE) Search and Shortest-Path (SP) Estimation, to further improve the quality of the mapping.
- Experimental results show that Duostra outperforms existing algorithms, especially for large circuits beyond the NISQ (Noisy Intermediate-Scale Quantum) era.
Plain English Explanation
Quantum computers are still in the early stages of development, and one of the key challenges is getting them to run complex quantum circuits effectively on real hardware. This paper introduces an algorithm called Duostra that helps address this challenge.
The problem is that current quantum hardware has a limited number of qubits (the basic units of quantum information) and they are not all directly connected to each other. This means that when you try to run a quantum circuit with lots of qubits and connections between them, you have to figure out how to "map" that circuit onto the real hardware in a way that works.
Duostra is designed to do this mapping efficiently, especially for large circuits that could have hundreds of qubits. It works by finding the best paths for the double-qubit gates (the connections between qubits) and then inserting extra SWAP gates to make it all fit on the real hardware.
The paper also presents two other algorithms, LE Search and SP Estimation, that help Duostra find even better mappings. When the researchers tested Duostra, they found it outperformed other existing mapping algorithms, especially for large, complex circuits that are beyond the current NISQ era of quantum computing.
Technical Explanation
The key innovation in this paper is the Duostra algorithm, which is designed to efficiently map quantum circuits to real hardware devices with limited connectivity. Duostra operates by determining optimal paths for double-qubit gates and inserting SWAP gates accordingly. This allows the algorithm to implement the desired double-qubit operations on the real hardware.
- Limitedly-Exhaustive (LE) Search: This algorithm explores a limited set of possible mappings to find a high-quality solution efficiently.
- Shortest-Path (SP) Estimation: This algorithm estimates the cost of a mapping by considering the shortest paths between qubits, allowing it to quickly identify promising solutions.
The experimental results demonstrate that Duostra outperforms existing algorithms, especially for large circuits beyond the NISQ era. For example, on circuits with more than 50 qubits, Duostra can reduce the mapping cost by an average of 21.75% compared to the best results from other algorithms like QMAP, t|ket>, Qiskit, and SABRE.
Critical Analysis
The paper presents a promising approach to the challenging problem of mapping quantum circuits to real hardware devices. However, there are a few potential limitations and areas for further research:
- Scalability: While Duostra performs well for large circuits, it would be valuable to further investigate its scalability as the number of qubits continues to increase in the future.
- Hardware diversity: The paper focuses on a specific type of hardware with limited connectivity. It would be interesting to see how Duostra performs on a wider range of quantum hardware architectures.
- Practical considerations: The paper does not address factors like noise, error rates, and the impact of SWAP gates on the overall circuit fidelity. These practical concerns would need to be considered for real-world quantum computing applications.
Overall, the Duostra algorithm and the accompanying heuristic scheduling methods represent a significant contribution to the field of quantum circuit mapping. The promising results suggest that this approach could help unlock the potential of large-scale quantum circuits on current and future hardware platforms.
Conclusion
This paper presents an innovative algorithm called Duostra that addresses the challenge of mapping quantum circuits to real hardware devices with limited connectivity. Duostra efficiently determines optimal paths for double-qubit gates and inserts SWAP gates to enable their implementation on the available hardware.
The paper also introduces two heuristic scheduling algorithms, LE Search and SP Estimation, which further improve the quality of the mapping results. Experimental evaluations show that Duostra outperforms existing algorithms, especially for large circuits beyond the NISQ era.
The research findings have important implications for the development of practical quantum computing systems. By addressing the circuit mapping challenge, Duostra takes a step towards unlocking the potential of large-scale quantum circuits and moving closer to achieving quantum advantage in real-world applications.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Learning to rank quantum circuits for hardware-optimized performance enhancement
Gavin S. Hartnett, Aaron Barbosa, Pranav S. Mundada, Michael Hush, Michael J. Biercuk, Yuval Baum
0
0
We introduce and experimentally test a machine-learning-based method for ranking logically equivalent quantum circuits based on expected performance estimates derived from a training procedure conducted on real hardware. We apply our method to the problem of layout selection, in which abstracted qubits are assigned to physical qubits on a given device. Circuit measurements performed on IBM hardware indicate that the maximum and median fidelities of logically equivalent layouts can differ by an order of magnitude. We introduce a circuit score used for ranking that is parameterized in terms of a physics-based, phenomenological error model whose parameters are fit by training a ranking-loss function over a measured dataset. The dataset consists of quantum circuits exhibiting a diversity of structures and executed on IBM hardware, allowing the model to incorporate the contextual nature of real device noise and errors without the need to perform an exponentially costly tomographic protocol. We perform model training and execution on the 16-qubit ibmq_guadalupe device and compare our method to two common approaches: random layout selection and a publicly available baseline called Mapomatic. Our model consistently outperforms both approaches, predicting layouts that exhibit lower noise and higher performance. In particular, we find that our best model leads to a $1.8times$ reduction in selection error when compared to the baseline approach and a $3.2times$ reduction when compared to random selection. Beyond delivering a new form of predictive quantum characterization, verification, and validation, our results reveal the specific way in which context-dependent and coherent gate errors appear to dominate the divergence from performance estimates extrapolated from simple proxy measures.
4/11/2024
🛠️
Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems
Filip B. Maciejewski, Stuart Hadfield, Benjamin Hall, Mark Hodson, Maxime Dupont, Bram Evert, James Sud, M. Sohaib Alam, Zhihui Wang, Stephen Jeffrey, Bhuvanesh Sundar, P. Aaron Lott, Shon Grabbe, Eleanor G. Rieffel, Matthew J. Reagor, Davide Venturelli
0
0
We develop a hardware-efficient ansatz for variational optimization, derived from existing ansatze in the literature, that parametrizes subsets of all interactions in the Cost Hamiltonian in each layer. We treat gate orderings as a variational parameter and observe that doing so can provide significant performance boosts in experiments. We carried out experimental runs of a compilation-optimized implementation of fully-connected Sherrington-Kirkpatrick Hamiltonians on a 50-qubit linear-chain subsystem of Rigetti Aspen-M-3 transmon processor. Our results indicate that, for the best circuit designs tested, the average performance at optimized angles and gate orderings increases with circuit depth (using more parameters), despite the presence of a high level of noise. We report performance significantly better than using a random guess oracle for circuits involving up to approx 5000 two-qubit and approx 5000 one-qubit native gates. We additionally discuss various takeaways of our results toward more effective utilization of current and future quantum processors for optimization.
5/3/2024
📈
New!An Abstract Model and Efficient Routing for Logical Entangling Gates on Zoned Neutral Atom Architectures
Yannick Stade, Ludwig Schmid, Lukas Burgholzer, Robert Wille
0
0
Recent experimental achievements have demonstrated the potential of neutral atom architectures for fault-tolerant quantum computing. These architectures feature the dynamic rearrangement of atoms during computation, enabling nearly arbitrary two-dimensional rearrangements. Additionally, they employ a zoned layout with dedicated regions for entangling, storage, and readout. This architecture requires design automation software that efficiently compiles quantum circuits to this hardware and takes care that atoms are in the right place at the right time. In this paper, we initiate this line of work by providing, (1) an abstract model of the novel architecture and, (2) an efficient solution to the routing problem of entangling gates. By this, we aim to maximize the parallelism of entangling gates and minimize the overhead caused by the routing of atoms between zones. In addition to that, we keep the realm of fault-tolerant quantum computing in mind and consider logical qubit arrays, each of which encodes one logical qubit. We implemented the proposed idea as a tool called NALAC and demonstrated its effectiveness and efficiency by showing that it can significantly reduce the routing overhead of logical entangling gates compared to the naive approach. As part of the Munich Quantum Toolkit (MQT), NALAC is publicly available as open-source at https://github.com/cda-tum/mqt-qmap.
5/15/2024
Multi Digit Ising Mapping for Low Precision Ising Solvers
Abhishek Kumar Singh, Kyle Jamieson
0
0
The last couple of years have seen an ever-increasing interest in using different Ising solvers, like Quantum annealers, Coherent Ising machines, and Oscillator-based Ising machines, for solving tough computational problems in various domains. Although the simulations predict massive performance improvements for several tough computational problems, the real implementations of the Ising solvers tend to have limited precision, which can cause significant performance deterioration. This paper presents a novel methodology for mapping the problem on the Ising solvers to artificially increase the effective precision. We further evaluate our method for the Multiple-Input-Multiple-Output signal detection problem.
4/9/2024