⚛️ quantum physics

Numerical Evaluation of ZX Calculus Optimization for Solovay Kitaev Quantum Circuit Synthesis

This paper demonstrates that applying ZX-calculus-based diagrammatic simplification to Solovay-Kitaev synthesized quantum circuits consistently reduces T-count and total gate counts by approximately 18–30% across various recursion depths without increasing approximation error, though the computational cost of the rewriting process grows sharply with circuit complexity.

Original authors: Dulari De Silva, Anuradha Mahasinghe, Chon-Fai Kam, Kaushika De Silva, Frederic Cadet, Jingbo Wang

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dulari De Silva, Anuradha Mahasinghe, Chon-Fai Kam, Kaushika De Silva, Frederic Cadet, Jingbo Wang

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

Quantum computers promise to solve problems that would take classical machines thousands of years to finish, but building them is like trying to construct a skyscraper out of glass while standing in a hurricane. The machines are incredibly fragile; the slightest noise or vibration causes their calculations to collapse. To survive, engineers must build a system that can detect and fix its own mistakes, a concept known as fault tolerance. In this protected world, not all computer instructions are created equal. Some basic operations are cheap and easy to perform, but the specific instructions needed to make the computer truly powerful are expensive. They require a complex, resource-heavy process to create, consuming vast amounts of time and physical hardware just to produce a single usable command. Because of this, the total number of these expensive commands in a program is the primary measure of how much a quantum computer will cost to run.

The challenge for scientists is that quantum computers cannot natively understand the smooth, continuous rotations needed for many algorithms. Instead, they must approximate these smooth movements by stringing together a long sequence of the few basic instructions they do have. One famous mathematical recipe, known as the Solovay–Kitaev algorithm, provides a way to build these approximations. It works like a recursive nesting doll, where each layer of the solution corrects the errors of the layer below it. While this method is mathematically guaranteed to work and gets the job done, it is not efficient. It produces sequences that are far longer than necessary, filled with redundant steps that cancel each other out. These extra steps are invisible to a standard compiler because they are hidden inside the mathematical structure of the sequence, but they still count toward the expensive cost of running the program.

A team of researchers set out to see if they could clean up this mess. They asked a simple question: if they took the long, messy sequences produced by the Solovay–Kitaev algorithm and ran them through a specialized diagram-based optimization tool, how much of that waste could they recover? They did not invent a new way to build the sequences; they simply took the existing, unoptimized output and applied a set of rules designed to simplify the visual representation of the quantum circuit. By treating the circuit as a graph of connected nodes rather than a linear list of steps, their tool could spot and merge parts of the calculation that a standard compiler would miss. They tested this on twelve hundred different random quantum targets, ranging from simple rotations to complex, general-purpose gates, and ran the process at three different levels of precision to see how the results changed as the circuits grew larger.

The results showed that the diagram-based tool was remarkably effective at finding waste. Across all the tests, the optimization process removed between twenty-six and thirty percent of the total number of instructions in the circuit. More importantly, it reduced the number of those expensive, hard-to-make commands by nearly twenty-two percent. This is a significant saving because every one of those removed commands represents a direct reduction in the physical resources required to run the quantum computer. The researchers found that the amount of waste removed was not random; it was a consistent fraction of the total size. Whether the circuit was small or grew to be twenty-five times larger, the tool removed roughly the same percentage of the instructions. This suggests that the redundancy is a fundamental feature of the mathematical recipe used to build the circuits, rather than a quirk of specific calculations.

However, this cleanup comes with a price, and the researchers were careful to measure exactly what that price was. While the savings in circuit size were substantial, the time it took to perform the optimization grew dramatically as the circuits got larger. For the smallest circuits, the optimization was almost instantaneous and cost nothing to run. But for the largest circuits, the time spent simplifying the diagram became the dominant part of the entire process, taking over ninety-nine percent of the total time. The researchers concluded that this technique is not a free upgrade for every situation. It is a trade-off: you pay a heavy cost in computer time during the preparation phase to save a significant amount of resources every time the circuit is actually run. For a program that will be executed many times, the trade is worth it, but for a one-off calculation, the time spent optimizing might not be justified.

The study also clarified what this method is and what it is not. The researchers were careful to state that they were not proposing the Solovay–Kitaev algorithm as the best way to build quantum circuits in the first place; other methods exist that are already more efficient. Instead, they were measuring how much structural waste is left behind by this specific, general-purpose mathematical construction. They found that the optimization tool successfully recovered a fixed share of that waste, proving that the redundancy is real and measurable. The work does not claim to have solved the problem of quantum circuit efficiency, nor does it suggest that this tool is better than all other existing optimizers. It simply provides a clear, measured answer to how much can be recovered from a specific type of quantum circuit when viewed through the lens of diagrammatic rewriting, offering a concrete data point for engineers designing the next generation of fault-tolerant quantum computers.

Technical Summary: Numerical Evaluation of ZX-Calculus Optimization for Solovay–Kitaev Quantum Circuit Synthesis

