CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.
Blocks composed of {CNOT, Rz} are ubiquitous in modern quantum applications, notably in circuits such as QAOA ansatzes and quantum adders. After compilation, many of them exhibit large CNOT counts or depths, which lowers fidelity. Therefore, we introduce HOPPS: a SAT-based hardware-aware optimal phase polynomial synthesis algorithm that could generate {CNOT, Rz} blocks with CNOT count or depth optimality.
Sometime {CNOT, Rz} blocks are large, such as in QAOA ansatzes, HOPPS's pursuit of optimality limits its scalability. To address this issue, we introduce an iterative blockwise optimization strategy: large circuits are partitioned into smaller blocks, each block is optimally refined, and the process is repeated for several iterations.
Empirical results show that HOPPS is more efficient comparing with existing near optimal synthesis tools. Used as a peephole optimizer, HOPPS reduces the CNOT count by up to 50.0% and the CNOT depth by up to 57.1% under OLSQ. For large QAOA circuit, after mapping by Qiskit, circuit can be reduced CNOT count and depth by up to 44.4% and 42.4% by our iterative blockwise optimization. Index Terms-Phase Polynomial, Quantum Circuit Synthesis, Quantum Circuit Optimization.
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× parallel speedup with 32 workers, whereas the parallel speedups of existing SAT-based methods remain below
5× with the same worker budget. On randomly generated synthesis targets, the proposed algorithm is typically
100-
1000× 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× on the QASMBench benchmark.