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

IEEE International Conference on Nanotechnology (IEEE-NANO)

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

Marek Szyprowski, Paweł Kerntopf

Published Aug 1, 2013• 24 citations
Publisher

Abstract

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.

DOI
10.1109/nano.2013.6721034

Related papers

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

Improved quantum cost for n -bit Toffoli gates

Dmitri A Maslov, Gerhard W. Dueck

An n-bit Toffoli gate quantum circuit based on the realisation proposed by Barenco et al., where some of the Toffoli gates in their construction are replaced with Peres gates, is presented. This results in a significant cost reduction. The main contribution of this presentation is a quantum circuit which simulates the (m+1)-bit Toffoli gate with 32m−120 elementary quantum gates and one garbage bit which is passed unchanged.

arXiv:quant-ph/0403053•Electronics Letters•Dec 11, 2003•137 citations

A Quantum Cost 9 Reversible Full Adder with Single-Toffoli Complexity

GEORGE PAPAKONSTANTINOU

The minimization of Quantum Cost (QC), specifically the number of Toffoli gates, is a primary objective in the synthesis of reversible arithmetic circuits. For decades, the Peres Full Adder has been considered the benchmark for minimal realizations, requiring 2 Toffoli gates and a Quantum Cost of 12. In this note, we propose a novel reversible Full Adder circuit that utilizes only one Toffoli gate and four CNOT gates. The proposed design achieves a Quantum Cost of 9, representing a 25% reduction compared to the Peres structure, while maintaining a competitive logical depth of 4. We rigorously verify the logic and demonstrate that the reduction is achieved through the automated synthesis framework recently proposed by the authors.

•Jan 27, 2026•1 citation

Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques

Md. Belayet Ali, Takashi Hirayama, Katsuhisa Yamanaka +1 more

Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.

International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 1, 2015•18 citations

Pairwise decomposition of toffoli gates in a quantum circuit

Nathan O. Scott, Gerhard W. Dueck

Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 4, 2008•13 citations

Quantum circuit for multi-qubit Toffoli gate with optimal resource

Nie, Junhong, Wei Zi, Xiaoming Sun

Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the $n$-Toffoli gate and general multi-controlled unitary, which have only $O(\log n)$-depth and $O(n)$-size, and only require $1$ ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of $O(\log^2n)$ and size of $O(n)$ without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.

arXiv:2402.05053•Feb 7, 2024•4 citations
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.
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.
The minimization of Quantum Cost (QC), specifically the number of Toffoli gates, is a primary objective in the synthesis of reversible arithmetic circuits. For decades, the Peres Full Adder has been considered the benchmark for minimal realizations, requiring 2 Toffoli gates and a Quantum Cost of 12. In this note, we propose a novel reversible Full Adder circuit that utilizes only one Toffoli gate and four CNOT gates. The proposed design achieves a Quantum Cost of 9, representing a 25% reduction compared to the Peres structure, while maintaining a competitive logical depth of 4. We rigorously verify the logic and demonstrate that the reduction is achieved through the automated synthesis framework recently proposed by the authors.
Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.
Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.
Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the nnn-Toffoli gate and general multi-controlled unitary, which have only O(log⁡n)O(\log n)O(logn)-depth and O(n)O(n)O(n)-size, and only require 111 ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of O(log⁡2n)O(\log^2n)O(log2n) and size of O(n)O(n)O(n) without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.