Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search

Zhou, X; Li, S; Feng, Y

Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search

Zhou, X Li, S

Feng, Y

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020
Issue Date:: 2020-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 1 Jan 2022

Adobe PDF

Download Accepted ManuscriptAdobe PDF (541.36 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhou, X	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Feng, Y https://orcid.org/0000-0002-3097-3896	en_US
dc.date.issued	2020-01-01	en_US
dc.identifier.citation	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020	en_US
dc.identifier.issn	0278-0070	en_US
dc.identifier.uri	http://hdl.handle.net/10453/139112
dc.description.abstract	IEEE 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.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP180100691
dc.relation.ispartof	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems	en_US
dc.relation.isbasedon	10.1109/TCAD.2020.2969647	en_US
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject.classification	Computer Hardware & Architecture	en_US
dc.title	Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search	en_US
dc.type	Journal Article
utslib.for	0906 Electrical and Electronic Engineering	en_US
utslib.for	1006 Computer Hardware	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
utslib.copyright.embargo	2022-01-01T00:00:00+1100
pubs.publication-status	Published	en_US

Abstract:

IEEE 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/139112