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

International Conference on Computer and Information Technology (ICCIT)

Primitive quantum gate realizations of multiple-controlled Toffoli gates

Mozammel H. A. Khan

Published Mar 1, 2014• 1 citation
Publisher

Abstract

Multiple-controlled Toffoli gates are extensively used in quantum and reversible circuits. However, very limited attempt has been made for primitive quantum gate realizations of these gates. In this paper, we present realization of three-qubit Toffoli gate requiring five primitive quantum gates. We then propose realization of four-qubit Toffoli gate requiring 13 primitive quantum gates and one ancilla input. Finally, we propose realizations of (n + 1)-qubit (n > 3 control lines) Toffoli gates using (⌈n/2⌉ + 1)-qubit and (⌊n/2⌋ + 1)-qubit Toffoli gates and ancilla inputs, which make a trade off between quantum cost and number of ancilla inputs. Our proposed method outperforms the best result so far presented in the literature in terms of quantum cost and number of ancilla inputs.

DOI
10.1109/iccitechn.2014.6997380

Related papers

Quantum Realization of Multiple-Valued Feynman and Toffoli Gates without Ancilla Input

Mozammel H. A. Khan

Multiple-valued Feynman and Toffoli gates are used in GFSOP based synthesis of quantum logic circuits. These gates are macro-level gates and need to be realized using technology dependent primitive gates. In this paper, we present ancilla input free architectures for realization of d-valued (dges3 ) Feynman and n-qudit (nges3 ) Toffoli gates on the top of liquid ion-trap realizable Muthukrishnan-Stroud gates. The proposed architectures can be used for any d if GF(d) can be constructed. We show realization examples of ternary, quaternary, and quinary Feynman gates, and 3 and 4-qudit Toffoli gates. The present realizations require either less or equal primitive gates than the previously reported realizations. Moreover, in contrast to the earlier realizations, the present Toffoli gate realizations do not require any ancilla input, which reduce the register width of a synthesized quantum logic circuit.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Jan 1, 2009•22 citations

Low quantum cost realization of generalized peres and toffoli gates with multiple-control signals

Marek Szyprowski, Paweł Kerntopf

Multiple-control Toffoli gates are basic building blocks for reversible and quantum circuits. 3-bit Peres gate can be considered as a pair of 3-bit and 2-bit Toffoli gates, which can be implemented with fewer elementary quantum gates (what defines a metric called quantum cost) than the total number of elementary quantum gates required by each of Toffoli gates implemented separately. Due to this property, Peres gates are often used for quantum cost reduction of reversible circuits. This paper introduces a generalization of the Peres gate with n > 2 control signals. For such generalized gates corresponding quantum circuits are presented. The realizations have quantum cost of n2and require no ancillary signals. The proposed designs are built from elementary quantum gates, which consist of NOT, controlled NOT, controlled `square-roots-of-NOT' (known as controlled V/V+gates) and controlled `higher roots-of-NOT' (up to 2n-1-roots-of-NOT). The obtained quantum circuits are not entangled. The proposed designs are used to construct Toffoli gates of n control signals with quantum cost of 2n2- 2n + 1 and using no ancillary signals. This is an improvement in comparison with 2n+1- 3 and 48n2+ O(n), which are quantum costs of the known designs of the multiple-control Toffoli gate without ancillary signals.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2013•24 citations

Toffoli-porttien toteutuskustannuksien alentaminen approksimaatioilla

Simo Puttonen

The Toffoli gate (controlled-controlled-NOT) and its multi-controlled generalizations are fundamental logical building blocks of quantum algorithms and utilized extensively in pivotal algorithms such as Grover’s algorithm and Shor’s algorithm. Despite being a fundamental logical primitive of quantum algorithms, Toffoli gates must be decomposed to primitive single-qubit and two-qubit gates which are available in physical quantum hardware. These decompositions incur significant implementation costs in circuit depth and gate count, costs that propagate directly to the entire circuit. Consequently, reducing the implementation cots of Toffoli gates provides a direct method of reducing the implementation costs of many quantum algorithms. This thesis evaluates state-of-the-art methods for reducing the implementation costs of Toffoli gates by introducing approximations. While approximations introduce errors to the output of the Toffoli gate, they can reduce the depth and gate count of the implementation. This thesis finds that discrete errors in two-qubit and three-qubit controlled Toffoli gates have been utilized to reduce the gate counts in such a way that the implementation is exact cancelling the errors. Additionally, continuous errors are utilized to reduce the depth of a multi-controlled Toffoli gate decomposition in ancilla-free settings. However, this review also demonstrates other, non-approximate, construction of multi-controlled Toffoli gate, which achieves comparable implementation costs demonstrating marginal gains for the approximation techniques currently.

•Apr 24, 2026•0 citations

Lower cost quantum gate realizations of multiple-control Toffoli gates

D. Michael Miller

A systematic method is presented for realizing multiple-control Toffoli gates using elementary quantum gates. Results are presented showing that for the NOT, controlled-NOT and the two square root of NOT gates, the method produces circuits as good and in certain cases better than those known to date. A major feature of the work reported here is that in addition to the previously studied cases of one and the maximum required ancillary lines, the presented method covers all cases in between. The approach is general and can be directly applied to other sets of elementary gates.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)•Aug 1, 2009•15 citations

Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates

D. Michael Miller, Robert Wille, Zahra Sasanian

