Optimizing quantum circuit placement via machine learning
File(s)
Accepted version
Author(s)
Fan, Hongxiang
Guo, Ce
Luk, Wayne
Type
Conference Paper
Abstract
Quantum circuit placement (QCP) is the process of mapping the
synthesized logical quantum programs on physical quantum ma-
chines, which introduces additional SWAP gates and affects the
performance of quantum circuits. Nevertheless, determining the
minimal number of SWAP gates has been demonstrated to be an
N P-complete problem. Various heuristic approaches have been pro-
posed to address QCP, but they suffer from suboptimality due to the
lack of exploration. Although exact approaches can achieve higher
optimality, they are not scalable for large quantum circuits due to
the massive design space and expensive runtime. By formulating
QCP as a bilevel optimization problem, this paper proposes a novel
machine learning (ML)-based framework to tackle this challenge.
To address the lower-level combinatorial optimization problem, we
adopt a policy-based deep reinforcement learning (DRL) algorithm
with knowledge transfer to enable the generalization ability of our
framework. An evolutionary algorithm is then deployed to solve
the upper-level discrete search problem, which optimizes the ini-
tial mapping with a lower SWAP cost. The proposed ML-based
approach provides a new paradigm to overcome the drawbacks in
both traditional heuristic and exact approaches while enabling the
exploration of optimality-runtime trade-off. Compared with the
leading heuristic approaches, our ML-based method significantly
reduces the SWAP cost by up to 100%. In comparison with the lead-
ing exact search, our proposed algorithm achieves the same level
of optimality while reducing the runtime cost by up to 40 times.
synthesized logical quantum programs on physical quantum ma-
chines, which introduces additional SWAP gates and affects the
performance of quantum circuits. Nevertheless, determining the
minimal number of SWAP gates has been demonstrated to be an
N P-complete problem. Various heuristic approaches have been pro-
posed to address QCP, but they suffer from suboptimality due to the
lack of exploration. Although exact approaches can achieve higher
optimality, they are not scalable for large quantum circuits due to
the massive design space and expensive runtime. By formulating
QCP as a bilevel optimization problem, this paper proposes a novel
machine learning (ML)-based framework to tackle this challenge.
To address the lower-level combinatorial optimization problem, we
adopt a policy-based deep reinforcement learning (DRL) algorithm
with knowledge transfer to enable the generalization ability of our
framework. An evolutionary algorithm is then deployed to solve
the upper-level discrete search problem, which optimizes the ini-
tial mapping with a lower SWAP cost. The proposed ML-based
approach provides a new paradigm to overcome the drawbacks in
both traditional heuristic and exact approaches while enabling the
exploration of optimality-runtime trade-off. Compared with the
leading heuristic approaches, our ML-based method significantly
reduces the SWAP cost by up to 100%. In comparison with the lead-
ing exact search, our proposed algorithm achieves the same level
of optimality while reducing the runtime cost by up to 40 times.
Date Issued
2022-07-01
Date Acceptance
2022-02-21
Citation
DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference, 2022, pp.19-24
ISBN
9781450391429
Publisher
ACM / IEEE
Start Page
19
End Page
24
Journal / Book Title
DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference
Copyright Statement
© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
Source
Design Automation Conference (DAC)
Publication Status
Published
Start Date
2022-07-10
Finish Date
2022-07-14
Coverage Spatial
San Francisco, USA
Date Publish Online
2022-08-23