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 Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)

Lower cost quantum gate realizations of multiple-control Toffoli gates

D. Michael Miller

Published Aug 1, 2009• 15 citations
Publisher

Abstract

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.

DOI
10.1109/pacrim.2009.5291355

Related papers

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

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

Primitive quantum gate realizations of multiple-controlled Toffoli gates

Mozammel H. A. Khan

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.

International Conference on Computer and Information Technology (ICCIT)•Mar 1, 2014•1 citation

Dynamic Realization of Multiple Control Toffoli Gate

Abhoy Kole, Arighna Deb, Kamalika Datta +1 more

Dynamic Quantum Circuits (DQC) is an inevitable solution for today's Noisy Intermediate Scale Quantum (NISQ) systems. This enables realization of an n-qubit (where,$n > 2$) quantum circuit using only 2-qubits with the aid of additional non-unitary operations which is evident from the recent dynamic realizations of algorithms like Quantum Phase Estimation (QPE) and Bernstein- Vazirani (BV) as well as 3-qubit Toffoli operation. In this work, we introduce two different dynamic realization schemes for Multiple Control Toffoli (MCT) gates, for the first time to the best of our knowledge. We compare the respective realizations in terms of resources (e.g., gate, depth and nearest neighbor overhead) and computational accuracy. For this purpose, we apply the proposed dynamic MCT gates in Deutsch-Jozsa (DJ) algorithm, thereby realizing the traditional DJ algorithm as DQCs. Experimental evaluations show that one dynamic scheme for MCT gates leads to DQCs with better computational accuracy, while the other one results in DQCs with better computational resources.

Design, Automation, and Test in Europe•Mar 25, 2024•6 citations

NCV realization of MCT gates with mixed controls

Zahra Sasanian, D. Michael Miller

Multiple-control Toffoli (MCT) gates are widely used in the synthesis of reversible circuits. These gates are not usually directly implemented and need to be mapped to circuits of more elementary components such as quantum gates. In this work, the realization of MCT gates with mixed controls is explored for the NCV quantum library containing NOT, CNOT, V and V+gates. The results show that the proposed approach significantly improves the best known NCV costs for MCT gates.

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

Quantum Circuit Simplification Using Templates

D. Maslov, Cho Eun Young, D. Michael Miller +1 more

Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.

Design, Automation, and Test in Europe•Apr 1, 2005•114 citations
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.
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.
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.
Dynamic Quantum Circuits (DQC) is an inevitable solution for today's Noisy Intermediate Scale Quantum (NISQ) systems. This enables realization of an n-qubit (where,n>2n > 2n>2) quantum circuit using only 2-qubits with the aid of additional non-unitary operations which is evident from the recent dynamic realizations of algorithms like Quantum Phase Estimation (QPE) and Bernstein- Vazirani (BV) as well as 3-qubit Toffoli operation. In this work, we introduce two different dynamic realization schemes for Multiple Control Toffoli (MCT) gates, for the first time to the best of our knowledge. We compare the respective realizations in terms of resources (e.g., gate, depth and nearest neighbor overhead) and computational accuracy. For this purpose, we apply the proposed dynamic MCT gates in Deutsch-Jozsa (DJ) algorithm, thereby realizing the traditional DJ algorithm as DQCs. Experimental evaluations show that one dynamic scheme for MCT gates leads to DQCs with better computational accuracy, while the other one results in DQCs with better computational resources.
Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.