Quantum Fourier addition simplified to Toffoli addition

Quantum addition circuits are considered being of two types: (1) Toffoli-adder circuits which use only classical reversible gates (controlled-not and Toffoli), and (2) QFT-adder circuits based on the quantum Fourier transformation. We present a systematic translation of the QFT addition circuit into a Toffoli-based adder. This result shows that QFT addition has fundamentally the same fault-tolerance cost (e.g., T count) as the most cost-efficient Toffoli adder: instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates. In order to achieve this, we formulated circuit identities for multicontrolled gates and apply the identities algorithmically. The employed techniques can be used to automate quantum circuit optimization heuristics.

Figure 1

A three-qubit QFT adder for adding the numbers A and B. The three-qubit register A is orange, and the three-qubit register B is green. The blue regions are the QFTs (direct $QFT$ and inverse $QF{T}^{†}$). The red region includes the controlled rotations.

Figure 2

A QFT adder expressed using multiqubit Toffoli gates. Similarly to the initial circuit, the number of controlled operations by the qubits from A is maintained. For example, the third qubit from A was controlling three rotations in the QFT case, and now it is part of three Toffoli gates.

Figure 3

(a) The direction of controlled rotations around the $z$ axis can be changed, in this example, the controlled-S gate. (b) Hadamard gates are merged into $n$-qubit Toffoli gates (in this example cnot).

Figure 4

Inserting a QFT (green, left) and its inverse (red, right) between two controlled rotations. This leaves the computation unchanged because the QFTs cancel. The controlled rotation gates will be used to form larger angle rotations until multiqubit CCZ gates are obtained. The newly inserted Hadamards will be merged together with existing Hadamard gates (not illustrated) and multiqubit CCZ gates to form multiqubit Toffoli gates.

Figure 5

Implementing a CZ with controlled-S gates. The circuit identity holds in general for $V^2=U$. In this example, $V=S$ and $U=Z$.

Figure 6

Equivalent circuit for a double controlled unitary $Z$; adding second controls to the first two controlled-S gates does not change the computation.

Figure 7

Removing the controls from the cnots does not change the computation. Two double controlled-S gates and a single controlled-S gate to implement a double controlled-Z.

Figure 8

Multiqubit controlled gate, where $U=Z$ using $V=S$.

Figure 9

Example of using the SQRT identity as a step during the translation algorithm. The left-hand side is a subcircuit appearing in the QFT adder. The right-hand side is the result of applying the SQRT rule.

Figure 10

Example illustrating the correctness of the transformation from Fig. 9. (a) The SQRT rule for T and S gates; (b) a cnot and controlled-T are commuted on the side of the double controlled-S gate; and (c) the second and third wire are swapped.

Figure 11

(a) An inverse and a direct QFT are inserted before the rightmost CZ gate. (b) The two Hadamards surrounding the CZ gate transform it into a CNOT. (c) The controlled-T and controlled-${\mathrm{T}}^{†}$ are commuted right next to the cnot. (d) The direction of the controlled-T gates is changed. (e) The SQRT rule is applied. The result is a double controlled-S gate, a cnot, and a controlled-${\mathrm{T}}^{†}$. (f) The freshly introduced controlled-${\mathrm{T}}^{†}$ cancels with the leftmost controlled-T. (g) The controlled-S and controlled-${\mathrm{S}}^{†}$ are commuted right next to the cnot. (h) The direction of the controlled-S gates is changed. (i) An equivalent circuit to the previous figure. (j) The SQRT rule is applied. The results are a CCZ gate, a cnot, and a controlled-${\mathrm{S}}^{†}$. (k) The direction of the freshly introduced controlled-${\mathrm{S}}^{†}$ is changed. (l) The freshly introduced controlled-${\mathrm{S}}^{†}$ cancels with the leftmost controlled-S. (m) The Hadamards surrounding the CCZ transform the gate into a Toffoli. (n) The controlled-S and controlled-${\mathrm{S}}^{†}$ are commuted right next to the cnot.

Figure 12

(a) The direction of the controlled-S gates is changed. (b) The SQRT rule is applied. The result is a four-qubit controlled-Z gate, a Toffoli and a double controlled-${\mathrm{S}}^{†}$. (c) The double controlled-${\mathrm{S}}^{†}$ cancels with the leftmost double controlled-S. (d) The Hadamards surrounding the CCCZ transform the gate into a four-qubit Toffoli. (e) The Hadamards and the controlled-S gates on the bottom wire cancel. (f) The controlled-T gates on the bottom wire cancel. (g) The two Hadamards are moved next to the CZ. (h) The two Hadamards surrounding the CZ gate transform it into a cnot. (i) The controlled-S and controlled-${\mathrm{S}}^{†}$ are commuted right next to the cnot. (j) The direction of the controlled-S gates is changed. (k) The SQRT rule is applied. The result is a CCZ gate, a cnot and a controlled-${\mathrm{S}}^{†}$. (l) The freshly introduced controlled-${\mathrm{S}}^{†}$ cancels with the leftmost controlled-S. (m) The Hadamards surrounding the targets of the multiple controlled-Z gates change the gates into Toffolis.