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

Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates

Sano, Kaoru, Hayata Morisaki, Seiseki Akibue

Published Oct 8, 2025• 1 citation
arXivHTMLPDF

Abstract

We study ancilla-free approximation of single-qubit unitaries $U\in {\rm SU}(2)$ by gate sequences over Clifford+$G$, where $G\in\{T,V\}$ or their generalization. Let $p$ denote the characteristic factor of the gate set (e.g., $p=2$ for $G=T$ and $p=5$ for $G=V$). We prove three asymptotic bounds on the minimum $G$-count required to achieve approximation error at most $\varepsilon$. First, for Haar-almost every $U$, we show that $3\log_{p}(1/\varepsilon)$ $G$-count is both necessary and sufficient; moreover, probabilistic synthesis improves the leading constant to $3/2$. Second, for unitaries whose ratio of matrix elements lies in a specified number field, $4\log_p(1/\varepsilon)$ $G$-count is necessary. Again, the leading constant can be improved to $2$ by probabilistic synthesis. Third, there exist unitaries for which the $G$-count per $\log_{p}(1/\varepsilon)$ fails to converge as $\varepsilon\to 0^+$. These results partially resolve a generalized form of the Ross--Selinger conjecture.

DOI
10.48550/arxiv.2510.07627

Related papers

Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries

Hayata Morisaki, Sano, Kaoru, Seiseki Akibue

We propose two Clifford+$T$ synthesis algorithms that are optimal with respect to $T$-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+$T$ circuit with the minimum $T$-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+$T$ circuits with the minimum $T$-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are $\varepsilon^{-1/2 - o(1)}$ and $\varepsilon^{-1/4 - o(1)}$, respectively, for an approximation error $\varepsilon$. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at $\varepsilon \approx 10^{-15}$ and $\varepsilon \approx 10^{-22}$, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most $3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates, and the probabilistic synthesis algorithm requires at most $1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.

arXiv:2510.05816•Oct 7, 2025•11 citations

Multi-qubit controlled gate synthesis without T-count overhead in the small-error limit

Soichiro Yamazaki, Seiseki Akibue, Kaoru Sano

We study the Clifford+T synthesis of quantum multiplexers $U=\bigoplus_{i=1}^{2^n}U_i$: an $n$-qubit control register selects which single-qubit gate $U_i\in\mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$, consider the minimum even T-count needed to approximate it within diamond distance $\varepsilon$ without ancillae, and let $m$ be the largest of these costs. For an arbitrary multiplexer $U$, we construct an approximation of $U$ within the same distance using at most $m+O(\sqrt{2^n(m+1)})$ $T$ gates. With one control qubit, the cost is $m+O(1)$ and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed $n$ and independent Haar-random blocks, the minimum T-count among these circuits lies between $(3-δ)\log_2(1/\varepsilon)$ and $(3+δ)\log_2(1/\varepsilon)$ for every fixed $δ>0$, except with probability $O(\varepsilon^{c_{n,δ}})$ as $\varepsilon\rightarrow0$. The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{SU}(2)$ gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order $\varepsilon^2$. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random $\mathrm{SU}(4)$ gates within diamond distance $\varepsilon$, using at most $(9+δ)\log_2(1/\varepsilon)$ $T$ gates for every fixed $δ>0$, except with probability $O(\varepsilon^{c_δ})$ with $c_δ>0$.

quant-pharXiv:2603.14202•Mar 17, 2026•1 citation

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

Fast exact synthesis of two-qubit unitaries using a near-minimum number of T gates

Longcheng Li, Cheng Guo, Qian Li +1 more

This paper focuses on exact synthesis of two-qubit unitaries using Clifford and $T$ gates. We propose an ancilla-free synthesis algorithm (i) which uses $T$ gates no more than ten times the minimum possible number of $T$ gates, also known as the $T$ count, and (ii) whose time complexity is linear with the $T$ count and thus instance optimal. Our synthesis algorithm relies on a characterization of the $T$ count of two-qubit unitaries based on Lie group homomorphism, which may be interest of its own. Precisely, we show that for any two-qubit unitary generated by Clifford and $T$ gates, its $T$ count is equivalent to the least denominator exponent of its SO(6) representation up to a factor of at most 10.

Physical Review A•Apr 18, 2023•4 citations

Shorter quantum circuits via single-qubit gate approximation

Vadym Kliuchnikov, Kristin Lauter, Romy Minko +2 more

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ⁡ ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ⁡ ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

arXiv:2203.10064•Quantum•Dec 18, 2023•61 citations

Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits

Vadym Kliuchnikov, Dmitri A Maslov, Michele Mosca

Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae and the phase kickback approach that requires $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates but uses $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathbf{)}$ ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision $\ensuremath{\epsilon}$ using $O\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ Clifford and $T$ gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ operations with integers.

