There are several facts about quantum circuits that can be used to
express more complicated unitary
transformations,
write circuits more concisely, or adapt circuits to experimental
constraints.

In the first example “CNOT (Reverse),” we consider how to implement a
CNOT gate from control qubit 2 to target qubit 1 (notated
\(CNOT_{21}\)) using a CNOT gate that acts in the opposite direction,
from control qubit 1 to target qubit 2, \(CNOT_{12}\). By multiplying
the matrices for each gate, you can convince yourself that
\((H\otimes H)CNOT_{12}(H\otimes H)=CNOT_{21}\).

The Kronecker
product
\(H\otimes H\) in this equation is equal to a four-by-four matrix
\(\frac{1}{\sqrt{2}}\begin{pmatrix} H & H \\ H &
-H\end{pmatrix}\). If you run the example, you will confirm that this
combination of Hadamard and CNOT gates implements a CNOT gate in the
opposite direction. The Pauli
\(X\) acts
to invert the control qubit 2, and the result is \(|11\rangle\) as
expected for \(CNOT_{21}\).

Our second example, “Swap,” demonstrates a building block that allows
you to permute the information stored in a set of qubits. Suppose we
want to exchange the states of a pair of qubits by implementing a SWAP
gate on the pair. There is no SWAP gate in our basis, but we can
construct one from three CNOT gates
\(SWAP_{12}=CNOT_{12}CNOT_{21}CNOT_{12}\).

To see that this is true, it is enough to look at what happens to each classical state \(00\), \(01\), \(10\), and \(11\). Let’s consider \(01\). The first gate \(CNOT_{12}\) does nothing since the control is \(0\). The second gate \(CNOT_{21}\) flips the first qubit, so we have \(11\). Finally, the last \(CNOT_{12}\) flips the second qubit and we get \(10\). The \(1\) has moved from the second qubit to the first. The other cases can be worked out similarly. Now you can see this for yourself by running the “Swap” example below. Notice that we have used the “CNOT (Reverse)” identity to change the direction of the \(CNOT_{21}\) gate, since this is necessary to run the example on the real device. Try deleting the Pauli \(X\) and placing a Pauli \(X\) on qubit 1 instead.

In the experimental device, not all qubits are connected to each
other; therefore, some two-qubit gates cannot be applied directly. In
the third example, “Swap Q0 with Q1,” we show how to swap a pair of
qubits that are not directly connected to each other but share a
common neighbor (in this case Q2). The state \(|+\rangle\), prepared
by the first Hadamard gate on \(Q_0\), is swapped into \(Q_1\) by three
successive SWAP gates.

Some unitary transformations can be constructed exactly using gates in our basis. One set of transformations we use regularly are controlled-Pauli operations, where we apply a Pauli gate to a target qubit if a control qubit is \(|1\rangle\). The CNOT gate is a controlled-\(X\) gate. Since we know that \(HXH=Z\) and \(SXS^\dagger=Y\), and furthermore that \(HH=I\) and \(SS^\dagger=I\), it is straightforward to construct circuits for controlled-\(Z\) and controlled-\(Y\). This is illustrated in the following figure, where \(P\) is a Pauli gate \(X\), \(Y\), or \(Z\), and \(C\) is a Clifford operation such as \(I\), \(S\), or \(H\).

For a more involved example, let’s add a control qubit to a Hadamard
gate to implement a controlled-Hadamard operation:

It turns out that we can write down a circuit for a controlled-\(V\) operation if we can find three circuits \(A\), \(B\), and \(C\) such that \(ABC=I\) and \(e^{i\alpha}AZBZC=V\) [Barenco et al., 1995]. There is a general recipe for doing this, but we will just write down a solution for when \(V=H\) that you can check for yourself: \(A=e^{i3\pi/8}XSHTHS^\dagger\), \(B=e^{-i\pi/8}SHT^\dagger HS^\dagger HSH\), \(C=e^{-i\pi/4}HSH\), and \(e^{i\alpha}=-i\). Combining these circuits as shown here

and making some simplifications, we get the result shown in the fourth
example, “controlled-Hadamard.” This example applies a Hadamard gate
to the control qubit, \(Q_0\), and then applies the controlled-Hadamard
circuit from \(Q_0\) to \(Q_2\). This creates the output state
\(\frac{1}{\sqrt{2}}\left(|00\rangle+|1+\rangle\right)=\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{2}|10\rangle+\frac{1}{2}|11\rangle\).
Try deleting the first Hadamard gate on \(Q_0\) and replacing it with a
bit-flip (\(X\)) to see what happens. Can you implement circuits for
other controlled gates, such as a controlled-S?

