Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search
- 27 January 2020
- 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. 39 (12) , 4683-4694
Abstract
Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom and arbitrarily long coherence time. In Noisy Intermediate-Scale Quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and therefore cause further decay of the performance of a quantum circuit. Thus it is crucial to minimize the number of added gates. In this paper, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. Experimental results on extensive realistic circuits confirm that the proposed method is efficient and the number of added gates of our algorithm is, on average, only 57% of that of state-of-the-art algorithms on IBM Q20 (Tokyo), the most recent IBM quantum device.Keywords
All Related Versions
Funding Information
- National Key Research and Development Program of China (2018YFA0306704)
- Australian Research Council (DP180100691)
This publication has 18 references indexed in Scilit:
- Computer-aided design for quantum computation2018
- 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 software methodology for compiling quantum programsQuantum Science and Technology, 2018
- Temporal Planning for Compilation of Quantum Approximate Optimization Circuits2017
- Building logical qubits in a superconducting quantum computing systemnpj Quantum Information, 2017
- Quantum Networking2014
- Elementary gates for quantum computationPhysical Review A, 1995
- Routing Permutations on Graphs via MatchingsSIAM Journal on Discrete Mathematics, 1994
- Optimization by Simulated AnnealingScience, 1983