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

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.

Figure 1

(a) A multiple control Toffoli gate $\mathrm{TOF}(X;y)$. (b) A diagonal gate $D_1(X;y)$ and its inverse. Observe how different diagonal gates can be visually distinguished by the number within the control, and a diagonal gate and its inverse are related by the different color of the control. (c) A relative-phase multiple control Toffoli gate $\mathrm{R}{}_1\mathrm{TOF}(X;y)$ and its inverse $\mathrm{R}{}_1^{-1}\mathrm{TOF}(X;y)$. (d) A type-$y$ special form $\mathrm{S}{}^y\mathrm{R}{}_1\mathrm{TOF}(X;y)$, and its inverse. (e) A controlled-unitary $U$ implemented up to some relative phase. The $/$—symbol denotes a multiqubit register.

Figure 2

(a) and (b) Implementation of $\mathrm{TOF}{}^6$ on qubits 1–9 using $\mathrm{S}{}^{\left\{8\right\}}\mathrm{RTOF}{}^3$ and its inverse, and 10 $\mathrm{RTOF}{}^3$ gates. (a)–(c) Implementation of $\mathrm{TOF}{}^6$ using a narrow selection of the relative-phase and special form relative-phase Toffoli gates.

Figure 3

Toffoli gate implemented up to a relative phase. Gates 1–10 implement a type-$\left\{c\right\}$ special relative-phase Toffoli gate, known as the controlled-controlled-$iX$ in [7], whereas circuit with gates 2–10 implement some generic relative-phase Toffoli gate. The controlled-$Z$ gate $CZ(a;c)$ may commute through the Hadamard $H\left(c\right)$, at which point it will change into cnot$(a;c)$, and the circuit will show in an alternate form. It may be established, via applying the result of Corollary t5, that the cnot count of the circuit with gates 2–10 is optimal.

Figure 4

Circuit implementing Toffoli-4 up to a relative phase, $\mathrm{RTOF}(a,b,c;d)$.