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

• URL: http://arxiv.org/abs/2510.05816v1
• Date: Tue, 07 Oct 2025 11:37:02 GMT
• Title: Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries
• Authors: Hayata Morisaki, Kaoru Sano, Seiseki Akibue,
• Abstract summary: The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+$T$ circuit with the minimum $T$-count.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates [0.0]
  We study ancilla-free approximation of single-qubit unitaries $Uin rm SU(2)$ by gate sequences over Clifford+$G$.<n>We prove three bounds on the minimum $G$-count required to achieve approximation error at most $varepsilon$.
  arXiv  Detail & Related papers  (2025-10-08T23:48:48Z)
• Synthesis of Single Qutrit Circuits from Clifford+R [0.0]
  Two deterministic algorithms are presented to approximate single-qutrit gates.<n>The first algorithm exhaustively searches over the Clifford + $mathbfR$ group.<n>The second algorithm searches for Householder reflections.
  arXiv  Detail & Related papers  (2025-03-26T03:55:43Z)
• Quantum state preparation with optimal T-count [2.1386090295255333]
  We show how many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $varepsilon$. We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $varepsilon$.
  arXiv  Detail & Related papers  (2024-11-07T15:29:33Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  Two recent works established the $O(epsilon-3)$ sample complexity to obtain an $O(epsilon)$-stationary point. However, both require a large batch size on the order of $mathrmploy(epsilon-1)$, which is not only computationally burdensome but also unsuitable for streaming applications. In this work, we solve the prior two problems simultaneously by revisiting a simple variant of the STORM algorithm.
  arXiv  Detail & Related papers  (2023-02-13T00:22:28Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.