Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates

Abstract

The Toffoli gate is a fundamental building block for quantum arithmetic and reversible logic, yet its efficient realization remains a major challenge in both near-term and fault-tolerant quantum architectures. 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. In this work, we propose a set of dynamic decomposition strategies for multi-controlled Toffoli gates that exploit adaptive circuit execution and ancilla-assisted constructions. Our methods systematically reduce entangling-gate count, T-count, and T-depth compared with conventional static decompositions, while preserving fault-tolerance guarantees. Through analytical cost models and experimental evaluation, we demonstrate that relative-phase primitives and measurement-conditioned corrections enable scalable implementations with improved depth and resource efficiency.

References in corpus (11)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Quantum circuits of T-depth one
• Magic State Distillation: Not as Costly as You Think
• Novel constructions for the fault-tolerant Toffoli gate
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Quantum gate teleportation between separated qubits in a trapped-ion processor
• Measurement-Based Long-Range Entangling Gates in Constant Depth
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking