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

Optimal Control and Circuit Synthesis of Quantum Gates

Hyeong-Jin Kim

•Jan 1, 2021•0 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

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

Xueyun Cheng, Zhijin Guan, Weiping Ding

Quantum Information Processing•May 29, 2018•13 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

Synthesis and Optimization of Quantum Boolean Circuit Using the Truth Table Method

Fatma Hamzaoui, Roselyne Chotin-Avot, Patricia Renault +3 more

•Apr 26, 2012•0 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.
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.