An exact qubit allocation approach for NISQ architectures
- PDF / 1,332,895 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 197 Views
An exact qubit allocation approach for NISQ architectures Pengcheng Zhu1,2
· Xueyun Cheng1 · Zhijin Guan1
Received: 23 April 2020 / Accepted: 20 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The noisy intermediate-scale quantum (NISQ) devices that have just emerged in recent years provide an opportunity for the physical realization of quantum circuits. As the first step of mapping quantum circuits to these devices, qubit allocation imposes a great impact on the number of additional quantum operations required throughout the mapping. The global optimization of qubit allocation is NP-hard, but since many current NISQ devices have very few qubits, it is possible to solve this problem exactly. In this paper, we propose an exact approach for qubit allocation, which takes advantage of the branch and bound algorithm as the basic framework. In order to further prune the considerably huge state space, three techniques have been proposed and integrated into the exact approach, including an optimized lower bound for quadratic assignment problem, prioritization of logical qubits, and branch pruning by structural symmetry of physical qubits. Moreover, based on the multiple optimal solutions obtained by the exact approach, we give an error-aware qubit allocation method. For problems that are too large to be solved by the exact approach, we also give a heuristic qubit allocation approach with polynomial time complexity. Experimental evaluations show that the exact approach proposed in this paper is feasible for the qubit allocation of current NISQ architectures. For all benchmarks considered, this exact approach can find multiple optimal solutions to the qubit allocation problem on IBM Melbourne, a 16-qubit NISQ architecture, in no more than 20 min. It can serve as a evaluation baseline of any heuristic approach. Experimental evaluations also show that the proposed heuristic approach is near-optimal in terms of routing cost. Both the exact approach and the heuristic approach can be integrated into existing quantum circuit mapping approaches. Keywords Quantum circuit · Qubit allocation · Exact approach · Noisy intermediate-scale quantum (NISQ) · Quantum circuit mapping
This work was supported by the National Natural Science Foundation of China under Grant 61402244, in part by Jiangsu Province Natural Science Foundation of China under Grant BK20151274, in part by Suqian Science and Technology Foundation under Grant H201721. Extended author information available on the last page of the article 0123456789().: V,-vol
123
391
Page 2 of 21
P. Zhu et al.
1 Introduction Quantum computing (QC) is a frontier interdiscipline which brings together ideas from quantum physics, classical computer science, and information theory. The manufacture of general-purpose quantum computers has always been one of the frontiers in the field of quantum computing. In particular, in recent years, with the emergence of a few NISQ (noisy intermediate-scale quantum) [23] devices, the preparation of quantum c
Data Loading...
