Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Comment on “Linear-depth quantum circuits for n -qubit Toffoli gates with no ancilla”

Ming-Xing Luo, Hui-Ran Li

Published Aug 18, 2016• 3 citations
Publisher

Abstract

Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary $n$-qubit Toffoli gate with ancillary qubits [M. Saeedi and M. Pedram, Phys. Rev. A 87, 062318 (2013)]. Their circuits are based on an equivalent representation of the not gate regardless of the global phase. However, we find that this equivalence cannot be extended to the controlled-not gate or the $n$-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an $n$-qubit Toffoli gate and an $n$-qubit phase-flip gate.

DOI
10.1103/physreva.94.026301

Related papers

Linear-depth quantum circuits for n -qubit Toffoli gates with no ancilla

Mehdi Saeedi, Massoud Pedram

We design a circuit structure with linear depth to implement an $n$-qubit Toffoli gate. The proposed construction uses a quadratic-size circuit that consists of elementary two-qubit controlled-rotation gates around the $x$ axis and uses no ancilla qubit. Circuit depth remains linear in quantum technologies with finite-distance interactions between qubits. The suggested construction is related to the long-standing construction by A. Barenco et al. [Phys. Rev. A 52, 3457 (1995)], which uses a quadratic-size, quadratic-depth quantum circuit for an $n$-qubit Toffoli gate.

arXiv:1303.3557•Physical Review A•Jun 17, 2013•71 citations

Decomposing (n+1)$(n+1)$‐Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla

Jian Leng, Fan Yang, Xiang‐Bin Wang

Abstract Circuit depth optimization is crucial for implementing quantum algorithms in practical systems. The decomposition of ‐qubit Toffoli gate is continually optimized since this gate is a fundamental component for many quantum algorithms. Without any ancilla, ‐qubit Toffoli gate can be decomposed by standard gates with circuit depth . Here, the decomposition is further optimized and its circuit depth is reduced to . The decomposition is equivalent to ‐qubit Toffoli gate up to an overall phase and also does not need any ancilla.

Advanced Quantum Technologies•Dec 20, 2023•2 citations

Modifying $n$-qubit controlled-$ZX$ gate to be $n$-qubit Toffoli gate

Leng, Jian, Fan Yang, Xiang‐Bin Wang

The decomposition for controlled-$ZX$ gate in [Phys. Rev. A, 87, 062318 (2013)] has a shallow circuit depth $8n-20$ with no ancilla. Here we modify this decomposition to decompose $n$-qubit Toffoli gate with only $2n-3$ additional single-qubit gates. The circuit depth is unchanged and no ancilla is needed. We explicitly show that the circuit after decomposition can be easily constructed in present physical systems.

arXiv:2305.15018•May 24, 2023•0 citations

Generalized Toffoli Gate Decomposition Using Ququints: Towards Realizing Grover’s Algorithm with Qudits

Anastasiia S. Nikolaeva, Evgeniy O. Kiktenko, Aleksey K. Fedorov

Qubits, which are the quantum counterparts of classical bits, are used as basic information units for quantum information processing, whereas underlying physical information carriers, e.g., (artificial) atoms or ions, admit encoding of more complex multilevel states—qudits. Recently, significant attention has been paid to the idea of using qudit encoding as a way for further scaling quantum processors. In this work, we present an efficient decomposition of the generalized Toffoli gate on five-level quantum systems—so-called ququints—that use ququints’ space as the space of two qubits with a joint ancillary state. The basic two-qubit operation we use is a version of the controlled-phase gate. The proposed N-qubit Toffoli gate decomposition has O(N) asymptotic depth and does not use ancillary qubits. We then apply our results for Grover’s algorithm, where we indicate on the sizable advantage of using the qudit-based approach with the proposed decomposition in comparison to the standard qubit case. We expect that our results are applicable for quantum processors based on various physical platforms, such as trapped ions, neutral atoms, protonic systems, superconducting circuits, and others.

arXiv:2212.12505•Entropy•Feb 20, 2023•16 citations

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