Problem Statement
In fault-tolerant quantum computing, the physical cost of logical operations is dominated by the implementation of non-Clifford T gates, which require expensive magic-state distillation. Consequently, the T-count of a synthesized circuit is the primary engineering metric for compilation efficiency. The Solovay–Kitaev theorem provides a general recursive method to approximate arbitrary single-qubit unitaries from a finite gate set (specifically Clifford+T) with a sequence length that grows polylogarithmically with the inverse of the target error. However, this algorithm optimizes for numerical convergence rather than circuit economy. Its recursive construction, based on nested group commutators, introduces significant structural redundancy—gates that cancel out when viewed as a whole but remain in the linear sequence. While diagrammatic optimization via the ZX-calculus offers a mechanism to identify and remove such redundancies by treating circuits as graphs rather than ordered lists, the specific efficacy of this approach on Solovay–Kitaev outputs has received little empirical attention. This paper addresses the question: how much recoverable structural redundancy does a general recursive group-commutator construction leave behind, and how much can automated ZX rewriting recover?

Methodology
The study employs a four-stage pipeline to measure the impact of ZX-calculus post-processing on Solovay–Kitaev synthesized circuits:

Synthesis: 1,200 random single-qubit targets were generated across four families: Pauli rotations ( $R_x, R_y, R_z$ ) and the general unitary $U(\theta, \phi, \lambda)$ . These were synthesized using the Qiskit Solovay–Kitaev transpiler over the gate set $\{H, S, S^\dagger, T, T^\dagger, Z\}$ at three recursion depths ( $d=2, 3, 4$ ).
Mapping: The resulting gate strings were exported to QASM, parsed into ZX-diagrams, and converted to "graph-like" form, where Clifford and non-Clifford gates are represented as spiders and edges.
Simplification: The diagrams were simplified using PyZX (v0.10.5) via the full_reduce strategy. This applies sound rewrite rules (spider fusion, identity removal, local complementation, and pivoting) that preserve the implemented linear map up to a global scalar.
Extraction and Measurement: The simplified diagrams were extracted back into circuits. The study measured the total gate count, T-count, and wall-clock time before and after optimization. Accuracy was verified by ensuring the trace error norm remained unchanged, as the rewrite rules are semantics-preserving.

Key Contributions and Results
The paper presents a quantitative measurement of the composition between Solovay–Kitaev synthesis and ZX-calculus optimization, rather than proposing a new synthesis method. The key findings are:

Gate Reduction: Post-processing removed between 26.6% and 30.1% of the total gate count and 18.5% to 22.2% of the T-count.
Depth Independence of Fractional Savings: A critical finding is that the fractional reduction remains nearly constant across recursion depths. While the absolute circuit length grows twenty-five-fold from $d=2$ to $d=4$ , the proportion of gates removed by rewriting stays flat (rising slightly from the shallowest setting and then stabilizing). This suggests the redundancy is a fixed share of the output generated locally at the junctions of base words, rather than accumulating with nesting depth.
Target Family Independence: The reduction fraction is consistent across the four target families. At the deepest recursion level ( $d=4$ ), the four families are statistically indistinguishable, and the variance across individual targets collapses significantly. This indicates the recoverable redundancy is a property of the Solovay–Kitaev construction itself, not the specific target unitary.
Absolute vs. Fractional Savings: While the percentage saving is constant, the absolute saving grows with circuit size, ranging from approximately 60 gates at $d=2$ to roughly 1,600 gates at $d=4$ .
Compile-Time Cost: The cost of the rewriting layer grows superlinearly with circuit depth. At shallow depths, the rewriting cost is negligible compared to synthesis; however, at $d=4$ , the rewriting layer accounts for over 99% of the total pipeline time, dominating the synthesis step itself.
Accuracy Preservation: The optimization incurs no loss in accuracy. The extracted circuits were verified to implement the same linear map as the synthesized circuits, with deviations limited to floating-point accumulation ( $< 5.8 \times 10^{-13}$ ).

Significance and Claims
The paper modestly positions its contribution as a measurement of the "recoverable structural redundancy" inherent in the Solovay–Kitaev algorithm when viewed through a diagrammatic lens. It explicitly states that Solovay–Kitaev is not a competitive synthesis route for production compilers (which typically use number-theoretic methods for z-rotations), and thus the reported T-counts are not competitive with state-of-the-art near-optimal synthesis.

The significance lies in characterizing the trade-off of using diagrammatic optimization on recursive synthesis outputs:

Predictability: The fractional savings are a stable property of the construction, independent of the target or depth.
Trade-off: The benefit is not "free." The composition has a specific operating range; while the absolute gate savings are substantial for deep circuits, the compile-time cost of obtaining them becomes the dominant factor at higher recursion depths.
Mechanism: The reduction is driven by the ability of the ZX-calculus to merge phase nodes separated by basis changes in the linear gate list, a capability linear compilers lack.

The authors conclude that this composition offers a uniform reduction in gate count but should be viewed as a trade with an operating range rather than a universal improvement, particularly given the steep growth in compilation time. Future work is suggested to compare against non-diagrammatic optimizers and to investigate multi-qubit settings.

Technical Summary: Numerical Evaluation of ZX-Calculus Optimization for Solovay–Kitaev Quantum Circuit Synthesis

More like this