⚛️ quantum physics

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

This paper introduces three families of algorithms for the heuristic and optimal synthesis of CNOT and Clifford circuits that minimize either gate count or circuit depth, demonstrating superior performance over existing methods and providing an open-source implementation.

Original authors: Mark Webster, Stergios Koutsioumpas, Dan E Browne

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mark Webster, Stergios Koutsioumpas, Dan E Browne

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a complex machine out of Lego bricks, but with a twist: the bricks are invisible, and the instructions are written in a language of pure math. This is the world of quantum computing. In this realm, scientists don't just build static structures; they build "circuits" that manipulate the very fabric of reality to solve problems too hard for regular computers. To make these circuits work, they need to perform specific moves, like flipping a switch or swapping two pieces. The most common moves are called "CNOT" gates (think of them as a master switch that flips one piece only if another piece is in a certain state) and "Clifford" gates (a slightly more complex set of moves that includes the master switch plus some special rotations).

Why does this matter? Because these circuits are the backbone of "quantum error correction." Just like a noisy radio signal needs a decoder to make sense of the static, quantum computers are incredibly fragile and prone to mistakes. To fix these mistakes and run useful algorithms, we need to build these circuits as efficiently as possible. The problem is that there are millions of ways to arrange the same set of moves. Some arrangements are like a tangled ball of yarn—long, slow, and prone to breaking. Others are like a sleek, straight line—short, fast, and reliable. The goal is to find the shortest, most efficient path to get the job done, because in the quantum world, every extra step increases the chance of an error ruining the whole calculation.

Now, enter a team of researchers from University College London who decided to tackle this tangle of Lego bricks with a new set of tools. They didn't just want to find a way to build these circuits; they wanted to find the best way, or at least a way that was significantly better than what everyone else was using. They developed three different strategies, each designed for a different size of the puzzle.

First, for the smallest puzzles (involving up to 7 qubits, or quantum bits), they created an "Optimal" method. Imagine this as a super-slow, super-detailed mapmaker who checks every single possible path through a maze to guarantee they found the absolute shortest route. They built a massive database of all possible "shortcuts" by grouping together paths that look different but are actually the same when you rotate or flip the board. This allowed them to instantly look up the best solution for small problems, beating previous methods in speed and efficiency.

For medium-sized puzzles, they used an "A*" strategy. Think of this as a smart hiker with a compass. The hiker doesn't check every single path, but they use a clever guess (a "heuristic") to estimate which direction looks most promising. They keep a list of potential paths, always picking the one that looks closest to the finish line. The researchers found that by using a specific type of math to make these guesses, their hiker could find paths that were almost as short as the perfect mapmaker's routes, but much faster to find.

Finally, for the giant, massive puzzles (dozens of qubits), they used a "Greedy" approach. This is like a hiker who looks only at the step immediately in front of them and always takes the one that seems to reduce the distance the most right now. Usually, this kind of "short-sighted" thinking gets you stuck in a dead end (a local minimum), but the team invented a new way of looking at the map. Instead of just counting steps, they looked at the "shape" of the problem using a vector (a list of numbers) that helped them avoid dead ends. This method consistently produced shorter circuits than the best existing tools, like those from Qiskit or Rustiq, especially for large systems.

The results are impressive. When they tested their methods on random circuits and specific error-correction codes (like the famous Golay code), their algorithms consistently used fewer "entangling" two-qubit gates—the most expensive and error-prone parts of the circuit—than any other method currently available. For the Golay code, they even found a circuit with 56 gates, beating the previous best of 57. They didn't just find a slightly better way; they found a way that scales much better as the problems get bigger.

However, the authors are careful to note where their magic stops. The "perfect" mapmaker (Optimal) only works for very small circuits because the number of paths grows so fast it becomes impossible to check them all for larger sizes. The "smart hiker" (A*) is great for medium sizes but can still get slow if the maze is too complex. And the "short-sighted hiker" (Greedy), while excellent for large circuits, doesn't guarantee the absolute shortest path, just a very good one. They also point out that their work focuses on the theoretical number of gates; making these circuits run on real, physical hardware with specific connection limitations is the next step.