IEEE Access•Jan 1, 2023•3 citations

Quantum circuits of T -depth one

Peter Selinger

We give a $\text{Clifford}+T$ representation of the Toffoli gate of $T$-depth one, using four ancillas. More generally, we describe a class of circuits whose $T$-depth can be reduced to one by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most eight additional $T$ gates and $T$-depth two. We also show that the circuit $THT$ does not possess a $T$-depth one representation with an arbitrary number of ancillas initialized to $|0\ensuremath{\rangle}$.

arXiv:1210.0974•Physical Review A•Apr 1, 2013•224 citations
Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary nnn-qubit Toffoli gate with ancillary qubits [M. Saeedi and M. Pedram, Phys. Rev. A 87, 062318 (2013)]. Their circuits are based on an equivalent representation of the not gate regardless of the global phase. However, we find that this equivalence cannot be extended to the controlled-not gate or the nnn-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an nnn-qubit Toffoli gate and an nnn-qubit phase-flip gate.
We design a circuit structure with linear depth to implement an nnn-qubit Toffoli gate. The proposed construction uses a quadratic-size circuit that consists of elementary two-qubit controlled-rotation gates around the xxx axis and uses no ancilla qubit. Circuit depth remains linear in quantum technologies with finite-distance interactions between qubits. The suggested construction is related to the long-standing construction by A. Barenco et al. [Phys. Rev. A 52, 3457 (1995)], which uses a quadratic-size, quadratic-depth quantum circuit for an nnn-qubit Toffoli gate.
Decomposing (n+1)(n+1)(n+1)(n+1)‐Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla
Abstract Circuit depth optimization is crucial for implementing quantum algorithms in practical systems. The decomposition of ‐qubit Toffoli gate is continually optimized since this gate is a fundamental component for many quantum algorithms. Without any ancilla, ‐qubit Toffoli gate can be decomposed by standard gates with circuit depth . Here, the decomposition is further optimized and its circuit depth is reduced to . The decomposition is equivalent to ‐qubit Toffoli gate up to an overall phase and also does not need any ancilla.
Modifying nnn-qubit controlled-ZXZXZX gate to be nnn-qubit Toffoli gate
The decomposition for controlled-ZXZXZX gate in [Phys. Rev. A, 87, 062318 (2013)] has a shallow circuit depth 8n−208n-208n−20 with no ancilla. Here we modify this decomposition to decompose nnn-qubit Toffoli gate with only 2n−32n-32n−3 additional single-qubit gates. The circuit depth is unchanged and no ancilla is needed. We explicitly show that the circuit after decomposition can be easily constructed in present physical systems.
Qubits, which are the quantum counterparts of classical bits, are used as basic information units for quantum information processing, whereas underlying physical information carriers, e.g., (artificial) atoms or ions, admit encoding of more complex multilevel states—qudits. Recently, significant attention has been paid to the idea of using qudit encoding as a way for further scaling quantum processors. In this work, we present an efficient decomposition of the generalized Toffoli gate on five-level quantum systems—so-called ququints—that use ququints’ space as the space of two qubits with a joint ancillary state. The basic two-qubit operation we use is a version of the controlled-phase gate. The proposed N-qubit Toffoli gate decomposition has O(N) asymptotic depth and does not use ancillary qubits. We then apply our results for Grover’s algorithm, where we indicate on the sizable advantage of using the qudit-based approach with the proposed decomposition in comparison to the standard qubit case. We expect that our results are applicable for quantum processors based on various physical platforms, such as trapped ions, neutral atoms, protonic systems, superconducting circuits, and others.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.
We give a Clifford+T\text{Clifford}+TClifford+T representation of the Toffoli gate of TTT-depth one, using four ancillas. More generally, we describe a class of circuits whose TTT-depth can be reduced to one by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most eight additional TTT gates and TTT-depth two. We also show that the circuit THTTHTTHT does not possess a TTT-depth one representation with an arbitrary number of ancillas initialized to $|0\ensuremath{\rangle}$.