Basic circuit identities and larger circuits¶
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 ) using a CNOT gate that acts in the opposite direction, from control qubit 1 to target qubit 2, . By multiplying the matrices for each gate, you can convince yourself that .
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 .
To see that this is true, it is enough to look at what happens to each classical state , , , and . Let’s consider . The first gate does nothing since the control is . The second gate flips the first qubit, so we have . Finally, the last flips the second qubit and we get . The 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 gate, since this is necessary to run the example on the real device. Try deleting the Pauli and placing a Pauli 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 , prepared by the first Hadamard gate on , is swapped into 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 . The CNOT gate is a controlled- gate. Since we know that and , and furthermore that and , it is straightforward to construct circuits for controlled- and controlled-. This is illustrated in the following figure, where is a Pauli gate , , or , and is a Clifford operation such as , , or .
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- operation if we can find three circuits , , and such that and [Barenco et al., 1995]. There is a general recipe for doing this, but we will just write down a solution for when that you can check for yourself: , , , and . 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, , and then applies the controlled-Hadamard circuit from to . This creates the output state . Try deleting the first Hadamard gate on and replacing it with a bit-flip () 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 unitary transformation cannot be written exactly using our basis. Since is a -rotation, the identity gate (which does nothing) is an approximate gate, but not a very good one. The fifth example, “Approximate sqrt(T)”, gives a much better approximation using Hadamard, S, and T gates. This example first puts the qubit on the equator of the Bloch sphere using a Hadamard gate, then applies the gate sequence. We use state tomography to observe the final state on the Bloch sphere. Had we applied an exact gate, the final state would correspond to the point on the Bloch sphere. How good is the gate approximation? Arbitrarily good approximations exist, so can you find a better one? How might you use these circuits to construct an approximate controlled- 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 , , and 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 .
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 . By tracing through each value of the two control qubits, you can convince yourself that a gate is applied to the target qubit if and only if both controls are . Using ideas we have already described, you could now implement each controlled- gate to arrive at some circuit for the doubly-controlled- 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 on qubits 0 and 1 and identity on qubit 2, so the default output is . 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 , the output labels are actually . This means, for example, that an input of produces output (not ). Finally, the “Toffoli state” example demonstrates the creation of an interesting 3-qubit entangled state 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?
Toffoli with flips
Swap q and q
3Q Toffoli state