Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.
Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.
Gate synthesis and circuit optimization are usually studied separately, and evidence on their interaction is contradictory: ZX-calculus rewriting removes a stable fraction of Solovay-Kitaev circuits, yet almost nothing from number-theoretically synthesized circuits. We show both behaviours follow from a single bound. For any optimizer that preserves the implemented element exactly--including all sound ZX rewriting with extraction--the achievable T-count is bounded below by the denominator exponent of the synthesized ring element. This exactness barrier is computable per instance and separates exact post-processing from approximation-aware resynthesis by a certified factor reaching 101x at recursion depth five. The two behaviours are then the barrier operating at different distances from the floor. For Solovay-Kitaev circuits we prove that the local ZX simplification layer (spider fusion and identity removal) computes exactly the free-product normal form of Z_2 * Z_8, giving exact per-instance compression and, under a calibrated ergodicity hypothesis, a depth-independent limit law confirmed on two independently constructed nets. For number-theoretically synthesized circuits the floor is already saturated: on single-qubit words automated ZX simplification attains it exactly, via a closed-form formula for minimal T-count in terms of phase linkage through the Z-axis normalizer. At two qubits and beyond the same valuation yields unconditional rigidity certificates, which on the quantum-Shannon-decomposition plus gridsynth pipeline certify 99.4-99.9% of the synthesized T-count as incompressible, with rigidity strengthening as accuracy tightens. This explains, and predicts the size of, the near-null optimization recently reported for that pipeline.
For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.
Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce T-count
Compiling quantum circuits into Clifford+T gates is a central task for fault-tolerant quantum computing using stabilizer codes. In the near term, T gates will dominate the cost of fault tolerant implementations, and any reduction in the number of such expensive gates could mean the difference between being able to run a circuit or not. While exact synthesis is exponentially hard in the number of qubits, local synthesis approaches are commonly used to compile large circuits by decomposing them into substructures. However, composing local methods leads to suboptimal compilations in key metrics such as T-count or circuit depth, and their performance strongly depends on circuit representation. In this work, we address this challenge by proposing \textsc{Q-PreSyn}, a strategy that, given a set of local edits preserving circuit equivalence, uses a RL agent to identify effective sequences of such actions and thereby obtain circuit representations that yield a reduced T-count upon synthesis. Experimental results of our proposed strategy, applied on top of well-known synthesis algorithms, show up to a 20% reduction in T-count on circuits with up to 25 qubits, without introducing any additional approximation error prior to synthesis.
Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of ε>0 requires O(logc[1/ε]) quantum gates with c>1.44042. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log[1/ε]loglog[1/ε]logloglog[1/ε]⋯) FT gates chosen from a finite set depending on the value of ε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.
Quantum computers promise exponential speedups for problems in cryptography, chemistry, and optimization. Realizing this promise requires fault tolerance: physical qubits are noisy, so logical qubits must be encoded redundantly across many physical ones using quantum error-correcting codes. In most practical fault-tolerance schemes, T gates cannot be implemented transversally and instead require costly magic-state distillation protocols involving a complex set of operations. As a result, T-gate count can dominate the resource budget of large-scale quantum computations, making T-count minimization a central bottleneck on the path to quantum advantage. Existing T-count optimization tools, however, do not scale to the circuits that quantum advantage demands.
We present theoretical and practical results on T-gate optimization. On the theoretical side, we give a linear-time randomized algorithm for phase folding, based on a novel randomized static analysis. Our static analysis soundly approximates the set of reachable quantum states with an arbitrarily high probability. Our key insight is a static analysis that does not track symbolic expressions, but propagates constant-width bitstrings down the circuit. On the practical side, our implementation, TZAP, is multiple orders of magnitude faster than state-of-the-art tools -- such as PyZX, VOQC, and Feynman -- closely matches their T-count reductions on standard benchmarks, and within seconds on a laptop computer can optimize circuits with millions of gates.
Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances of quantum computing hardware, the practical use of NISQ era devices remains severely limited due to resources constraints (e.g., noise, qubits, gates, circuit depth, and coherence time). QC optimization is an essential mitigation strategy to enable the execution of quantum programs on restricted quantum devices. In this context, ZX-calculus emerged as an alternative to conventional gate-level QC optimization approaches. Instead of depending upon gate set specific rewriting rules, it offers a compact, universal and semantics-preserving framework for QC optimization. However, ZX-based QC optimization faces two challenges in practice. On the one hand, ZX-calculus admits a non-terminating rewriting system. On the other hand, ZX-diagrams lose causality. As a consequence, only a subset of ZX-diagrams that preserve CFlow, GFlow or Pauli flow allow for the extraction of QCs in polynomial-time. The first challenge can be addressed by effective heuristics, search algorithms and pruning conditions while the latter is an optimization problem with an upper bound of NPNP#P, where the choice of the extraction algorithm can negate ZX-diagram level improvements. This thesis establishes a ZX-based end-to-end pipeline for QC optimization that leverages tree search for metric-agnostic ZX-diagram optimization and \gls{ilp} paired with backtracking search to improve the circuit extraction step. The contributions of this thesis are four-fold: (i) First, it presents a comprehensive survey of ZX-based QC optimization, categorizing them by the employed optimization strategy, the target metric, and the intended quantum computing architecture. (ii) Second, this work formalizes the ZX-diagram optimization problem as the explicit state-space exploration of rewriting rule sequences. (iii) Thirdly, the formal approach is put into practice by implementing tree search algorithms, in particular DFS, IDDFS, and LDS, to reduce the T-gate, and Edge count of ZX-diagrams. Furthermore, the efficacy of different pruning conditions are investigated. Lastly, the novel Local-Elimination (LE) is introduced as a metaheuristic to select growing sub ZX-diagrams around a target spider. Instead of performing tree search optimization on intractable large ZX-diagrams, LE changes one large optimization problem into a sequence of tractable small searches. All tree search strategies are extensively tested on benchmark data sets that contain different QC types. (iv) Finally, this work enhances two-qubit gate count during circuit extraction by introducing an ILP model that replaces the Gaussian Elimination steps present in current circuit extraction algorithms. Pairing the ILP model for circuit extraction with backtracking allows the exploration of multiple solutions that take advantage of gate commutation and cancellation rules during extraction. The last research artifact of this thesis is the introduction of \emph{ZX-benchmark}, a declarative end-to-end optimization pipeline and ZX benchmarking framework to compare different optimization and extraction algorithms on the same data sets and under comparable experimental conditions. To this end, it offers access to multiple data sets, and various third-party optimizers. With the intent to offer a framework that is useful beyond the scope of this thesis, the framework provides support of configuration files and a unified API to declare experiments. All artifacts produced are in the form of plain text formats (JSON, and OpenQASM). In summary, the thesis advances ZX-based compilation by connecting metric-agnostic diagram rewriting with extraction-aware optimization in a reusable, end-to-end workflow.