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:1412.5608

Efficient Approximation of Diagonal Unitaries over the Clifford+T Basis

Welch, Jonathan, Alex Bocharov, Krysta M. Svore

Published Dec 17, 2014• 1 citation
arXivHTMLPDF

Abstract

We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+$T$ basis, that minimize the number of phase-rotation gates in the synthesized approximation circuit. The equivalent $T$-count of the synthesized circuit is bounded by $k \, C_0 \log_2(1/\varepsilon) + E(n,k)$, where $k$ is the number of distinct phases in the diagonal $n$-qubit unitary, $\varepsilon$ is the desired precision, $C_0$ is a quality factor of the implementation method ($1

DOI
10.48550/arxiv.1412.5608

Related papers

Efficient approximation of diagonal unitaries over the Clifford+T basis

Jonathan Welch, Alex Bocharov, Krysta M. Svore

We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+T basis, that minimizes the number of phase-rotation gates in the synthesized approximation circuit. The equivalent T-count of the synthesized circuit is bounded by kC_0 log_2 (1/ε)+E(n, k), where k is the number of distinct phases in the diagonal n-qubit unitary, ε is the desired precision, C0 is a quality factor of the implementation method (1 < C_0 < 4), and E(n, k) is the total entanglement cost (in T gates). We determine an optimal decision boundary in (n, k, ε)-space where our decomposition algorithm achieves lower entanglement cost than previous state-of-the-art techniques. Our method outperforms state-of-the-art techniques for a practical range of ε values and diagonal operators and can reduce the number of T gates exponentially in n when k far less than 2^ n .

Quantum Information and Computation•Jan 1, 2016•7 citations

High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization

Mathias Weiden, Justin Kalloor, John David Kubiatowicz +2 more

Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.

arXiv:2409.00433•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•1 citation

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

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Unitary Synthesis with Fewer T Gates

Xinyu Tan

We present a simple algorithm that implements an arbitrary n -qubit unitary operator using a Clifford + T circuit with T-count O ( 2 4 n / 3 n 2 / 3 ) and ancilla-count O ( 2 2 n / 3 n 1 / 3 ) . The previous best T-count for unitary synthesis was O ( 2 3 n / 2 n ) with O ( 2 n / 2 ) ancillae by [Low , ]. There is a fundamental tradeoff between T gates and ancillae, and our algorithm extends the achievable regime of this tradeoff, reducing the exponent in T-count from 3 n / 2 to 4 n / 3 . The best known lower bound remains Ω ( 2 n ) , so the optimal T-count for general unitary synthesis is still open. Our construction is based on a recursive application of the cosine-sine decomposition, together with a generalization of the optimal diagonal unitary synthesis method by [D. Gosset , ] to multi-controlled k -qubit unitaries.

arXiv:2509.25702•PRX Quantum•Aug 10, 2026•0 citations

Phase-context decomposition of diagonal unitaries for higher-dimensional systems

Kerstin Beer, Friederike Anna Dziemba

We generalize the efficient decomposition method for phase-sparse diagonal operators of J. Welch et al. [Quantum Info. Comput. 16, 87 (2016)] to qudit systems. The phase-context-aware method focuses on cascaded entanglers, whose decomposition into multicontrolled inc gates can be optimized by the choice of a proper signed base-$d$ representation for the natural numbers. While the gate count of the best-known decomposition method for general diagonal operators on qubit systems scales with $O({2}^{n})$, the circuits synthesized by the Welch algorithm for diagonal operators with $k$ distinct phases are upper-bounded by $O({n}^{2}k)$, which is generalized to $O(d{n}^{2}k)$ for the qudit case in this paper.

arXiv:1511.05758•Physical Review A•May 25, 2016•3 citations
We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+TTT basis, that minimize the number of phase-rotation gates in the synthesized approximation circuit. The equivalent TTT-count of the synthesized circuit is bounded by k C0log⁡2(1/ε)+E(n,k)k \, C_0 \log_2(1/\varepsilon) + E(n,k)kC0​log2​(1/ε)+E(n,k), where kkk is the number of distinct phases in the diagonal nnn-qubit unitary, ε\varepsilonε is the desired precision, C0C_0C0​ is a quality factor of the implementation method ($1
We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+T basis, that minimizes the number of phase-rotation gates in the synthesized approximation circuit. The equivalent T-count of the synthesized circuit is bounded by kC_0 log_2 (1/ε)+E(n, k), where k is the number of distinct phases in the diagonal n-qubit unitary, ε is the desired precision, C0 is a quality factor of the implementation method (1 < C_0 < 4), and E(n, k) is the total entanglement cost (in T gates). We determine an optimal decision boundary in (n, k, ε)-space where our decomposition algorithm achieves lower entanglement cost than previous state-of-the-art techniques. Our method outperforms state-of-the-art techniques for a practical range of ε values and diagonal operators and can reduce the number of T gates exponentially in n when k far less than 2^ n .
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.
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.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
We present a simple algorithm that implements an arbitrary n -qubit unitary operator using a Clifford + T circuit with T-count O ( 2 4 n / 3 n 2 / 3 ) and ancilla-count O ( 2 2 n / 3 n 1 / 3 ) . The previous best T-count for unitary synthesis was O ( 2 3 n / 2 n ) with O ( 2 n / 2 ) ancillae by [Low , ]. There is a fundamental tradeoff between T gates and ancillae, and our algorithm extends the achievable regime of this tradeoff, reducing the exponent in T-count from 3 n / 2 to 4 n / 3 . The best known lower bound remains Ω ( 2 n ) , so the optimal T-count for general unitary synthesis is still open. Our construction is based on a recursive application of the cosine-sine decomposition, together with a generalization of the optimal diagonal unitary synthesis method by [D. Gosset , ] to multi-controlled k -qubit unitaries.
We generalize the efficient decomposition method for phase-sparse diagonal operators of J. Welch et al. [Quantum Info. Comput. 16, 87 (2016)] to qudit systems. The phase-context-aware method focuses on cascaded entanglers, whose decomposition into multicontrolled inc gates can be optimized by the choice of a proper signed base-ddd representation for the natural numbers. While the gate count of the best-known decomposition method for general diagonal operators on qubit systems scales with O(2n)O({2}^{n})O(2n), the circuits synthesized by the Welch algorithm for diagonal operators with kkk distinct phases are upper-bounded by O(n2k)O({n}^{2}k)O(n2k), which is generalized to O(dn2k)O(d{n}^{2}k)O(dn2k) for the qudit case in this paper.