On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition

• URL: http://arxiv.org/abs/2502.01433v3
• Date: Tue, 11 Feb 2025 15:37:27 GMT
• Title: On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition
• Authors: Suman Dutta, Siyi Wang, Anubhab Baksi, Anupam Chattopadhyay, Subhamoy Maitra,
• Abstract summary: We consider the optimized implementation of Multi Toffoli (MCT) using the Clifford $+$ T gate sets.<n>We quantify the trade-off between the Toffoli depth and the depth using the classical 2-controlled Toffoli.
• Score: 5.286310769012741
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford $+$ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the $n$-controlled Toffoli (hereform we will tell $n$-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the ($2$-controlled) Toffoli gate can further be decomposed using Clifford $+$ T, various methodologies are explored too in this regard for trade-off related implications.

Related papers

• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Tensor Decomposition for Non-Clifford Gate Minimization [17.808896175242644]
  Fault-tolerant quantum computation requires minimizing non-Clifford gates, whose implementation via magic state distillation dominates resource costs.<n>We develop methods for this problem, building on a connection between Toffoli count and tensor decomposition over $bbF$.<n>On standard benchmarks, these methods match or improve all reported results for both Toffoli and $T$-count, with most circuits completing in under a minute on a single CPU instead of thousands of TPUs used by prior work.
  arXiv  Detail & Related papers  (2026-02-17T01:11:07Z)
• Any Clifford+T circuit can be controlled with constant T-depth overhead [0.0]
  We show that the Toffoli count can be reduced to O(1) at the cost of 2n Toffoli gates.<n>We also show how to catalyze a rotation by any angle up to precision $$ in T-depth exactly 1 using a universal $lceillog_2(8/)rceil$-qubit catalyst state.
  arXiv  Detail & Related papers  (2025-12-31T17:28:07Z)
• Prefix Sums via Kronecker Products [47.600794349481966]
  We show how to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.<n>As an application, we show how to use these circuits to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.
  arXiv  Detail & Related papers  (2025-12-18T08:49:18Z)
• Multi-qubit Toffoli with exponentially fewer T gates [3.5887330421214063]
  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.
  arXiv  Detail & Related papers  (2025-10-08T16:56:23Z)
• Optimal T depth quantum circuits for implementing arbitrary Boolean functions [4.730360540444164]
  We present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f.<n>We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function.<n>The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations.
  arXiv  Detail & Related papers  (2025-06-02T11:07:54Z)
• Rise of conditionally clean ancillae for efficient quantum circuit constructions [0.06640389895742692]
  We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [NZS24], that bridges the gap between traditional clean and dirty ancillae.<n>They begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation.<n>We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and iteration, particularly with limited ancilla availability.
  arXiv  Detail & Related papers  (2024-07-25T11:38:04Z)
• A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits [0.8192907805418581]
  We give a complete equational theory for 3-qubit quantum circuits over the Toffoli-Hadamard gate set X, CX, CCX, H .
  arXiv  Detail & Related papers  (2024-07-15T18:19:20Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM) We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries [0.0]
  We study the Clifford+Toffoli universal fault-tolerant gate set. We develop Toffoli-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries.
  arXiv  Detail & Related papers  (2024-01-17T03:53:37Z)
• A T-depth two Toffoli gate for 2D square lattice architectures [49.88310438099143]
  We present a novel Clifford+T decomposition of a Toffoli gate. Our decomposition requires no SWAP gates in order to be implemented on 2D square lattices of qubits. This decomposition enables shallower, more fault-tolerant quantum computations on both NISQ and error-corrected architectures.
  arXiv  Detail & Related papers  (2023-11-21T10:33:51Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  We establish efficient and uncoupled learning dynamics so that the trigger regret of each player grows as $O(log T)$ after $T$ repetitions of play. This improves exponentially over the prior best known trigger-regret bound of $O(T1/4)$.
  arXiv  Detail & Related papers  (2022-08-20T20:48:58Z)
• Constructing all qutrit controlled Clifford+T gates in Clifford+T [0.0]
  We show how to construct any qutrit multiple-controlled Clifford+T unitary using just Clifford+T gates. With our results we can construct ancilla-free implementations of multiple-controlled T gates as well as all versions of the qutrit multiple-controlled Toffoli. As an application of our results, we provide a procedure to implement any ternary classical reversible function on $n$ trits as an ancilla-free qutrit unitary.
  arXiv  Detail & Related papers  (2022-04-01T16:21:43Z)
• Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
  We derive improved regret bounds for the Tsallis-INF algorithm of Zimmert and Seldin (2021). In particular, for $C = Thetaleft(fracTlog Tlog T$)$, where $T$ is the time horizon, we achieve an improvement by a multiplicative factor. We also improve the dependence of the regret bound on time horizon from $log T$ to $log frac(K-1)T(sum_ineq i*frac1Delta_
  arXiv  Detail & Related papers  (2021-03-23T12:26:39Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
  arXiv  Detail & Related papers  (2021-02-06T17:07:48Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

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.