Original title: Heuristic and Optimal Synthesis of CNOT and Clifford Circuits
Mark Webster, Stergios Koutsioumpas, Dan E. Browne · September 2026
Quantum computers rely on special setups called Clifford circuits, which matter for stopping errors and running programs. Similarly, classical computers use reversible circuits made of CNOTA basic quantum gate that flips the state of one qubit depending on the state of another, a common two-qubit operation. gates, a basic building block that flips a target bit based on a control bit. Designing these circuits efficiently is tricky because extra parts cause problems. To fix this, researchers created ways to synthesize these circuits to minimize either two-qubit entangling gates or circuit depthThe number of consecutive steps in a circuit when parallel operations are counted together; shorter depth means faster execution.. Their system uses three algorithms: optimal synthesis for small circuits, an A* search method for intermediate-size circuits, and a greedy method for large circuits. These methods build circuits with fewer two-qubit gates than older tools, outperforming earlier reinforcement learning tests and setting a new record-low count for the Golay codeA specific error-correcting code used to protect quantum information, often used as a benchmark in quantum computing research..
Imagine packing a suitcase with a few bulky items that eat most of the space. If you toss them in carelessly, you waste room and risk leaving things behind, so you rearrange them to fit better. For a handful of items you can try every order to find the best fit, but with a closet full you need a faster rule of thumb. In this paper, the bulky items are the costliest operations in a computation, and the suitcase is the final arrangement of those operations; the three algorithms are the perfect search, a smart middle ground, and a quick rule.
Quantum error correction, essential for practical quantum computers, depends on Clifford circuits. Making those circuits smaller means fewer chances for errors and less overhead, which brings fault-tolerant quantum computing closer. The same tools also shrink certain classical circuits used in ordinary computing.
The optimal synthesis only works for small circuits; larger ones rely on heuristics that don't guarantee the best result. The benchmarks cover specific tools and codes, so improvements may not generalize to all cases. The paper does not address physical constraints like qubit connectivity or error rates.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Heuristic and Optimal Synthesis of CNOT and Clifford Circuits — Mark Webster, Stergios Koutsioumpas, Dan E. Browne — Quantum — doi:10.22331/q-2026-09-21-2212
Abstract licence: CC BY
Explanation generated by Synthesis from the abstract — it is not the original paper.