Parallelizable Exact Synthesis of Quantum Circuits via Semi-Tensor Product

AI summary

Overview

Research area: Quantum circuit synthesis and compilation, specifically exact synthesis of CNOT (linear) and phase polynomial (CNOT + $R_z$) circuits, using the semi-tensor product (STP) theory of matrices.

Technical level: Advanced. Readers need familiarity with quantum gates, parity matrices over $\mathbb{F}_2$, phase polynomials, and SAT-based synthesis to follow the technical sections, though the high-level two-stage architecture is accessible.

Scope: One-sentence summary: the paper proposes a parallelizable two-stage exact synthesis framework that enumerates CNOT circuit topologies and then solves each topology with an STP-based circuit solver, reporting up to 12.8× parallel speedup and a median 3.41× speedup on QASMBench.

What This Paper Is About

Exact synthesis finds a provably optimal (minimum-gate) circuit for a given target and is routinely used as a re-synthesis kernel on small circuit windows, but existing methods are limited: SAT-based encodings carry substantial overhead and parallelize poorly, while database-based methods need huge precomputed tables. The paper's goal is an exact synthesis framework for CNOT and phase polynomial circuits that has low encoding overhead, no large lookup tables, and that exposes parallelism naturally across independent circuit topologies. The authors build this by combining topology enumeration with a new circuit solver derived from semi-tensor product matrix factorization.

Key Contributions

1. A two-stage exact synthesis framework for CNOT circuits, extended to phase polynomial circuits. The first stage enumerates candidate circuit topologies (interacting qubit pairs treated as undirected partial gates); the second stage instantiates each topology into a concrete circuit. The framework is described as avoiding heavy encoding overhead, not relying on large precomputed tables, and naturally exposing parallelism across independent topologies.

2. An STP-based circuit solver tailored to CNOT synthesis. Each topology is encoded as a canonical STP expression, and CNOT gates are synthesized through right-to-left STP matrix factorization that progressively eliminates infeasible gate decisions. The solver is reported to achieve more than 500× speedup over the SAT solver for single-topology solving in most tested configurations.

3. Synthesis-specific optimization techniques. These cover topology pruning and a CNOT-specific STP factorization simplification (presented as a theorem). The pruning strategies are reported to eliminate more than 99.5% of candidate topologies in representative cases.

4. Evaluation on both random targets and real-world circuits. On random targets the method is typically 100–1000× faster than Qiskit-SAT on small and moderately difficult instances and remains competitive on harder ones; on QASMBench the STP-based optimization workflow achieves a median 3.41× speedup over the SAT-based baseline under a matched worker budget.

Main Findings

• Parallel scalability: The proposed 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.

• Per-topology solver speed: The STP-based solver achieves more than 500× speedup over the SAT solver for single-topology solving in most tested configurations.

• Random-target comparison: On randomly generated synthesis targets, the algorithm is typically 100× to 1000× faster than the SAT-based approach (Qiskit-SAT) on small and moderately difficult instances, and remains competitive for more difficult instances.

• Pruning effectiveness: The proposed pruning strategies eliminate more than 99.5% of candidate topologies in representative cases, which is central to keeping enumeration tractable.

• Real-workflow impact: When integrated into a real-world circuit optimization workflow, the algorithm achieves a median speedup of 3.41× on the QASMBench benchmark.

• Hardness context: The problem is NP-hard even when restricted to CNOT + $R_z$ circuits, so the reported gains are algorithmic and engineering gains in practice rather than a complexity-theoretic breakthrough; the paper frames the contribution explicitly as "despite the NP-hardness of the problem."

• Not reported in the provided text: the full experimental setup (hardware, exact qubit counts, timeouts, per-benchmark tables) and the contents of the proofs lie beyond the truncation point of the supplied content, so those specifics are not stated here.

Methodology in Plain English

A pure CNOT circuit acts as a linear map over bits, so it can be written as a parity matrix over $\mathbb{F}_2$; adding $R_z$ gates produces a phase polynomial circuit described by a parity matrix sketch plus a phase polynomial. The authors exploit this structure in two stages.

First, instead of guessing gates with fixed directions, they enumerate topologies: sets of qubit pairs that interact, where each pair is left as an undirected "partial gate" whose control and target are not yet decided. This converts a combinatorial gate-placement problem into a smaller problem of choosing an interaction pattern.

Second, for each surviving topology, they call a solver that decides the direction of every partial gate. The solver encodes the topology as a canonical expression in semi-tensor product algebra — a matrix product framework that is convenient for expressing and manipulating multi-qubit operations — and then factors the target matrix from right to left, discarding gate-direction choices as soon as they are shown to be infeasible rather than searching them blindly.

Because different topologies are enumerated and solved independently, both stages can be spread across workers with little coordination. Aggressive pruning removes the vast majority of candidate topologies before the solver runs, and a CNOT-specific simplification of the STP factorization keeps the per-topology solve cheap. The same architecture is then extended to phase polynomial circuits, where the CNOT skeleton is synthesized and $R_z$ phases are handled within the same framework.

Why This Matters

Impact on research: Exact synthesis is used as a rewriting kernel inside larger optimization flows, so its speed and memory profile directly determine how often it can be invoked. This work offers an algebraic alternative to SAT encodings and to memory-hungry precomputed databases, and it demonstrates that exact synthesis workloads can be parallelized across topologies — a property the paper reports SAT-based methods lack (below 5× speedup with the same 32-worker budget).

Real-world applications (as grounded in the paper's framing):

• NISQ compilation: shorter circuits mean lower error rates and higher success rates on noisy hardware, and CNOT gates are described as much more expensive and error-prone than single-qubit gates, making CNOT reduction a central optimization target.
• Circuit re-synthesis passes: embedding the solver as an optimization kernel on small circuit windows, analogous to its use in classical logic synthesis.
• Parity-matrix / linear circuit optimization: optimizing CNOT skeletons of arithmetic and parity-based subroutines.
• Phase polynomial optimization: handling CNOT + $R_z$ subcircuits, the gate set targeted by the framework's extension.

Industry relevance: Compiler and SDK teams (the baseline is Qiskit-SAT), quantum cloud providers, and hardware vendors who need fast, low-memory optimization passes that scale across many cores rather than requiring enormous lookup tables.

Future Directions

• Scaling to harder instances: the method is reported as competitive but not dominant on harder random targets, so improving the solver and pruning on difficult cases is a natural next step.
• Broadening the gate set: the framework is developed for CNOT and CNOT + $R_z$ (phase polynomial) circuits; extending the STP formulation to other gate libraries is an open question this work raises.
• Tighter workflow integration: the QASMBench result (median 3.41×) comes from one integration; how best to schedule and combine the exact kernel with heuristic optimization passes at larger circuit scales is unresolved.
• Deeper parallel and distributed engineering: the reported 12.8× with 32 workers leaves room to study scheduling, load balancing, and topology-ordering heuristics to push parallel efficiency further.

Target Audience

Researchers and graduate students working on quantum circuit synthesis, quantum compilation, and quantum-assisted logic synthesis/EDA, as well as compiler engineers who build optimization passes and want a low-overhead, parallel exact-synthesis kernel as an alternative to SAT-based or database-based approaches. Readers without background in parity matrices, phase polynomials, or semi-tensor product algebra will find the technical sections demanding, but the two-stage architecture and the benchmark results are readable at an intermediate level.

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