Timing-Aware Qubit Mapping and Gate Scheduling Adapted to Neutral Atom Quantum Computing
- 27 March 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 42 (11) , 3768-3780
Abstract
As a less developed but potential quantum technology, neutral atoms (NA) can provide advantages including higher qubit connectivity, longer-range interactions, and much more native multi-control gates than superconductivity. Long-range interactions, however, prevent parallelism of interacting qubit pairs with their surrounding restriction zones. Therefore, the quantum program cannot be run directly on a neutral atom quantum computer (NAQC) unless compiled. The recent compiling study of NAQC applies simple layer-by-layer scheduling and does not consider the difference in gate duration. To address the above issues, we focus on the qubit mapping and quantum gate scheduling () problem of quantum circuits to meet hardware constraints of superconductivity and even neutral atoms. Our goal is to shorten the execution time to mitigate decoherence noise. We propose a block-game-like abstraction mechanism which is an abstract model of the problem and aware of the duration difference of gates and several other NA characteristics. Based on the abstraction, we propose a heuristic greedy algorithm (HGA) to solve the problem efficiently. To further speed up the execution of the circuit, we embed HGA into a Monte Carlo tree search (MCTS) framework to solve the problem, which consumes more compiling time but achieves a better result. Comparing our MCTS algorithm with the only recent algorithm for NAQC, the average speedup ratio is 1.75× for several quantum circuits collected from RevLib, and 1.18× for circuits from Qiskit Lib.Keywords
Funding Information
- Innovation Program for Quantum Science and Technology (2021ZD0302300, 2021ZD0302900)
- National Natural Science Foundation of China (62272434)
- Fundamental Research Funds for the Central Universities (WK2060000018)
- National Key Research and Development Program of China (2021YFA1402001)
This publication has 29 references indexed in Scilit:
- Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers2019
- Quantum Computing in the NISQ era and beyondQuantum, 2018
- An Efficient Methodology for Mapping Quantum Circuits to the IBM QX ArchitecturesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018
- A blueprint for demonstrating quantum supremacy with superconducting qubitsScience, 2018
- Temporal Planning for Compilation of Quantum Approximate Optimization Circuits2017
- SyReC: a programming language for synthesis of reversible circuits2010
- BDD-based synthesis of reversible logic for large functions2009
- RevLib: An Online Resource for Reversible Functions and Reversible Circuits37th International Symposium on Multiple-Valued Logic (SMVLL'07), 2008
- Bandit Based Monte-Carlo Planning2006
- On the Complexity of the Hidden Weighted Bit Function for Various BDD ModelsRAIRO - Theoretical Informatics and Applications, 1999