A multi-commodity network model for optimal quantum reversible circuit synthesis

Jihye Jung, In Chan Choi

Research output: Contribution to journalArticlepeer-review


Quantum computing is a newly emerging computing environment that has recently attracted intense research interest in improving the output fidelity, fully utilizing its high computing power from both hardware and software perspectives. In particular, several attempts have been made to reduce the errors in quantum computing algorithms through the efficient synthesis of quantum circuits. In this study, we present an application of an optimization model for synthesizing quantum circuits with minimum implementation costs to lower the error rates by forming a simpler circuit. Our model has a unique structure that combines the arcsubset selection problem with a conventional multi-commodity network flow model. The model targets the circuit synthesis with multiple control Toffoli gates to implement Boolean reversible functions that are often used as a key component in many quantum algorithms. Compared to previous studies, the proposed model has a unifying yet straightforward structure for exploiting the operational characteristics of quantum gates. Our computational experiment shows the potential of the proposed model, obtaining quantum circuits with significantly lower quantum costs compared to prior studies. The proposed model is also applicable to various other fields where reversible logic is utilized, such as low-power computing, fault-tolerant designs, and DNA computing. In addition, our model can be applied to network- based problems, such as logistics distribution and time-stage network problems.

Original languageEnglish
Article numbere0253140
JournalPloS one
Issue number6 June
Publication statusPublished - 2021 Jun

Bibliographical note

Funding Information:
This research was supported by the Basic Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science and ICT(MSIT).(No. 2020R1A4A307986411) This research was also supported by the NRF grant funded by the Korea government(MSIT). (No. 2017R1E1A1A0307098814) Both funding is received by professor IC Choi, the corresponding author. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. National Research Foundation of Korea(NRF): https://www.nrf.re.kr/ eng/index Ministry of Science and ICT(MSIT): https://english.msit.go.kr/eng/index.do.

Publisher Copyright:
© 2021 Jung, Choi. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

ASJC Scopus subject areas

  • General


Dive into the research topics of 'A multi-commodity network model for optimal quantum reversible circuit synthesis'. Together they form a unique fingerprint.

Cite this