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

• URL: http://arxiv.org/abs/2510.07627v1
• Date: Wed, 08 Oct 2025 23:48:48 GMT
• Title: Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates
• Authors: Kaoru Sano, Hayata Morisaki, Seiseki Akibue,
• Abstract summary: 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$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Contributions to the Theory of Clifford-Cyclotomic Circuits [0.0]
  We make two contributions to the theory of Clifford-cyclotomic circuits.<n>We improve the existing synthesis algorithm by showing that, when $n=2k$ and $kgeq 4$, only $k-3$ ancillas are needed to synthesize a circuit for $U$.
  arXiv  Detail & Related papers  (2025-08-20T12:44:39Z)
• 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)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  We show that any algorithm requires $Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods. Our lower bound addresses Open Question 1WooWoo14, providing evidence for the lack of progress on algorithms for Spectral LRA.
  arXiv  Detail & Related papers  (2023-04-06T16:15:19Z)
• 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)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• 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)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.