Basic Circuit Identities and Larger Circuits

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

The following hand-drawing pictures are very important because they show the design principles for quantum 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 CNOT21) using a CNOT gate that acts in the opposite direction, from control qubit 1 to target qubit 2, CNOT12. By multiplying the matrices for each gate, you can convince yourself that (H⊗H)CNOT12(H⊗H)=CNOT21.

At any rate, I am still not convinced how this design principle comes about.

The simulation for ideal processor results in the following distribution:

The simulation for realistic processor results in the following distribution:

The quantum score file is:

x q[2];
h q[1];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
measure q[1];
measure q[2];

Let us prove (H⊗H)CNOT12(H⊗H)=CNOT21:

The matrix representations of CNOT and its reverse CNOT are the same.  Therefore it seems to me mathematically the above proof cannot show the sense of reverse.

Swapping the states of 2 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 SWAP12=CNOT12CNOT21CNOT12.

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 CNOT12 does nothing since the control is 0. The second gate CNOT21 flips the first qubit, so we have 11. Finally, the last CNOT12 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 CNOT21 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.

Mathematically, SWAP12=CNOT12CNOT21CNOT12

This does not tell us much.

Exercise 2. Swap

The simulation for ideal processor results in the following distribution:

The simulation for realistic processor results in the following distribution:

The quantum score file is:

x q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
measure q[1];
measure q[2];

The only thing that makes sense to me as regards to building circuits, is that the circuit consisting 4 Hadamard gates with a CNOT in the middle (“2HC2H” hereafter) appears in the circuit, which is equivalent to an reverse CNOT (meaning that the BLUE CNOT symbol is upside-down).

Now in order to do swap, 2HC2H needs to add one CNOT in front and one CNOT in the back, or SWAP=CNOT+2HC2H+CNOT, for whatever reason!

Swapping the states of 2 qubits connected with a 3rd qubit

In the experimental device, not all qubits are connected to each other; therefore, some two-qubit gates cannot be applied directly. In the third exercise, "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 Q0, is swapped into Q1 by three successive SWAP gates.

Exercise 3. Swap Q0 and Q1

The simulation for ideal processor results in the following qubits:

The simulation for realistic processor results in the following qubits:

The quantum score file is:

h q[0];
cx q[0], q[2];
h q[0];
h q[2];
cx q[0], q[2];
h q[0];
h q[2];
cx q[0], q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
cx q[0], q[2];
h q[0];
h q[2];
cx q[0], q[2];
h q[0];
h q[2];
cx q[0], q[2];
bloch q[0];
bloch q[1];
bloch q[2];

So we use an H gate and 3 SWAP gates for the 3 qubit lines.  Here is the processes: First, the H gate makes Q0 from ground state |0⟩ (or x=0, y=0, z=1) to |+⟩ (or x=1, y=0, z=0). The first SWAP gate then swaps state |+⟩ from Q0 to Q2 so that Q0 becomes ground state |0⟩ (or 0,0,1) and Q2 becomes |+⟩ (or 1,0,0). The second SWAP gate then swaps state |+⟩ from Q2 to Q1 so that Q2 becomes ground state |0⟩ (or 0,0,1) and Q1 becomes |+⟩ (or 1,0,0).  Finally, the third SWAP swaps ground state |0⟩ from Q2 back to Q0 so that both Q0 and Q2 has ground state |0⟩ (or 0,0,1).  This explains the individual Bloch sphere representation for the ideal simulation: the red line is on z-axis for Q0, the orange line is on x-axis for Q1, and the yellow line is on z-axis for Q2.  Meanwhile, it is interesting for the combined Bloch since the red and yellow lines overlap to form an orange line on the z-axis for the ideal-processor simulated result.  However, for the realistic-processor simulation, there is no “exact” value to overlap because of the probabilistic distribution in quantum computing.  So there are three separate lines of red, yellow and orange colors in the combined Bloch sphere.

Note that it is confusing that the Bloch sphere has the following correspondences BUT STILL MEANS SINGLE-QUBIT STATE for each individual circuit line, NOT A COMBINED Q0,Q2,Q3 state.

|0⟩ à (0,0,1)

|1⟩ à (0,0,-1)

|+⟩ à (1,0,0)

|-⟩ à (-1,0,0)

|i⟩ à (0,1,0)

|-i⟩ à (0,-1,0).

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⟩. The CNOT gate is a controlled-X gate. Since we know that HXH=Z and SXS†=Y, and furthermore that HH=I and SS†=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.

