Field |
Value |
Language |
dc.contributor.author |
Zhou, X |
|
dc.contributor.author |
Feng, Y
https://orcid.org/0000-0002-3097-3896
|
|
dc.contributor.author |
Li, S |
|
dc.date.accessioned |
2022-03-31T01:57:42Z |
|
dc.date.available |
2022-03-31T01:57:42Z |
|
dc.date.issued |
2022-02-18 |
|
dc.identifier.citation |
ACM Transactions on Design Automation of Electronic Systems, 2022 |
|
dc.identifier.issn |
1084-4309 |
|
dc.identifier.issn |
1557-7309 |
|
dc.identifier.uri |
http://hdl.handle.net/10453/155744
|
|
dc.description.abstract |
<jats:p>
In Noisy Intermediate-Scale Quantum (NISQ) era, quantum processing units (QPUs) suffer from, among others, highly limited connectivity between physical qubits. To make a quantum circuit
<jats:italic>effectively</jats:italic>
executable, a circuit transformation process is necessary to transform it, with overhead cost the smaller the better, into a functionally equivalent one so that the connectivity constraints imposed by the QPU are satisfied. While several algorithms have been proposed for this goal, the overhead costs are often very high, which degenerates the fidelity of the obtained circuits sharply. One major reason for this lies in that, due to the high branching factor and vast search space, almost all these algorithms only search very
<jats:italic>shallowly</jats:italic>
and thus, very often, only (at most) locally optimal solutions can be reached. In this paper, we propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit transformation problem, which enables the search process to go much deeper. The general framework supports implementations aiming to reduce either the size or depth of the output circuit through introducing SWAP or remote CNOT gates. The algorithms, called MCTS-Size and MCTS-Depth, are polynomial in all relevant parameters. Empirical results on extensive realistic circuits and IBM Q Tokyo show that the MCTS-based algorithms can reduce the size (depth, resp.) overhead by, on average, 66% (84%, resp.) when compared with t|ket
<jats:italic>PLX</jats:italic>
−
<jats:italic>right</jats:italic>
〉., an industrial level compiler.
</jats:p> |
|
dc.language |
en |
|
dc.publisher |
Association for Computing Machinery (ACM) |
|
dc.relation |
http://purl.org/au-research/grants/arc/DP180100691
|
|
dc.relation |
Beijing Baidu Netcom Science and Technology Co Ltd |
|
dc.relation |
http://purl.org/au-research/grants/arc/DP220102059
|
|
dc.relation.ispartof |
ACM Transactions on Design Automation of Electronic Systems |
|
dc.relation.isbasedon |
10.1145/3514239 |
|
dc.rights |
info:eu-repo/semantics/embargoedAccess |
|
dc.rights |
© Xiangzhen Zhou et al 2022. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Design Automation of Electronic Systems, http://doi.org/10.1145/3514239 |
|
dc.subject |
0803 Computer Software, 1006 Computer Hardware |
|
dc.subject.classification |
Design Practice & Management |
|
dc.title |
Quantum Circuit Transformation: A Monte Carlo Tree Search Framework |
|
dc.type |
Journal Article |
|
utslib.for |
0803 Computer Software |
|
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 |
* |
utslib.copyright.embargo |
2022-05-01T00:00:00+1000Z |
|
dc.date.updated |
2022-03-31T01:57:41Z |
|
pubs.publication-status |
Published online |
|