Basic Circuit Identities and Larger Circuits

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.

Changing the direction of a CNOT gate

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}\).

image0

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}\).

Swapping the states of qubits

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}\).

image1

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.

Adding a control qubit to a gate

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\).

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

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

image4

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?

Approximating a unitary transformation

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?

The Toffoli gate

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\).

image5

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
image6
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]:

image7

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?

Approximate sqrt(T)
Open in composer

Toffoli with flips
Open in composer

CNOT (Reversed)
Open in composer

SWAP Gate
Open in composer

Swap q[0] and q[1]
Open in composer

Controlled-Hadamard
Open in composer

3Q Toffoli state
Open in composer