arXiv:1212.0822•Physical Review Letters•May 8, 2013•146 citations
We study ancilla-free approximation of single-qubit unitaries U∈SU(2)U\in {\rm SU}(2)U∈SU(2) by gate sequences over Clifford+GGG, where G∈{T,V}G\in\{T,V\}G∈{T,V} or their generalization. Let ppp denote the characteristic factor of the gate set (e.g., p=2p=2p=2 for G=TG=TG=T and p=5p=5p=5 for G=VG=VG=V). We prove three asymptotic bounds on the minimum GGG-count required to achieve approximation error at most ε\varepsilonε. First, for Haar-almost every UUU, we show that 3log⁡p(1/ε)3\log_{p}(1/\varepsilon)3logp​(1/ε) GGG-count is both necessary and sufficient; moreover, probabilistic synthesis improves the leading constant to 3/23/23/2. Second, for unitaries whose ratio of matrix elements lies in a specified number field, 4log⁡p(1/ε)4\log_p(1/\varepsilon)4logp​(1/ε) GGG-count is necessary. Again, the leading constant can be improved to 222 by probabilistic synthesis. Third, there exist unitaries for which the GGG-count per log⁡p(1/ε)\log_{p}(1/\varepsilon)logp​(1/ε) fails to converge as ε→0+\varepsilon\to 0^+ε→0+. These results partially resolve a generalized form of the Ross--Selinger conjecture.
We propose two Clifford+TTT synthesis algorithms that are optimal with respect to TTT-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+TTT circuit with the minimum TTT-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+TTT circuits with the minimum TTT-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ε−1/2−o(1)\varepsilon^{-1/2 - o(1)}ε−1/2−o(1) and ε−1/4−o(1)\varepsilon^{-1/4 - o(1)}ε−1/4−o(1), respectively, for an approximation error ε\varepsilonε. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at ε≈10−15\varepsilon \approx 10^{-15}ε≈10−15 and ε≈10−22\varepsilon \approx 10^{-22}ε≈10−22, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most 3log⁡2(1/ε)+o(log⁡2(1/ε))3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))3log2​(1/ε)+o(log2​(1/ε)) TTT-gates, and the probabilistic synthesis algorithm requires at most 1.5log⁡2(1/ε)+o(log⁡2(1/ε))1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))1.5log2​(1/ε)+o(log2​(1/ε)) TTT-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUiU=\bigoplus_{i=1}^{2^n}U_iU=⨁i=12n​Ui​: an nnn-qubit control register selects which single-qubit gate Ui∈SU(2)U_i\in\mathrm{SU}(2)Ui​∈SU(2) acts on the target qubit. For each block UiU_iUi​, consider the minimum even T-count needed to approximate it within diamond distance ε\varepsilonε without ancillae, and let mmm be the largest of these costs. For an arbitrary multiplexer UUU, we construct an approximation of UUU within the same distance using at most m+O(2n(m+1))m+O(\sqrt{2^n(m+1)})m+O(2n(m+1)​) TTT gates. With one control qubit, the cost is m+O(1)m+O(1)m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed nnn and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log⁡2(1/ε)(3-δ)\log_2(1/\varepsilon)(3−δ)log2​(1/ε) and (3+δ)log⁡2(1/ε)(3+δ)\log_2(1/\varepsilon)(3+δ)log2​(1/ε) for every fixed δ>0δ>0δ>0, except with probability O(εcn,δ)O(\varepsilon^{c_{n,δ}})O(εcn,δ​) as ε→0\varepsilon\rightarrow0ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2)\mathrm{SU}(2)SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2\varepsilon^2ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4)\mathrm{SU}(4)SU(4) gates within diamond distance ε\varepsilonε, using at most (9+δ)log⁡2(1/ε)(9+δ)\log_2(1/\varepsilon)(9+δ)log2​(1/ε) TTT gates for every fixed δ>0δ>0δ>0, except with probability O(εcδ)O(\varepsilon^{c_δ})O(εcδ​) with cδ>0c_δ>0cδ​>0.
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.
This paper focuses on exact synthesis of two-qubit unitaries using Clifford and TTT gates. We propose an ancilla-free synthesis algorithm (i) which uses TTT gates no more than ten times the minimum possible number of TTT gates, also known as the TTT count, and (ii) whose time complexity is linear with the TTT count and thus instance optimal. Our synthesis algorithm relies on a characterization of the TTT count of two-qubit unitaries based on Lie group homomorphism, which may be interest of its own. Precisely, we show that for any two-qubit unitary generated by Clifford and TTT gates, its TTT count is equivalent to the least denominator exponent of its SO(6) representation up to a factor of at most 10.
We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ⁡ ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ⁡ ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.
Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae and the phase kickback approach that requires $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates but uses $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathbf{)}$ ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision $\ensuremath{\epsilon}$ using $O\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ Clifford and TTT gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ operations with integers.