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, 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.
Currently, the most used universal quantum gate set is the augmented Clifford+T set of gates. Most commonly, we use the cost reduction in terms of the T-depth or T-count to implement logic primitives such as the Toffoli gate. While a lot of research has been done in this area, the Clifford+T set of gates is difficult to use for the synthesis of larger multi-controlled NOT gates (CnNOT) or simply larger circuits. To address this issue, in this work, we examine the composition of the Toffoli gate in relation to the T-gates. We adopt an approach based on the logic formalization of the T-gate placement and deduce three main results. First, if the trailing phase is not a concern, we can efficiently reduce the number of T gates. The second result is that to construct CnNOT gates for n>2 the T gates require smaller angles of rotation (analogous to the original scaling problem in the Barenco et al. Toffoli implementation). Lastly, we demonstrate that it is feasible to substitute all T gates with RZrotations, ensuring the correct logic operation and a constant phase across all outputs.
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.
Prior work of Beverland et al. has shown that any exact Clifford+T implementation of the n-qubit Toffoli gate must use at least nT gates. Here we show how to get away with exponentially fewer T gates, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely, the n-qubit Toffoli gate can be implemented to within error ε in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ε))T gates. We also give a matching Ω(log(1/ε)) lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use Ω(n)T gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.
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.
In fault-tolerant quantum circuit synthesis, T gates supplied via magic states dominate space-time cost, while Clifford gates incur negligible overhead. Conventional flows minimize AND count in an {XOR, AND, NOT} basis as a proxy for T, which neglects phase cancellation and can be far from T-optimal. We instead formulate an exact T synthesis problem and canonicalize Boolean functions under Clifford equivalence. By precomputing T-optimal implementations up to seven variables and developing a customized mapper, we reduce the T count by up to 14.3% on EPFL benchmarks and improve the T counts of several cryptographic modules by up to 40%.