Synthesis of Semi-Classical Quantum Circuits.

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.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.

quant-pharXiv:2607.24195Jul 28, 20260 citations

Synthesis of Quantum Circuits

Philipp Niemann, Robert Wille

SpringerBriefs in physicsJan 1, 20170 citations

Studies on methods for the synthesis of quantum circuits

裕美中島

Jan 1, 20090 citations

Algorithm of Optimizing Quantum Reversible Logic Synthesis

Zhiqiang Li, Wenqian Li, Hanwu Chen

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.

Journal of SoftwareNov 13, 20090 citations

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.