Qubit Mapping Toward Quantum Advantage

Qubit Mapping is an essential step in realizing quantum circuits on actual hardware devices. However, due to the high complexity of this problem, current solutions can only work on circuits in fairly small scales (i.e. $<50$ qubits). In this paper, we propose a qubit mapping methodology which, to the best of our knowledge, is the first framework to handle very large quantum circuits (i.e. thousands of qubits) towards the quantum advantage. Our novel routing algorithm, Duostra, can efficiently identify the optimal routing path for a given two-qubit gate to operate on physical qubits through swap-gate insertions, and our scheduling heuristic offers the flexibility to strike the balance in optimizing the performance and pursuing the scalability. Experimental results show that our method runs $10$ times faster than the state-of-the-art approaches, while on average can still outperform them by over $5\%$ in terms of the execution time of the quantum circuits. More specifically, our proposed algorithm can complete the qubit mapping of an $11,969$-qubit Quantum Fourier Transform circuit within five hours.