Multi-qubit Toffoli with exponentially fewer T gates

• URL: http://arxiv.org/abs/2510.07223v1
• Date: Wed, 08 Oct 2025 16:56:23 GMT
• Title: Multi-qubit Toffoli with exponentially fewer T gates
• Authors: David Gosset, Robin Kothari, Chenyi Zhang,
• Abstract summary: We show how to get away with exponentially fewer $T$ gates, at the cost of incurring a tiny $1/mathrmpoly(n)$ error.<n>More precisely, the $n$-qubit Toffoli gate can be implemented to within error $epsilon$ in the diamond distance by a randomly chosen Clifford+$T$ circuit.
• Score: 3.5887330421214063
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Prior work of Beverland et al. has shown that any exact Clifford+$T$ implementation of the $n$-qubit Toffoli gate must use at least $n$ $T$ gates. Here we show how to get away with exponentially fewer $T$ gates, at the cost of incurring a tiny $1/\mathrm{poly}(n)$ error that can be neglected in most practical situations. More precisely, the $n$-qubit Toffoli gate can be implemented to within error $\epsilon$ in the diamond distance by a randomly chosen Clifford+$T$ circuit with at most $O(\log(1/\epsilon))$ $T$ gates. We also give a matching $\Omega(\log(1/\epsilon))$ lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use $\Omega(n)$ $T$ gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the $T$-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.

Related papers

• Matchgate synthesis via Clifford matchgates and $T$ gates [0.0]
  Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions.<n>We propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates.<n>We show that this scheme is efficient, as an approximation error $varepsilon_mathbbSO (2n)$ incurred in this smaller-dimensional representation translates at most into an $O(n,varepsilon_mathbbSO (2n))$ error in the exponentially large unitary.
  arXiv  Detail & Related papers  (2026-02-05T08:15:52Z)
• Quantum state preparation with optimal T-count [1.9402062012850008]
  We show how many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $varepsilon$.<n>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 Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem [0.0]
  A recent improvement of the Solovay-Kitaev theorem implies that to approximate any single-qubit gate to an accuracy of $epsilon > 0$ requires $textO(logc[1/epsilon)$ quantum gates with $c > 1.44042$. Here I give a partial answer to this question by showing that this is possible using $textO(log[/epsilon] loglog[/epsilon] cdots)$ FT gates chosen from a finite set depending on the value of $
  arXiv  Detail & Related papers  (2024-06-07T11:21:05Z)
• Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
  We show that when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $mathcalG_n$. We moreover show that $log(n)-2$ ancillas are always sufficient to construct a circuit for $U$.
  arXiv  Detail & Related papers  (2023-11-13T20:46:51Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  An algorithm for reversible logic synthesis is proposed. Map can be written as a tensor product of a rank-($2n-2$) tensor and the $2times 2$ identity matrix.
  arXiv  Detail & Related papers  (2021-07-09T08:18:53Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  We introduce the problem of online convex optimization with continuous switching constraint. We show that, for strongly convex functions, the regret bound can be improved to $O(log T)$ for $S=Omega(log T)$, and $O(minT/exp(S)+S,T)$ for $S=O(log T)$.
  arXiv  Detail & Related papers  (2021-03-21T11:43:35Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)

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.