Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.22810

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

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

On Aqora:Jingbo WangJingbo WangChon-Fai KamChon-Fai Kam
quant-phSubmitted Aug 24, 2026• Announced Aug 25, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
20 pages, 9 figures

Related papers

An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits

Chon-Fai Kam, Anuradha Mahasinghe, Kaushika De Silva +2 more

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.

quant-pharXiv:2608.22801•Aug 25, 2026•1 citation

Cost-optimal single-qubit gate synthesis in the Clifford hierarchy

Gary J. Mooney, Charles D. Hill, Lloyd C. L. Hollenberg

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.

arXiv:2005.05581•Quantum•Feb 15, 2021•7 citations

Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$-count

Daniele Lizzio Bosco, Lukasz Cincio, Giuseppe Serra +1 more

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.

quant-pharXiv:2601.19738•Jan 28, 2026•6 citations

Quantum circuit synthesis using Solovay-Kitaev algorithm and optimization techniques

Al-Ta'ani, Ola

Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.

•May 1, 2015•7 citations

Optimal Approximation of Single Qubit Rotations within a Quantum Circuit

Gilad Kishony, Avi Elazari, Ron Cohen +1 more

Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T. As a baseline, Diagonal approximation can be used for synthesizing single-qubit Pauli rotations, yielding an approximating sequence with $T$-count that equals $3 \log_2(1/ε)$ for a target precision $ε$. Magnitude Approximation can reduce the $T$-count to only $1 \log_2(1/ε)$ by allowing large residual errors, which are rotations about orthogonal axes. Within a complete quantum circuit, these residual errors can then be absorbed into neighboring gates before they are approximated themselves. Determining the optimal allocation of approximation strategies within a large, multi-qubit circuit presents a significant combinatorial challenge. In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem. We demonstrate that the issue of delegating Magnitude versus Diagonal approximation across a circuit maps formally to a classical 1D Ising model with a spatially varying field. By minimizing the energy of this Hamiltonian, we identify the optimal approximation configuration for each rotation without exponential overhead. Benchmarking our method against standard diagonal approximation on random quantum circuits, we observe an average reduction of 26\% in the total approximating circuit gate count, offering a significant efficiency gain for the implementation of quantum algorithms on near-term and fault-tolerant architectures.

quant-pharXiv:2605.09671•May 12, 2026•0 citations

Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem

H. F. Chau

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 $\text{O}(\log^c[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 $\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)$ 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.

arXiv:2406.04846•Jun 7, 2024•0 citations
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 TTT-count
Compiling quantum circuits into Clifford+TTT gates is a central task for fault-tolerant quantum computing using stabilizer codes. In the near term, TTT 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 TTT-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 TTT-count upon synthesis. Experimental results of our proposed strategy, applied on top of well-known synthesis algorithms, show up to a 20%20\%20% reduction in TTT-count on circuits with up to 25 qubits, without introducing any additional approximation error prior to synthesis.
Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.
Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T. As a baseline, Diagonal approximation can be used for synthesizing single-qubit Pauli rotations, yielding an approximating sequence with TTT-count that equals 3log⁡2(1/ε)3 \log_2(1/ε)3log2​(1/ε) for a target precision εεε. Magnitude Approximation can reduce the TTT-count to only 1log⁡2(1/ε)1 \log_2(1/ε)1log2​(1/ε) by allowing large residual errors, which are rotations about orthogonal axes. Within a complete quantum circuit, these residual errors can then be absorbed into neighboring gates before they are approximated themselves. Determining the optimal allocation of approximation strategies within a large, multi-qubit circuit presents a significant combinatorial challenge. In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem. We demonstrate that the issue of delegating Magnitude versus Diagonal approximation across a circuit maps formally to a classical 1D Ising model with a spatially varying field. By minimizing the energy of this Hamiltonian, we identify the optimal approximation configuration for each rotation without exponential overhead. Benchmarking our method against standard diagonal approximation on random quantum circuits, we observe an average reduction of 26\% in the total approximating circuit gate count, offering a significant efficiency gain for the implementation of quantum algorithms on near-term and fault-tolerant architectures.
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ε> 0ε>0 requires O(log⁡c[1/ε])\text{O}(\log^c[1/ε])O(logc[1/ε]) quantum gates with c>1.44042c > 1.44042c>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/ε])Ω(\log[1/ε])Ω(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/ε]log⁡log⁡[1/ε]log⁡log⁡log⁡[1/ε]⋯ )\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)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ε> 0ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.