Rapid progress in the physical implementation of quantum comput- ers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being di- rectly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. How- ever, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping prob- lem. Our model can also be extended to practical heuristic algo- rithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor ar- chitecture. We also present a scalable extension of our theoretical model that can be used to solve large quantum circuits.
References
2021
ASPLOS
Time-Optimal Qubit Mapping
Chi Zhang, Ari B. Hayes, Longfei Qiu, and
3 more authors
In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Jun 2021
Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.
@inproceedings{zhangetalasplos21,author={Zhang, Chi and Hayes, Ari B. and Qiu, Longfei and Jin, Yuwei and Chen, Yanhao and Zhang, Eddy Z.},title={Time-Optimal Qubit Mapping},year={2021},isbn={9781450383172},publisher={Association for Computing Machinery},address={New York, NY, USA},doi={10.1145/3445814.3446706},booktitle={Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems},pages={360–374},numpages={15},keywords={Qubit Mapping, Quantum Fourier Transformation, Noisy Intermediate Quantum Computers, NISQ, Quantum Computing, QFT},location={Virtual, USA},series={ASPLOS '21},}