Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.24195

Parallelizable Exact Synthesis of Quantum Circuits via Semi-Tensor Product

Chenjian Li, Dingchao Gao, Xiangzhen Zhou, Ji Guan, Pengcheng Zhu, Zhufei Chu

quant-phcs.ETSubmitted Jul 27, 2026• Announced Jul 28, 2026• 0 citations• Revised Aug 16, 2026 (v2)
v1 · Jul 27, 2026v2 · Aug 16, 2026
arXivHTMLPDF

Abstract

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.

Related papers

Provably optimal exact gate synthesis from a discrete gate set

Élie Gouzien, Nicolas Sangouard

We propose a method for exact circuit synthesis using a discrete gate set, as required for fault-tolerant quantum computing. Our approach translates the problem of synthesizing a gate specified by its unitary matrix into a boolean satisfiability (SAT) instance. It leverages the algebraic properties of the coefficients of the matrices that constitute the gate set, enabling the transformation of the constraint of equality between complex matrices into a boolean expression to satisfy. For a specified number of gates, the SAT solver finds a circuit implementing the target or proves that none exist. Optimality of the number of gates is proven by iterating on the number of gates. We also propose some extensions of the method, for example, handling ancillary qubits, post-selection, or classical feedback. The time-to-solution scales double-exponentially with the number of qubits, making it impractical for large circuits. However, since many quantum algorithms rely on small, frequently used subcircuits, and because of the intrinsic value of having a provably optimal circuit synthesis, we believe that our tool are valuable for quantum circuit design.

arXiv:2503.15452•Mar 19, 2025•0 citations

Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

Irfansha Shaik, Jaco van de Pol

Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.

arXiv:2403.11598•Leibniz international proceedings in informatics•Jan 1, 2024•7 citations

Vanilla Exact Synthesis of CNOT Circuits is NP-hard

Chenjian Li, Ji Guan

Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over $\mathrm{GL}(n,2)$ with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.

quant-pharXiv:2609.04160•Sep 4, 2026•0 citations

CNOT-Optimal Clifford Synthesis as SAT

Irfansha Shaik, Jaco van de Pol

Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.

arXiv:2504.00634•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Approximate Quantum Circuit Synthesis for Diagonal Unitary

Wenqi Zhang, Jinyang Liu, Zixiang Zhou +1 more

The quantum circuit synthesis problem bridges quantum algorithm design and quantum hardware implementation in the Noisy Intermediate-Scale Quantum (NISQ) era. In quantum circuit synthesis problems, diagonal unitary synthesis plays a crucial role due to its fundamental and versatile nature. Meanwhile, experimental results have shown that moderately approximating the original algorithm to conserve quantum resources can improve the fidelity of algorithms during quantum execution. Building on this insight, we propose a quantum circuit synthesis algorithm to design diagonal unitary implementations based on specified quantum resource limits. Our algorithm can synthesize diagonal unitary for quantum circuits with up to 15 qubits on an ordinary laptop. In algorithm efficiency, synthesizing an n-qubit unitary matrix with an exact algorithm requires $2^n$ CNOT gates as a baseline. Within the algorithm error $\varepsilon $ range of interest (0\%-12\%), our algorithm achieves a $3.2\varepsilon $ reduction in CNOT gates on average. In runtime, the algorithm efficiently performs, synthesizing 12-qubit diagonal unitary in an average of 6.57 seconds and 15-qubit in approximately 561.71 seconds.

arXiv:2412.01869•Dec 2, 2024•0 citations

HOPPS: Hardware-Aware Optimal Phase Polynomial Synthesis with Blockwise Optimization for Quantum Circuits

Xinpeng Li, Ji Liu, Shuai Xu +2 more

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.

quant-pharXiv:2511.18770•Nov 25, 2025•0 citations
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×12.8\times12.8× parallel speedup with 32 workers, whereas the parallel speedups of existing SAT-based methods remain below 5×5\times5× with the same worker budget. On randomly generated synthesis targets, the proposed algorithm is typically 100100100-1000×1000\times1000× 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×3.41\times3.41× on the QASMBench benchmark.
We propose a method for exact circuit synthesis using a discrete gate set, as required for fault-tolerant quantum computing. Our approach translates the problem of synthesizing a gate specified by its unitary matrix into a boolean satisfiability (SAT) instance. It leverages the algebraic properties of the coefficients of the matrices that constitute the gate set, enabling the transformation of the constraint of equality between complex matrices into a boolean expression to satisfy. For a specified number of gates, the SAT solver finds a circuit implementing the target or proves that none exist. Optimality of the number of gates is proven by iterating on the number of gates. We also propose some extensions of the method, for example, handling ancillary qubits, post-selection, or classical feedback. The time-to-solution scales double-exponentially with the number of qubits, making it impractical for large circuits. However, since many quantum algorithms rely on small, frequently used subcircuits, and because of the intrinsic value of having a provably optimal circuit synthesis, we believe that our tool are valuable for quantum circuit design.
Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over GL(n,2)\mathrm{GL}(n,2)GL(n,2) with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.
Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.
The quantum circuit synthesis problem bridges quantum algorithm design and quantum hardware implementation in the Noisy Intermediate-Scale Quantum (NISQ) era. In quantum circuit synthesis problems, diagonal unitary synthesis plays a crucial role due to its fundamental and versatile nature. Meanwhile, experimental results have shown that moderately approximating the original algorithm to conserve quantum resources can improve the fidelity of algorithms during quantum execution. Building on this insight, we propose a quantum circuit synthesis algorithm to design diagonal unitary implementations based on specified quantum resource limits. Our algorithm can synthesize diagonal unitary for quantum circuits with up to 15 qubits on an ordinary laptop. In algorithm efficiency, synthesizing an n-qubit unitary matrix with an exact algorithm requires 2n2^n2n CNOT gates as a baseline. Within the algorithm error $\varepsilon $ range of interest (0\%-12\%), our algorithm achieves a $3.2\varepsilon $ reduction in CNOT gates on average. In runtime, the algorithm efficiently performs, synthesizing 12-qubit diagonal unitary in an average of 6.57 seconds and 15-qubit in approximately 561.71 seconds.
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.