A new method for determining elementary quantum gate realizations for multiple-control Toffoli (MCT) gates is presented. The realization for each MCT gate is formed as a composition of realizations of smaller MCT gates. A marking algorithm which is more effective than the traditional moving rule is used to optimize the final circuit. The main improvement is that the resulting circuits make significantly better use of ancillary lines than has been achieved in earlier approaches. Initial results are also presented for circuits with nearest-neighbour communication. These results show that the overall approach is not as effective for that problem indicating that research on direct synthesis of nearest-neighbour quantum circuits should be considered. While, the results presented are for the NCV quantum gate library (i.e. for quantum circuits composed of NOT gates, controlled-NOT gates, and controlled-V=V+gates), the approach can be applied to other libraries of elementary quantum gates.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2011•141 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
Multiple-controlled Toffoli gates are extensively used in quantum and reversible circuits. However, very limited attempt has been made for primitive quantum gate realizations of these gates. In this paper, we present realization of three-qubit Toffoli gate requiring five primitive quantum gates. We then propose realization of four-qubit Toffoli gate requiring 13 primitive quantum gates and one ancilla input. Finally, we propose realizations of (n + 1)-qubit (n > 3 control lines) Toffoli gates using (⌈n/2⌉ + 1)-qubit and (⌊n/2⌋ + 1)-qubit Toffoli gates and ancilla inputs, which make a trade off between quantum cost and number of ancilla inputs. Our proposed method outperforms the best result so far presented in the literature in terms of quantum cost and number of ancilla inputs.
Multiple-valued Feynman and Toffoli gates are used in GFSOP based synthesis of quantum logic circuits. These gates are macro-level gates and need to be realized using technology dependent primitive gates. In this paper, we present ancilla input free architectures for realization of d-valued (dges3 ) Feynman and n-qudit (nges3 ) Toffoli gates on the top of liquid ion-trap realizable Muthukrishnan-Stroud gates. The proposed architectures can be used for any d if GF(d) can be constructed. We show realization examples of ternary, quaternary, and quinary Feynman gates, and 3 and 4-qudit Toffoli gates. The present realizations require either less or equal primitive gates than the previously reported realizations. Moreover, in contrast to the earlier realizations, the present Toffoli gate realizations do not require any ancilla input, which reduce the register width of a synthesized quantum logic circuit.
Multiple-control Toffoli gates are basic building blocks for reversible and quantum circuits. 3-bit Peres gate can be considered as a pair of 3-bit and 2-bit Toffoli gates, which can be implemented with fewer elementary quantum gates (what defines a metric called quantum cost) than the total number of elementary quantum gates required by each of Toffoli gates implemented separately. Due to this property, Peres gates are often used for quantum cost reduction of reversible circuits. This paper introduces a generalization of the Peres gate with n > 2 control signals. For such generalized gates corresponding quantum circuits are presented. The realizations have quantum cost of n2and require no ancillary signals. The proposed designs are built from elementary quantum gates, which consist of NOT, controlled NOT, controlled `square-roots-of-NOT' (known as controlled V/V+gates) and controlled `higher roots-of-NOT' (up to 2n-1-roots-of-NOT). The obtained quantum circuits are not entangled. The proposed designs are used to construct Toffoli gates of n control signals with quantum cost of 2n2- 2n + 1 and using no ancillary signals. This is an improvement in comparison with 2n+1- 3 and 48n2+ O(n), which are quantum costs of the known designs of the multiple-control Toffoli gate without ancillary signals.
The Toffoli gate (controlled-controlled-NOT) and its multi-controlled generalizations are fundamental logical building blocks of quantum algorithms and utilized extensively in pivotal algorithms such as Grover’s algorithm and Shor’s algorithm. Despite being a fundamental logical primitive of quantum algorithms, Toffoli gates must be decomposed to primitive single-qubit and two-qubit gates which are available in physical quantum hardware. These decompositions incur significant implementation costs in circuit depth and gate count, costs that propagate directly to the entire circuit. Consequently, reducing the implementation cots of Toffoli gates provides a direct method of reducing the implementation costs of many quantum algorithms. This thesis evaluates state-of-the-art methods for reducing the implementation costs of Toffoli gates by introducing approximations. While approximations introduce errors to the output of the Toffoli gate, they can reduce the depth and gate count of the implementation. This thesis finds that discrete errors in two-qubit and three-qubit controlled Toffoli gates have been utilized to reduce the gate counts in such a way that the implementation is exact cancelling the errors. Additionally, continuous errors are utilized to reduce the depth of a multi-controlled Toffoli gate decomposition in ancilla-free settings. However, this review also demonstrates other, non-approximate, construction of multi-controlled Toffoli gate, which achieves comparable implementation costs demonstrating marginal gains for the approximation techniques currently.
A systematic method is presented for realizing multiple-control Toffoli gates using elementary quantum gates. Results are presented showing that for the NOT, controlled-NOT and the two square root of NOT gates, the method produces circuits as good and in certain cases better than those known to date. A major feature of the work reported here is that in addition to the previously studied cases of one and the maximum required ancillary lines, the presented method covers all cases in between. The approach is general and can be directly applied to other sets of elementary gates.
A new method for determining elementary quantum gate realizations for multiple-control Toffoli (MCT) gates is presented. The realization for each MCT gate is formed as a composition of realizations of smaller MCT gates. A marking algorithm which is more effective than the traditional moving rule is used to optimize the final circuit. The main improvement is that the resulting circuits make significantly better use of ancillary lines than has been achieved in earlier approaches. Initial results are also presented for circuits with nearest-neighbour communication. These results show that the overall approach is not as effective for that problem indicating that research on direct synthesis of nearest-neighbour quantum circuits should be considered. While, the results presented are for the NCV quantum gate library (i.e. for quantum circuits composed of NOT gates, controlled-NOT gates, and controlled-V=V+gates), the approach can be applied to other libraries of elementary quantum gates.
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.