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

arXiv:0806.0654 · Physical Review A

Efficient Toffoli gates using qudits

Timothy C. Ralph, Kevin J. Resch, Alexei Gilchrist

Published Feb 16, 2007• 293 citations
arXivHTMLPDF

Abstract

The simplest decomposition of a Toffoli gate acting on 3 qubits requires five 2-qubit gates. If we restrict ourselves to controlled-sign (or controlled-NOT) gates this number climbs to 6. We show that the number of controlled-sign gates required to implement a Toffoli gate can be reduced to just 3 if one of the three quantum systems has a third state that is accessible during the computation---i.e., is actually a qutrit. Such a requirement is not unreasonable or even atypical since we often artificially enforce a qubit structure on multilevel quantums systems (e.g., atoms, photonic polarization plus spatial modes). We explore the implementation of these techniques in optical quantum processing and show that linear optical circuits could operate with much higher probabilities of success.

DOI
10.1103/physreva.75.022313

Related papers

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

Implementation of CNOT and Toffoli gates with higher-dimensional spaces

Wen‐Qiang Liu, Hai‐Rui Wei, L. C. Kwek

Minimizing the number of necessary two-qubit gates is an important task in quantum information processing. By introducing non-computational quantum states in auxiliary spaces, we construct effective circuits for the controlled-NOT (CNOT) gate and the n-control-qubit Toffoli gate with (2n-1) qubit-qudit gates and (2n-2) single-qudit gates. We propose the polarization CNOT and Toffoli gates based on the designed quantum circuits in linear optics by operating on the spatial-mode degree of freedom of photons. Our optical schemes can be achieved with a higher success probability and no extra auxiliary photons are needed.

•Jul 20, 2021•1 citation

Hybrid Toffoli gate on photons and quantum spins

Ming-Xing Luo, Song-Ya Ma, Xiu‐Bo Chen +1 more

Quantum computation offers potential advantages in solving a number of interesting and difficult problems. Several controlled logic gates, the elemental building blocks of quantum computer, have been realized with various physical systems. A general technique was recently proposed that significantly reduces the realization complexity of multiple-control logic gates by harnessing multi-level information carriers. We present implementations of a key quantum circuit: the three-qubit Toffoli gate. By exploring the optical selection rules of one-sided optical microcavities, a Toffoli gate may be realized on all combinations of photon and quantum spins in the QD-cavity. The three general controlled-NOT gates are involved using an auxiliary photon with two degrees of freedom. Our results show that photons and quantum spins may be used alternatively in quantum information processing.

Scientific Reports•Nov 16, 2015•11 citations

On the CNOT-cost of TOFFOLI gates

Vivek Shende, Igor L. Markov

The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, TOFFOLI gates are decomposed into six CNOT gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its CNOT-optimality. We study three-qubit circuits which contain less than six CNOT gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonicity of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOT gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their CNOT-cost, which holds even if ancilla qubits are available.

arXiv:0803.2316•Mar 15, 2008•7 citations

On the CNOT-cost of TOFFOLI gates

Vivek Shende, Igor L. Markov

The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic oper-ations on quantum data, e.g., reversible arithmetic circuits. In physical implementations,however, TOFFOLI gates are decomposed into six CNOT gates and several one-qubit gates.Though this decomposition has been known for at least 10 years, we provide here thefirst demonstration of its CNOT-optimality. We study three-qubit circuits which containless than six CNOT gates and implement a block-diagonal operator, then show that theyimplicitly describe the cosine-sine decomposition of a related operator. Leveraging thecanonical nature of such decompositions to limit one-qubit gates appearing in respectivecircuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOTgates. Additionally, our results offer a complete classification of three-qubit diagonaloperators by their CNOT-cost, which holds even if ancilla qubits are available.

Quantum Information and Computation•May 1, 2009•127 citations

Linear-optics quantum Toffoli and Fredkin gates

Jaromı́r Fiurášek

