Efficient Adjoint Operations

Derivation

Figure 1: Derivation of the adjoint Elbow. (a) Definition of the adjoint Elbow, where the target qubit terminates to |0\rangle. (b) \mathrm{Toffoli} gate may be written as a CCZ gate sandwiched by Hadamard gates. (c) The CCZ gate is symmetric, so we can re-write the form to have the Z gate in the centre. (d). Earlier measurement leads to a classically controlled CZ gate.

The derivation is shown in the panels of Figure 1. The Toffoli gate in Figure 1a be written as a CCZ gate sandwiched by Hadamard gates, as in Figure 1b. By symmetry, a CCZ may be rewritten to have the Z gate execute on the middle qubit instead, as in Figure 1c. Based on the deferred measurement principle and that the final state of the target qubit must be |0\rangle, we can move the measurement and the Hadamard gate before the multi-controlled Z gate, creating a CZ gate that is classically controlled instead, as shown in Figure 1d.

Proof

Initial state and the Toffoli gate

In order to prove the equivalence, we will begin with an arbitrary 3-qubit state |\phi\rangle and check that the \mathrm{Toffoli} |\phi\rangle = \mathrm{Adjoint(Elbow)}|\phi\rangle. However, note that we cannot begin with a completely arbitrary state because we must ensure that the output of the target qubit is |0\rangle. It can be proven that the general initial state can be written as:

where the target qubit is furthest on the right. Thus, the state desired after the Toffoli gate is

Now, we will check that the circuit indeed creates |\psi_2\rangle.

Step-by-step walkthrough of the circuit

As mentioned above, the goal of this section is to work through the circuit step-by-step to see how the input state |\psi_1\rangle becomes |\psi_2\rangle. The particular decomposition of the measurement-based adjoint Elbow is depicted in Figure 2.

Figure 2. Implementation of the adjoint Elbow with zero T gates, assuming the target qubit must become state |0\rangle.

After the Hadamard gate, the state |\psi_1\rangle becomes:

Now, qubit 3 must be measured. If the outcome is 0, then the state collapses to:

It is clear that this is equivalent to |\psi_2\rangle, so we do not need to implement any classical control.

However, if the outcome of the measurement of 1, then the state collapses to:

If we apply a CZ gate onto the main register, the state is

Then, we apply a X gate to set qubit 3 to obtain |0\rangle. That yields the desired state, |\psi_2\rangle.

Finally, it is clear that the adjoint Elbow gate and the circuit involving measurements in Figure 2 are equivalent. The latter eliminates all T gates, which are very expensive to execute on hardware.