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

Lecture notes in computer science

Studying the Cost of n-qubit Toffoli Gates

Francisco José Orts, Gloria Ortega, Ester Martín Garzón

Published Jan 1, 2022• 5 citations
Publisher
DOI
10.1007/978-3-031-08760-8_10

Related papers

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

Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity

Yong He, Ming-Xing Luo, E. Zhang +2 more

International Journal of Theoretical Physics•Apr 26, 2017•91 citations

The Cost of Quantum Gates

Jacob Biamonte

J. Multiple Valued Log. Soft Comput.•Jan 1, 2006•4 citations

Cost-Effective Realization of n-Bit Toffoli Gates for IBM Quantum Computers Using the Bloch Sphere Approach and IBM Native Gates

Ali Al-Bayaty, Marek A. Perkowski

A cost-effective n-bit Toffoli gate is proposed to be realized (or transpiled) based on the layouts (linear, T-like, and I-like) and the number of n physical qubits for IBM quantum computers. This proposed gate is termed the "layout-aware n-bit Toffoli gate". The layout-aware n-bit Toffoli gate is designed using the visual approach of the Bloch sphere, from the visual representations of the rotational quantum operations for IBM native gates. In this paper, we also proposed a new formula for the quantum cost, which calculates the total number of native gates, the crossing connections, and the depth of the final transpiled quantum circuit. This formula is termed the "transpilation quantum cost". After transpilation, our proposed layout-aware n-bit Toffoli gate always has a much lower transpilation quantum cost than that of the conventional n-bit Toffoli gate, where 3 <= n <= 7 qubits, for different IBM quantum computers.

arXiv:2410.13104•Oct 17, 2024•2 citations

THE COST OF QUANTUM GATE PRIMITIVES

Soonchil Lee, Seong-Joo Lee, Taegon Kim +3 more

•Jan 1, 2006•53 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
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.
A cost-effective n-bit Toffoli gate is proposed to be realized (or transpiled) based on the layouts (linear, T-like, and I-like) and the number of n physical qubits for IBM quantum computers. This proposed gate is termed the "layout-aware n-bit Toffoli gate". The layout-aware n-bit Toffoli gate is designed using the visual approach of the Bloch sphere, from the visual representations of the rotational quantum operations for IBM native gates. In this paper, we also proposed a new formula for the quantum cost, which calculates the total number of native gates, the crossing connections, and the depth of the final transpiled quantum circuit. This formula is termed the "transpilation quantum cost". After transpilation, our proposed layout-aware n-bit Toffoli gate always has a much lower transpilation quantum cost than that of the conventional n-bit Toffoli gate, where 3 <= n <= 7 qubits, for different IBM quantum computers.
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.