A New Multicommodity Network Flow Model and Branch and Cut for Optimal Quantum Boolean Circuit Synthesis

Jihye Jung () and In-Chan Choi ()
Additional contact information
Jihye Jung: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
In-Chan Choi: Division of Industrial Management Engineering, Korea University, Seoul 02841, Republic of Korea

INFORMS Journal on Computing, 2025, vol. 37, issue 1, 42-62

Abstract: This study introduces a new optimization model and a branch-and-cut approach for synthesizing optimal quantum circuits for reversible Boolean functions, which are pivotal components in quantum algorithms. Although heuristic algorithms have been extensively explored for quantum circuit synthesis, research on exact counterparts remains relatively limited. However, the need to design quantum circuits with guaranteed optimality is increasing, especially for improving computational fidelity on noisy intermediate-scale quantum devices. This study presents mathematical optimization as a viable option for optimal synthesis, with the potential to accommodate practical considerations arising in fast-evolving quantum technologies. We set a demonstrative problem to implement reversible Boolean functions using high-level gates known as multiple control Toffoli gates while minimizing a technology-based proxy called quantum cost—the number of low-level gates used to realize each high-level gate. To address this problem, we propose a discrete optimization model based on a multicommodity network and discuss potential future variations at an abstract level to incorporate technical considerations. A customized branch and cut is then developed upon different aspects of our model, including polyhedron integrality, surrogate constraints, and variable prioritization. Our experiments demonstrate the robustness of the proposed approach in finding cost-optimal circuits for all benchmark instances within a two-hour time frame. Furthermore, we present interesting intuitions from these experiments and compare our computational results with relevant studies, highlighting newly discovered circuits with the lowest quantum costs reported in this paper.

Keywords: mixed-integer programming; multicommodity network; branch and cut; quantum computing; circuit synthesis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0562 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:1:p:42-62

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().