Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla

• URL: http://arxiv.org/abs/2605.18169v1
• Date: Mon, 18 May 2026 10:11:18 GMT
• Title: Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla
• Abstract summary: Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms.<n>Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead.<n>We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections.
• Score: 1.214455026524814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.

Related papers

• Optimal Toffoli-Depth Multi-Controlled Toffoli Decomposition in 2D Qubit Layout [2.5756681494057045]
  We study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts.<n>We introduce a motif-based packing framework in which interaction motifs are represented by basic Toffoli gates.
  arXiv  Detail & Related papers  (2026-06-13T05:02:39Z)
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates [1.3267048706241158]
  The Toffoli gate is a fundamental building block for quantum arithmetic and reversible logic.<n>Recent advances in dynamic quantum circuit capabilities, including mid-circuit measurement and classical feedforward, provide new opportunities for reducing the resource overhead of non-Clifford operations.<n>We propose a set of dynamic decomposition strategies for multi-controlled Toffoli gates that exploit adaptive circuit execution and ancilla-assisted constructions.
  arXiv  Detail & Related papers  (2026-05-18T10:03:17Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• FIMA-Q: Post-Training Quantization for Vision Transformers by Fisher Information Matrix Approximation [55.12070409045766]
  Post-training quantization (PTQ) has stood out as a cost-effective and promising model compression paradigm in recent years.<n>Current PTQ methods for Vision Transformers (ViTs) still suffer from significant accuracy degradation, especially under low-bit quantization.
  arXiv  Detail & Related papers  (2025-06-13T07:57:38Z)
• Survival of the Optimized: An Evolutionary Approach to T-depth Reduction [2.089191490381739]
  Quantum Error Correction (QEC) is cornerstone of practical Fault-Tolerant Quantum Computing (FTQC)<n>As circuit gates grow, sequential T-gate layers ("T-depth") increase amplifying overhead.<n>We introduce a mathematical formulation that approximates optimal layer merge patterns.<n>We achieve a 2.58x improvement in T-depth over the state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-04-13T00:55:18Z)
• The Art of Optimizing T-Depth for Quantum Error Correction in Large-Scale Quantum Computing [2.089191490381739]
  Quantum Error Correction (QEC) ensures fault tolerance in large-scale quantum computation.<n>Minimizing T-depth is crucial for optimizing resource efficiency in fault-tolerant quantum computing.<n>We introduce an expansion factor-based identity gate insertion strategy to achieve deeper reductions in circuits initially classified as non-reducible.
  arXiv  Detail & Related papers  (2025-03-08T03:48:21Z)
• Scalable improvement of the generalized Toffoli gate realization using trapped-ion-based qutrits [32.33017977520031]
  We experimentally demonstrate a scalable $N$-qubit Toffoli gate improvement using $171$Yb$+$ trapped-ion-based optical-metastable-ground encoded qutrits.<n>We also demonstrate an increase in the algorithm's accuracy by monitoring the leakage from the qubit subspace during a qutrit-based Toffoli gate implementation.
  arXiv  Detail & Related papers  (2024-07-10T15:34:56Z)
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging [0.0]
  Controlled-SWAP and controlled-controlled-NOT gates are at the heart of the original proposal of reversible classical computation. We provide several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity. We also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers.
  arXiv  Detail & Related papers  (2023-05-29T14:46:19Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Accurate methods for the analysis of strong-drive effects in parametric gates [94.70553167084388]
  We show how to efficiently extract gate parameters using exact numerics and a perturbative analytical approach. We identify optimal regimes of operation for different types of gates including $i$SWAP, controlled-Z, and CNOT.
  arXiv  Detail & Related papers  (2021-07-06T02:02:54Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.