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

Quantum Information and Computation

Optimal realizations of simplified Toffoli gates

SongGuang, KlappeneckerAndreas

Published Sep 1, 2004• 0 citations
Publisher

Abstract

A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate i...
DOI
10.5555/2011586.2011588

Related papers

Optimal realizations of simplified Toffoli gates

Guang Song, Andreas Klappenecker

A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate implementation by Margolus is optimal, in the sense that it attains a lower bound of {\em three} controlled-not gates, and subject to that, a sharp lower bound of {\em four} single-qubit gates. We also discuss optimal implementations of other simplified Toffoli gates, and explain why the phase factor $-1$ invariably occurs in such implementations.

Quantum Information and Computation•Sep 1, 2004•10 citations

Factorizations of Toffoli gate and quantum phase estimation

Yin Jun-chen

Factorizations of Toffoli gate and quantum phase estimation are given and proved so that they can be well-understanded and used.

Computer Engineering and Applications Journal•Jan 1, 2009•0 citations

The simplified Toffoli gate implementation by Margolus is optimal

Guang Song, Andreas Klappenecker

Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.

arXiv:quant-ph/0312225•Dec 31, 2003•11 citations

Both Toffoli and controlled-NOT need little help to do universal quantum computing

ShiYaoyun

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We prove that any single-qubit real gate suffices, except those that preserve the comput...

Quantum Information and Computation•Jan 1, 2003•30 citations

Using S Gates and Relative Phase Toffoli Gates to Improve T-Count in Quantum Boolean Circuits

David Clarino, Shohei Kuroda, Shigeru Yamashita

Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, a non-transversal gate like the T gate incurs extra cost relative to transversal gates like the S and CNOT gates. Relative-phase Toffoli Gates (RTOF) have been proposed as a way to minimize this "T-depth" at the cost of incurring a relative phase that could skew the final quantum states. While previous research has proposed a way to use transversal S gates to eliminate this relative phase, this paper proposes a novel form of the RTOF that incorporates S gates in order to simplify generation of the logic to return the phase

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2023•0 citations

Simplification of Toffoli networks via templates

Dmitri Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with Ñ gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for Ñ � � are described in this paper. 1

Symposium on Integrated Circuits and Systems Design•Sep 8, 2003•44 citations
A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate implementation by Margolus is optimal, in the sense that it attains a lower bound of {\em three} controlled-not gates, and subject to that, a sharp lower bound of {\em four} single-qubit gates. We also discuss optimal implementations of other simplified Toffoli gates, and explain why the phase factor −1-1−1 invariably occurs in such implementations.
Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.
Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, a non-transversal gate like the T gate incurs extra cost relative to transversal gates like the S and CNOT gates. Relative-phase Toffoli Gates (RTOF) have been proposed as a way to minimize this "T-depth" at the cost of incurring a relative phase that could skew the final quantum states. While previous research has proposed a way to use transversal S gates to eliminate this relative phase, this paper proposes a novel form of the RTOF that incorporates S gates in order to simplify generation of the logic to return the phase
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with Ñ gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for Ñ � � are described in this paper. 1