Most unitary transformations cannot be written exactly using the gates
we have in our basis; but because our basis is a discrete universal
set, it *is* possible to approximate any unitary transformation to any
accuracy. Let’s see an example of this. The \(\sqrt{T}\) unitary
transformation cannot be written exactly using our basis. Since
\(\sqrt{T}\) is a \(Z\)-rotation, the identity gate (which does nothing)
is an approximate \(\sqrt{T}\) gate, but not a very good one. The fifth
example “Approximate sqrt(T)” gives a much better approximation using
\(17\) Hadamard, S, and T gates. This example first puts the qubit
\(Q_0\) on the equator of the Bloch sphere using a Hadamard gate, then
applies the \(17\) gate sequence. We use state
tomography to
observe the final state on the Bloch sphere. Had we applied an exact
\(\sqrt{T}\) gate, the final state would correspond to the point
\((\frac{\sqrt{2+\sqrt{2}}}{2},\frac{\sqrt{2-\sqrt{2}}}{2},0)\approx
(0.92388,0.38268,0)\) on the Bloch sphere. How good is the \(17\) gate
approximation? Arbitrarily good approximations exist, so can you find
a better one? How might you use these circuits to construct an
approximate controlled-\(T\) unitary transformation?

Our final examples, “Toffoli with flips” and “Toffoli state” demonstrate how to implement the reversible circuit equivalent of the (irreversible, classical) AND gate using gates from our basis. An AND gate has two inputs and one output, and outputs 1 if and only if both inputs are 1. One reason the AND gate is important for computation is that it is a non-linear transformation (a multiplication). Why do we say AND is irreversible? Notice that all three inputs \(00\), \(01\), and \(10\) result in an output of 0. If you see that the output of the gate is 0, you can’t undo the gate because you don’t know which of these three inputs gave you the result. Since there are three possible answers, even if you add another output qubit, you won’t have enough information to undo the gate, since you must distinguish 3 cases, and there are only two choices for the state of the new qubit. However, it is possible to implement AND reversibly using 3 wires. This reversible AND gate is called the Toffoli gate \(TOF|a,b,c\rangle=|a,b,(a\ \mathrm{AND}\ b)\ \mathrm{XOR}\ c\rangle\).

It is not obvious how to build a Toffoli gate from gates in our basis
[Barenco et al.,
1995].
The main idea is illustrated in the following figure

where \(V=\sqrt{U}\). By tracing through each value of the two control
qubits, you can convince yourself that a \(U\) gate is applied to the
target qubit if and only if both controls are \(1\). Using ideas we have
already described, you could now implement each controlled-\(V\) gate to
arrive at some circuit for the doubly-controlled-\(U\) gate. It turns
out that the minimum number of CNOT gates required to implement the
Toffoli gate is 6 [Shende and Markov,
2009]:

The “Toffoli with flips” example below allows you to choose an input
state by changing the single-qubit gates at the beginning of the
circuit. Right now they are set to Pauli \(X\) on qubits 0 and 1 and
identity on qubit 2, so the default output is \(|111\rangle\). You
will notice that the example circuit uses 9 CNOT gates instead of the
optimal number 6. This is because we wrote the circuit so it can run
on the real device, which requires inserting a SWAP gate on qubits 1
and 2 near the end of the circuit. Note that we do not undo this swap,
so if the input qubit labels are \(0,1,2\), the output labels are
actually \(0,2,1\). This means, for example, that an input of \(010\)
produces output \(001\) (not \(010\)). Finally, the “Toffoli state”
example demonstrates the creation of an interesting 3-qubit entangled
state
\(SWAP_{1,2}TOF|++0\rangle_{0,1,2}=\frac{1}{2}\left(|000\rangle+|001\rangle+|100\rangle+|111\rangle\right)\)
that encodes the truth
table of the Toffoli
gate.

Using the Toffoli gate, it is possible to construct more complex
circuits. A single Toffoli gate is sufficient to implement a modulo-4
addition operation between a pair of 2-bit registers or an
increment-by-one operation from one 2-bit register to another. Can you
find circuits for these operations and run them in the Quantum
Composer?