Parallelizable Exact Synthesis of Quantum Circuits via Semi-Tensor Product
2026-07-27 • Emerging Technologies
Emerging Technologies
AI summaryⓘ
The authors present a new way to exactly build small quantum circuits more efficiently by using a math tool called the semi-tensor product. Their method splits the problem into parts that can be done at the same time, making it faster and easier to handle than previous approaches. They tested their method on random examples and in real-world circuit improvements, finding it often works much faster than older techniques. Overall, their approach helps optimize quantum circuits more quickly and with less computing hassle.
exact synthesisquantum compilationCNOT circuitsphase polynomial circuitssemi-tensor productparallel computingSAT-based methodscircuit optimization
Authors
Chenjian Li, Dingchao Gao, Xiangzhen Zhou, Ji Guan, Pengcheng Zhu, Zhufei Chu
Abstract
Exact synthesis is a useful tool in quantum compilation by providing optimal alternative implementations of small circuit shards and is widely used as a circuit re-synthesis optimization kernel. However, existing exact synthesis methods suffer from encoding overhead, poor parallel scalability, and memory bottlenecks. This paper introduces a parallel exact synthesis framework for CNOT and phase polynomial circuits, which is based on the semi-tensor product (STP) theory of matrices. By enumerating undirected partial-gate topologies and solving the missing gate directions separately, we are able to parallelize both stages and achieve a parallel speedup of up to $12.8\times$ with 32 workers on this NP-hard problem. More specifically, for each topology, the circuit semantics are converted into canonical STP formulas, and feasibility is decided by a right-to-left factorization procedure that removes infeasible direction assignments. On randomly generated synthesis targets, STP is typically $100\times-1000\times$ faster than the SAT-based baseline on small instances, and remains competitive for more difficult instances. When integrated in a real-world circuit optimization workflow, our algorithm outperforms the SAT-based approach on 89% of cases in QASMBench, and achieves a median speedup of $1.91\times$.