Summarizing the above description, I guess the author’s “straightforward” ways to construct controlled-X, controlled-Y and controlled-Z are:

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 eiα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=ei3π/8XSHTHS†, B=e−iπ/8SHT†HS†HSH, C=e−iπ/4HSH, and eiα=−i.

From the Barenco’s paper, we know ZZ=I and ZR(θ)Z= R(-θ). Therefore, the paper uses a trick to split B in the following formulas and insert ZZ into the split B.

eiαAZBZC

= (eiα)(ei3π/8XSHTHS†)·Z·(e−iπ/8SHT†HS†HSH)·Z·(e−iπ/4HSH)

= (eiα)(ei3π/8XSHTHS†)·Z·(e−iπ/16SHT†HS†)·Z·Z·(e−iπ/16HSH)·Z·(e−iπ/4HSH)

= (eiα)(ei3π/8XSHTHS†)(eiπ/16SHT†HS†)(eiπ/16HSH)(e−iπ/4HSH)

= (eiα)(e−iπ/4)(ei3π/8XSHTHS†)(e−iπ/8SHT†HS†HSH)(e−iπ/4HSH)

This derivation may be wrong since the result cannot deliver output state (|00⟩+|1+⟩) as said below.

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, Q1, and then applies the controlled-Hadamard circuit from Q1 to Q2. This creates the output state

Try deleting the first Hadamard gate on Q1 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?

Exercise 4. Controlled-Hadamard

The simulation for ideal processor results in the following distribution:

The simulation for realistic processor results in the following distribution:

The quantum score file is:

h q[1];
s q[1];
h q[2];
sdg q[2];
cx q[1], q[2];
h q[2];
t q[2];
cx q[1], q[2];
t q[2];
h q[2];
s q[2];
x q[2];
measure q[1];
measure q[2];

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 √T unitary transformation cannot be written exactly using our basis. Since √T is a Z-rotation, the identity gate (which does nothing) is an approximate √T gate, but not a very good one. The fifth exercise "Approximate sqrt(T)" gives a much better approximation using 17 Hadamard, S, and T gates. This example first puts the qubit Q0 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 √T gate, the final state would correspond to the point 

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?

Exercise 5. Approximate sqrt(T)

The simulation for ideal processor results in the following qubits:

The simulation for realistic processor results in the following qubits:

The quantum score file is:

h q[0];
h q[1];
h q[2];
h q[3];
h q[4];
bloch q[0];
h q[1];
t q[2];
s q[3];
z q[4];
t q[1];
bloch q[2];
bloch q[3];
bloch q[4];
h q[1];
t q[1];
h q[1];
t q[1];
s q[1];
h q[1];
t q[1];
h q[1];
t q[1];
s q[1];
h q[1];
t q[1];
h q[1];
t q[1];
h q[1];
bloch q[1];

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⟩=|a,b,(a AND b) XOR c⟩.

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=√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]:

Finally, the "Toffoli state" exercise below demonstrates the creation of an interesting 3-qubit entangled state SWAP1,2TOF|++0⟩0,1,2 = 1/2(|000⟩ + |001⟩ + |100⟩ + |111⟩) that encodes the truth table of the Toffoli gate.

Exercise 6. Toffoli state

The simulation for ideal processor results in the following distribution:

The simulation for realistic processor results in the following distribution:

The quantum score file is:

h q[0];
h q[1];
h q[2];
cx q[1], q[2];
tdg q[2];
cx q[0], q[2];
t q[2];
cx q[1], q[2];
tdg q[2];
cx q[0], q[2];
t q[1];
t q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
cx q[0], q[2];
t q[0];
h q[1];
tdg q[2];
cx q[0], q[2];
measure q[0];
measure q[1];
measure q[2];

Toffoli with flips

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

Exercise 7. Toffoli with flips

The simulation for ideal processor results in the following distribution:

The simulation for realistic processor results in the following distribution:

The quantum score file is:

x q[0];
x q[1];
id q[2];
h q[2];
cx q[1], q[2];
tdg q[2];
cx q[0], q[2];
t q[2];
cx q[1], q[2];
tdg q[2];
cx q[0], q[2];
t q[1];
t q[2];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
h q[1];
h q[2];
cx q[1], q[2];
cx q[0], q[2];
t q[0];
tdg q[2];
cx q[0], q[2];
measure q[0];
measure q[1];
measure q[2];

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?