Efficient Adjoint Operations

Certain adjoint operations can be performed with fewer resources by using measurements and classically conditioned controls. Two examples include the adjoint Elbow and the adjoint QROM that reset a qubit register to |0\rangle. Such operations are commonly found in compute-uncompute patterns applicable to a wide range of domains.

An Elbow is a Toffoli gate where the input of the target qubit must be in state |0\rangle. Ordinarily, a Toffoli gate costs 7 T gates to construct. However, when we stipulate that the initial state of the target qubit is |0\rangle, the cost can be reduced to 4 T gates (see Figure 4 of [1] and Figure 1 below).

Figure 1. Implementation of the Elbow with only 4 T gates, assuming the target qubit begins as state |0\rangle.

The adjoint Elbow, instead, can only be used if the final state of the target qubit is |0\rangle. A naive approach of the adjoint Elbow would require 4 T gates, based on Figure 1. However, implementing the adjoint Elbow with the measurement method, as illustrated in Figure 2, eliminates T gates altogether by using measurements and cheap Clifford gates. Note that this restricts what the input state can be.

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

Inputs

• A Toffoli gate where we know that the target qubit becomes the state |0\rangle.

Outputs

• A decomposition of that operator with 0 T gates.

Example

Below is PennyLane code that illustrates the typical compute-uncompute use case. The adjoint Elbow may be commented out and replaced by the Toffoli gate to verify that the final states are identical. The first two Hadamard gates may be replaced with any single-qubit gates.

import pennylane as qp

dev = qp.device("default.qubit")

qp.decomposition.enable_graph()

@qp.transforms.decompose(
        gate_set = {
        "MidMeasure",
        "CZ",
        "CNOT",
        'Toffoli',
        "Hadamard",
        }
)

@qp.qnode(dev)
def circuit():

    qp.Hadamard(0)
    qp.Hadamard(1)

    qp.Toffoli([0,1,2]) # Note that, ordinarily we would use qml.Elbow rather than qml.Toffoli
    qp.CNOT([2,3])

    # qp.Toffoli([0,1,2])
    qp.adjoint(qp.Elbow)([0,1,2])

    return qp.probs(wires = [0,1,2,3])

qp.drawer.use_style('pennylane')
qp.draw_mpl(circuit)()

Note that the CNOT in the middle represents some calculation performed on the output of the Toffoli gate.

References

[1] "Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity", Ryan Babbush et al., arXiv:1805.03662, 2018.

[2] "Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization", Dominic W. Berry et al., arXiv:1902.02134, 2019.