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

Optimization of Quantum Boolean Circuits by Relative-Phase Toffoli Gates

Shohei Kuroda, Shigeru Yamashita

Published Jan 1, 2022• 4 citations
Publisher
DOI
10.1007/978-3-031-09005-9_2

Related papers

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

Reducing T-count in Quantum Boolean Circuit Synthesis by Allowing a Relative Phase

David Clarino

•Mar 31, 2025•0 citations

Reducing T-Count in Quantum Circuits Using Alternate Forms of the Relative Phase Toffoli Gate

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, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 15, 2024•1 citation

Mapping from multiple-control Toffoli circuits to linear nearest neighbor quantum circuits

Xueyun Cheng, Zhijin Guan, Weiping Ding

Quantum Information Processing•May 29, 2018•16 citations

Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization

Dmitri A Maslov

Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over the regular Toffoli gate is its smaller circuit size. However, its use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative-phase deviations would prevent the relative-phase Toffoli gates from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative-phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the controlled-not count, $T$count, as well as the number of ancillae used. We suggest that a further study of the relative-phase Toffoli implementations and their use may yield other optimizations.

arXiv:1508.03273•Physical Review A•Feb 10, 2016•218 citations

Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

Arul Rhik Mazumder

In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.

quant-pharXiv:2610.38189•Oct 29, 2026•0 citations
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
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, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.
Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over the regular Toffoli gate is its smaller circuit size. However, its use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative-phase deviations would prevent the relative-phase Toffoli gates from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative-phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the controlled-not count, TTTcount, as well as the number of ancillae used. We suggest that a further study of the relative-phase Toffoli implementations and their use may yield other optimizations.
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.