Related papers: Any Clifford+T circuit can be controlled with constant T-depth overhead

Any Clifford+T circuit can be controlled with constant T-depth overhead

URL: http://arxiv.org/abs/2512.24982v1
Date: Wed, 31 Dec 2025 17:28:07 GMT
Title: Any Clifford+T circuit can be controlled with constant T-depth overhead
Authors: Isaac H. Kim, Tuomas Laakkonen,
Abstract summary: 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.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Since an n-qubit circuit consisting of CNOT gates can have up to $Ω(n^2/\log{n})$ CNOT gates, it is natural to expect that $Ω(n^2/\log{n})$ Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision $ε$ in T-depth exactly 1 using a universal $\lceil\log_2(8/ε)\rceil$-qubit catalyst state.

Related papers

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)
On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition [5.286310769012741]
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.
arXiv Detail & Related papers (2025-02-03T15:16:11Z)
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)
Optimising quantum circuits is generally hard [0.0]
We find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. We show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set.
arXiv Detail & Related papers (2023-09-12T09:35:23Z)
CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate [5.672898304129217]
A Hadamard-free Clifford transformation is a circuit composed of quantum Phase (P), CZ, and CNOT gates. In this paper, we focus on the minimization of circuit depth by entangling gates, corresponding to the important time-to-solution metric and the reduction of noise due to decoherence.
arXiv Detail & Related papers (2022-10-28T15:04:55Z)
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)
Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
Kitaev's quantum double model based on a finite group $G$. We describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement.
arXiv Detail & Related papers (2022-05-04T08:10:36Z)
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)
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)
On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
We show that commonly held intuitions when designing quantum circuits can be misleading. We show that reducing the T-count can increase the total depth. We illustrate our method on addition and multiplication circuits using ripple-carry.
arXiv Detail & Related papers (2021-01-12T21:36:16Z)

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