In short, this paper provides a new toolkit for quantum engineers. It offers a way to shrink the tangled yarn of quantum circuits into sleek, efficient lines, making the dream of error-free quantum computers a little bit closer to reality. By combining a database of perfect shortcuts for small jobs, a smart guessing game for medium jobs, and a clever "look-ahead" strategy for big jobs, they have shown that we can build these circuits with fewer moves and less waste than ever before.

Technical Summary: Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Problem Statement

Efficient implementation of Clifford circuits is fundamental to quantum error correction and quantum algorithms. The efficiency of these circuits is typically measured by the count of entangling two-qubit gates (specifically CNOTs for linear reversible circuits) or the circuit depth. Optimizing these metrics is challenging because a single Clifford operator can be implemented by numerous circuit configurations with vastly different gate counts and depths. Existing methods, such as Gaussian elimination or heuristic approaches like those in rustiq, tket, and qiskit, often fail to find the most compact implementations, particularly for larger qubit counts or specific encoding circuits. Furthermore, classical literature on linear reversible circuits (CNOT-only) has established various synthesis techniques, but there remains a need for unified, efficient methods that minimize two-qubit gate counts across both CNOT-only and general Clifford circuits.

Methodology

The authors propose a unified framework for synthesizing CNOT and general Clifford circuits using three distinct algorithmic families: Optimal, A*, and Greedy synthesis. The core of their approach relies on mapping circuit operators to binary matrices and exploiting equivalence classes to reduce search spaces.

1. Mathematical Representations

CNOT Circuits: Mapped to invertible binary matrices in $GL(n, 2)$. A CNOT gate corresponds to adding one column to another.
General Clifford Circuits: Mapped to symplectic binary matrices in $Sp(2n, 2)$. The authors utilize a circuit structure of three layers: qubit permutations, single-qubit Cliffords, and two-qubit symplectic transvections (which are equivalent to CNOTs up to single-qubit Cliffords).
Equivalence Classes: The authors significantly reduce computational complexity by considering equivalence classes of matrices under:
- Row and column permutations (qubit permutations).
- Matrix transposition and inversion.
- For Clifford circuits, left and right multiplication by single-qubit Clifford operators.
- This allows the selection of the circuit member with the lowest gate count or depth from an equivalence class.

2. Algorithm Families

A. Optimal Synthesis

Approach: Generates a database of all equivalence classes of matrices up to a certain qubit count ( $n \le 7$ for CNOT, $n \le 5$ for Clifford).
Mechanism: Matrices are generated by applying all possible gates sequentially. Equivalence is determined by mapping matrices to bi-colored graphs (for CNOT) or generalized graphs (for Clifford) and checking for isomorphism using packages like nauty or Bliss.
Usage: For a target matrix, the algorithm looks up its equivalence class in the pre-computed database and retrieves the optimal gate sequence, applying necessary permutations to match the target.

B. A* Synthesis

Approach: A best-first search algorithm designed for intermediate-sized circuits where optimal databases are too large.
Mechanism: Uses a priority queue to explore gate sequences. It employs a heuristic function $h(P)$ to estimate the remaining cost to reach a permutation matrix (for CNOT) or a permutation plus single-qubit Cliffords (for Clifford).
Heuristics: The authors derive robust estimators based on the row and column sums of the matrix (specifically $H_{sum}$ and $H_{prod}$ metrics). They found that scaling these heuristics ( $r \cdot h$ ) improves performance. The algorithm does not commit to a gate immediately but expands the node with the lowest $g(P) + h(P)$ value.
Optimization: To manage exponential worst-case complexity, the priority queue size is capped (e.g., at 100 entries), removing maximal entries if the limit is exceeded.

C. Greedy Synthesis