We design linear-optics multiqubit quantum logic gates. We assume the traditional encoding of a qubit onto the state of a single photon in two modes (e.g., spatial or polarization). We suggest schemes allowing direct probabilistic realization of the fundamental Toffoli and Fredkin gates without resorting to a sequence of single- and two-qubit gates. This yields more compact schemes and potentially reduces the number of ancilla photons. The proposed setups involve passive linear optics, sources of auxiliary single photons or maximally entangled pairs of photons, and single-photon detectors. In particular, we propose an interferometric implementation of the Toffoli gate in the coincidence basis, which does not require any ancilla photons and is experimentally feasible with current technology.

arXiv:quant-ph/0602220•Physical Review A•Jun 9, 2006•106 citations
The simplest decomposition of a Toffoli gate acting on 3 qubits requires five 2-qubit gates. If we restrict ourselves to controlled-sign (or controlled-NOT) gates this number climbs to 6. We show that the number of controlled-sign gates required to implement a Toffoli gate can be reduced to just 3 if one of the three quantum systems has a third state that is accessible during the computation---i.e., is actually a qutrit. Such a requirement is not unreasonable or even atypical since we often artificially enforce a qubit structure on multilevel quantums systems (e.g., atoms, photonic polarization plus spatial modes). We explore the implementation of these techniques in optical quantum processing and show that linear optical circuits could operate with much higher probabilities of success.
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.
Minimizing the number of necessary two-qubit gates is an important task in quantum information processing. By introducing non-computational quantum states in auxiliary spaces, we construct effective circuits for the controlled-NOT (CNOT) gate and the n-control-qubit Toffoli gate with (2n-1) qubit-qudit gates and (2n-2) single-qudit gates. We propose the polarization CNOT and Toffoli gates based on the designed quantum circuits in linear optics by operating on the spatial-mode degree of freedom of photons. Our optical schemes can be achieved with a higher success probability and no extra auxiliary photons are needed.
Quantum computation offers potential advantages in solving a number of interesting and difficult problems. Several controlled logic gates, the elemental building blocks of quantum computer, have been realized with various physical systems. A general technique was recently proposed that significantly reduces the realization complexity of multiple-control logic gates by harnessing multi-level information carriers. We present implementations of a key quantum circuit: the three-qubit Toffoli gate. By exploring the optical selection rules of one-sided optical microcavities, a Toffoli gate may be realized on all combinations of photon and quantum spins in the QD-cavity. The three general controlled-NOT gates are involved using an auxiliary photon with two degrees of freedom. Our results show that photons and quantum spins may be used alternatively in quantum information processing.
The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, TOFFOLI gates are decomposed into six CNOT gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its CNOT-optimality. We study three-qubit circuits which contain less than six CNOT gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonicity of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOT gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their CNOT-cost, which holds even if ancilla qubits are available.
The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic oper-ations on quantum data, e.g., reversible arithmetic circuits. In physical implementations,however, TOFFOLI gates are decomposed into six CNOT gates and several one-qubit gates.Though this decomposition has been known for at least 10 years, we provide here thefirst demonstration of its CNOT-optimality. We study three-qubit circuits which containless than six CNOT gates and implement a block-diagonal operator, then show that theyimplicitly describe the cosine-sine decomposition of a related operator. Leveraging thecanonical nature of such decompositions to limit one-qubit gates appearing in respectivecircuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOTgates. Additionally, our results offer a complete classification of three-qubit diagonaloperators by their CNOT-cost, which holds even if ancilla qubits are available.
We design linear-optics multiqubit quantum logic gates. We assume the traditional encoding of a qubit onto the state of a single photon in two modes (e.g., spatial or polarization). We suggest schemes allowing direct probabilistic realization of the fundamental Toffoli and Fredkin gates without resorting to a sequence of single- and two-qubit gates. This yields more compact schemes and potentially reduces the number of ancilla photons. The proposed setups involve passive linear optics, sources of auxiliary single photons or maximally entangled pairs of photons, and single-photon detectors. In particular, we propose an interferometric implementation of the Toffoli gate in the coincidence basis, which does not require any ancilla photons and is experimentally feasible with current technology.