Unitary synthesis with fewer T gates

• URL: http://arxiv.org/abs/2509.25702v1
• Date: Tue, 30 Sep 2025 03:01:34 GMT
• Title: Unitary synthesis with fewer T gates
• Authors: Xinyu Tan,
• Abstract summary: We present a simple algorithm that implements an arbitrary $n$-qubit unitary operator using a Clifford+T circuit with T-count $O(24n/3 n2/3)$.<n>This improves upon the previous best known upper bound of $O(23n/2 n)$, while the best known lower bound remains $Omega (2n)$.
• Score: 1.3512504563343783
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a simple algorithm that implements an arbitrary $n$-qubit unitary operator using a Clifford+T circuit with T-count $O(2^{4n/3} n^{2/3})$. This improves upon the previous best known upper bound of $O(2^{3n/2} n)$, while the best known lower bound remains $\Omega(2^n)$. 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 Gosset, Kothari, and Wu to multi-controlled $k$-qubit unitaries.

Related papers

• Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries [0.0]
  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.
  arXiv  Detail & Related papers  (2025-10-07T11:37:02Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms. We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Decision Processes (MDs) with finite state spaces.<n>We demonstrate that the step sizes for both the actor and critic must decay as ( O(k-Pfrac12) ) with $k$ diverging from the conventional ( O(k-Pfrac12) ) rates commonly used in (non- optimal) Markov framework optimization.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation $Gx = 0$.<n>Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms.<n> numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-06-04T15:23:29Z)
• Multi-qutrit exact synthesis [0.0]
  We present an exact synthesis algorithm for qutrit unitaries in $mathcalU_3n(mathbbZ[/3,e2pi i/3])$ over the Clifford$+T$ gate set with at most one ancilla. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford$+mathcalD$ over the multi-qutrit Clifford$+T$ gate set with at most two ancillas.
  arXiv  Detail & Related papers  (2024-05-13T19:48:10Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pair imation (BPE) is a popular algorithm used for tokenizing data in NLP, despite being devised initially as a compression method. We provide a faster implementation of BPE which improves the runtime complexity from $mathcalOleft(N Mright)$ to $mathcalOleft(N log Mright)$, where $N$ is the sequence length and $M$ is the merge count.
  arXiv  Detail & Related papers  (2023-06-29T10:29:23Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  In this paper, we revisit the smooth and strongly-strongly-concave minimax optimization problem. Existing state-of-the-art methods do not match lower bound $Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$. We fix this fundamental issue by providing the first algorithm with $mathcalOleft( sqrtkappa_xkappa_ylog
  arXiv  Detail & Related papers  (2022-05-11T17:33:07Z)
• T-count and T-depth of any multi-qubit unitary [1.933681537640272]
  We design provable algorithm to determine T-count of any $n$-qubit ($ngeq 1$) unitary $W$ of size $2ntimes 2n$, over the Clifford+T gate set. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary.
  arXiv  Detail & Related papers  (2021-10-19T22:16:00Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits [1.933681537640272]
  We use nested meet-in-the-middle technique to develop algorithms for synthesizing provably emphdepth-optimal and emphT-depth-optimal circuits. For synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity $Oleft(left(4n2right)lceil d/crceilright)$. Our algorithm has space and time complexity $poly(n,25.6n,d)$ (or $poly(nlog n,
  arXiv  Detail & Related papers  (2021-01-08T18:13:36Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)
• A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
  This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes. We consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set.
  arXiv  Detail & Related papers  (2020-06-22T17:21: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.