Approach: A fast, deterministic algorithm for large circuits.
Mechanism: At each step, it evaluates all possible gates and selects the one that minimizes a specific heuristic.
Innovation: Unlike previous scalar heuristics (which sum entries or log-sums and often get trapped in local minima), the authors introduce a vector-based heuristic. This vector is formed by sorting the column sums of the matrix, its inverse, its transpose, and its inverse-transpose.
Depth Optimization: The greedy algorithm can be modified to minimize circuit depth by treating the depth as a primary cost and the heuristic as a secondary penalty.

Key Contributions and Results

1. Algorithmic Improvements

Vector Heuristic: The proposed vector-based heuristic for greedy synthesis significantly outperforms scalar heuristics (like $H_{sum}$ and $H_{prod}$ ) in avoiding local minima. For circuits with $n \ge 32$ qubits, the vector heuristic was dominant, whereas scalar heuristics failed (abandoned runs) with a 100% abandonment rate for circuits with $n > 32$ qubits.
Equivalence Class Reduction: By mapping to graph isomorphism problems and considering permutations, transposes, and inverses, the authors generated databases that are exponentially smaller than previous methods (e.g., reducing the search space for $Sp(2n, 2)$ significantly compared to Bravyi et al. [4]).

2. Benchmarking Results

The authors benchmarked their methods against rustiq, tket, qiskit, PyZX, and Volanto using random matrices and specific datasets.

CNOT Circuits:
- Optimal/A:* For $n \le 7$ , the A* algorithm matches optimal gate counts. For circuits up to $n = 32$ , the A* algorithm provides the lowest gate counts. For circuits with $n \ge 32$ , the greedy algorithm with the vector heuristic yields the lowest CNOT counts, outperforming Gaussian elimination by an average of 50% reduction in gate count.
General Clifford Circuits:
- Random Matrices: The A* algorithm matches optimal counts for $n \le 5$ and provides the lowest counts for circuits up to $n = 16$ . For circuits with $n > 16$ , the greedy algorithm significantly outperforms all other tested methods (including pytket and rustiq).
- Hamiltonian Dataset: On a dataset of Hamiltonian evolution circuits (4 to 64 qubits), the greedy algorithm outperformed the BSHM algorithm (followed by pytket optimization) in both gate count and runtime.
- Encoding Circuits: For the Golay code $[[23, 1, 7]]$ , the authors found an encoding circuit with 56 entangling two-qubit gates using A*, improving upon the previous best of 57 (Steane's method) and 61 (Reinforcement Learning).
Comparison with SAT Solvers: Compared to qsynth (a SAT-based solver), the authors' optimal and A* algorithms matched or improved upon gate counts for circuits up to 5 qubits with processing times orders of magnitude faster. For $n \ge 6$ , qsynth timed out in almost all instances, while the authors' methods completed successfully.

3. Implementation

The algorithms are implemented in a Python package available on GitHub, allowing the community to reproduce results and apply the methods to their own circuits.

Significance and Claims

The paper claims that its primary significance lies in providing a suite of synthesis tools that consistently achieve lower two-qubit gate counts than existing state-of-the-art methods across a wide range of circuit sizes.

Scalability: The work bridges the gap between small-scale optimal synthesis and large-scale heuristic synthesis, offering a practical solution for circuits up to 64 qubits where previous optimal methods fail due to database size and SAT solvers fail due to time constraints.
Robustness: The vector-based heuristic is highlighted as a key advancement that prevents the "local minima" trap common in scalar-based greedy approaches.
Practical Impact: The ability to find more compact circuits for error correction codes (like Golay) directly impacts the feasibility of fault-tolerant quantum computing by reducing the resource overhead required for logical operations.
Modesty: The authors acknowledge that their optimal synthesis is currently limited to $n \le 7$ (CNOT) and $n \le 5$ (Clifford) due to database size, though they suggest this could be extended with better coding techniques. They also note that while their greedy algorithm is fast, it does not guarantee global optimality for large circuits, though it empirically outperforms competitors.

The work concludes by noting that the algorithms are currently device-agnostic and could be further optimized by porting to C/Rust or adapting to specific hardware connectivity constraints in future iterations.