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


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


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 .


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^{j\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^{j3\pi/8}XSHTHS^\dagger , B=e^{-j\pi/8}SHT^\dagger HS^\dagger HSH , C=e^{-j\pi/4}HSH , and e^{j\alpha}=-j . 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?

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 three cases, and there are only two choices for the state of the new qubit. However, it is possible to implement AND reversibly using three 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 six [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 nine CNOT gates instead of the optimal number six. 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) image8

Open in composer

Toffoli with flips image9

Open in composer

CNOT (Reversed) image10

Open in composer

SWAP Gate image11

Open in composer

Swap q[0] and q[1] image12

Open in composer

Controlled-Hadamard image13

Open in composer

3Q Toffoli state image14

Open in composer