Aug 2026· Quantum Reports· Vol 8, pp. 79· 0 citations· 11 references
TL;DR
A unified, highly scalable methodology for the optimal design of reversible circuits across both libraries is presented, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.
Abstract
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing (FTQC). The primary motivation of this work is to overcome the inherent disadvantages of existing synthesis techniques: approximate heuristic methods often miss optimal solutions, while pure exact computational methods suffer from combinatorial explosion on deep circuits. While the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary gates, standard physical implementations frequently utilize the broader NCV library (NOT, CNOT, V, V-dagger), requiring the decomposition of Toffoli gates into five elementary operations. To bridge this gap, this paper presents a unified, highly scalable methodology for the optimal design of reversible circuits across both libraries. First, a Mixed-Integer Non-Linear Programming (MINLP) formulation, linearized for the high-performance IBM ILOG CPLEX solver, is introduced to automate the exact generation of globally optimal strict NCT topologies. Second, a systematic four-phase optimization framework is proposed to reduce NCV costs. By replacing Toffoli gates with specific NCV decompositions, permuting control lines to match subsequent linear gates, and applying exact local searches via an extended MINLP solver on bounded sliding windows, significant gate cancellations are achieved. Applying this methodology to prominent primitives (MIG, SAYEM, URG, TSG, and MKG), we match global NCT optimality constraints and achieve highly optimized NCV Quantum Costs of 7, 14, and 12 for the MIG, TSG, and MKG gates, respectively, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.
A measurement of what diagrammatic post-processing recovers from structural redundancy in the Solovay-Kitaev algorithm, which optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see.
Dulari De Silva, A. Mahasinghe, Chon-Fai Kam et al.· 0 citations
The multi-controlled Toffoli (MCT) gate is a fundamental primitive in quantum circuit design, with applications in quantum arithmetic, cryptanalysis, and algorithmic implementations. Being a high-level logical operation, the efficient decomposition of MCT gates into lower-level netlists has remained a major optimization challenge for decades. While emerging quantum error-correcting codes such as bivariate bicycle (BB) codes drastically reduce fault-tolerance overhead, realizing non-Clifford circuits on modular BB-code architectures introduces complex compilation bottlenecks governed by inter-module routing, factory density, and layout. Consequently, the mapping of MCT gates onto BB-code architectures remains relatively unexplored. In this paper, we overcome these challenges by mapping optimal-Toffoli-depth MCT decompositions (Dutta et al., PRA, 2025) onto BB-code-based fault-tolerant architectures via direct $\lvert \mathrm{CCZ} \rangle$ state injection from an external magic state factory. We introduce a targeted placement strategy that exploits the binary-tree structure of MCT decompositions to co-locate interacting subtrees. This approach reduces inter-module instruction counts by up to $\mathbf{16.02}\%$ compared to a naive sequential first-fit placement. We also evaluate the impact of factory placement across different topologies, demonstrating that grid-based layouts yield up to a $\mathbf{23.7}\%$ reduction in inter-module instructions relative to linear architectures (Yoder et al., arXiv, 2025). Finally, we validate the practical viability of our compiled circuits by analyzing aggregate execution errors and logical failure probabilities using the bicycle-ISA error estimator bicycle_numerics provided by the Qiskit community, https://github.com/qiskit-community/bicycle-architecture-compiler.
A. Bhaumik, Suman Dutta, Siyi Wang et al.· 0 citations
Here it is shown that minimized expressions retain algebraic structure minimization cannot reach, arising from containment and complementary-polarity relationships among their terms, and that extracting it yields circuits cheaper to execute despite having more operations.
Mehul A. Shah, Robert Fiszer, M. Perkowski· 0 citations
This work considers the case where both non-local and local connectivity may be arbitrarily restricted, and gives an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination.
Exact synthesis is a key infrastructure in quantum circuit synthesis and optimization, which provides optimal implementations of small circuit shards and is widely used as a circuit re-synthesis optimization kernel. However, existing quantum exact synthesis methods suffer from encoding overhead, memory bottlenecks, and poor parallel scalability. In this work, we introduce a parallel exact synthesis framework for CNOT and phase polynomial circuits based on the semi-tensor product (STP) theory of matrices that avoids these issues. The algorithm contains two stages: it first enumerates candidate circuit topologies, and then instantiates each topology by determining the control and target qubit of its partial gates via a STP-based circuit solver. In the second stage, circuit topologies are encoded as canonical STP expressions, and the CNOT gates are synthesized through right-to-left STP matrix factorization that progressively eliminates infeasible gate decisions. In the framework, topology enumeration and the subsequent solving process are independent across different topologies, and can be naturally parallelized. Despite the NP-hardness of the problem, our algorithm yields up to $12.8\times$ parallel speedup with 32 workers, whereas the parallel speedups of existing SAT-based methods remain below $5\times$ with the same worker budget. On randomly generated synthesis targets, the proposed algorithm is typically $100$-$1000\times$ faster than the SAT-based approach on small and moderately difficult instances, and remains competitive for more difficult instances. When integrated in a real-world circuit optimization workflow, our algorithm achieves a median speedup of $3.41\times$ on the QASMBench benchmark.
