Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Li, S; Zhou, X; Feng, Y

Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Li, S

Zhou, X Feng, Y

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Journal Article
Citation:: IEEE Transactions on Computers, 2021, 70, (11), pp. 1-1
Issue Date:: 2021-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 30 Nov 2023

Adobe PDF

Download Accepted versionAdobe PDF (778.3 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546
dc.contributor.author	Zhou, X
dc.contributor.author	Feng, Y https://orcid.org/0000-0002-3097-3896
dc.date.accessioned	2022-04-12T22:02:38Z
dc.date.available	2022-04-12T22:02:38Z
dc.date.issued	2021-01-01
dc.identifier.citation	IEEE Transactions on Computers, 2021, 70, (11), pp. 1-1
dc.identifier.issn	0018-9340
dc.identifier.issn	2326-3814
dc.identifier.uri	http://hdl.handle.net/10453/156145
dc.description.abstract	Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most useful swap combination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.
dc.language	English
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation	http://purl.org/au-research/grants/arc/DP180100691
dc.relation.ispartof	IEEE Transactions on Computers
dc.relation.isbasedon	10.1109/tc.2020.3023247
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject	0803 Computer Software, 0805 Distributed Computing, 1006 Computer Hardware
dc.subject.classification	Computer Hardware & Architecture
dc.title	Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search
dc.type	Journal Article
utslib.citation.volume	70
utslib.for	0803 Computer Software
utslib.for	0805 Distributed Computing
utslib.for	1006 Computer Hardware
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	*
pubs.consider-herdc	false
utslib.copyright.embargo	2023-11-30T00:00:00+1000Z
dc.date.updated	2022-04-12T22:02:34Z
pubs.issue	11
pubs.publication-status	Published
pubs.volume	70
utslib.citation.issue	11

Abstract:

Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most useful swap combination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.

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

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