8
Two Qubits, Three

In the previous chapter we defined qubits and saw what we could do with just one of them. Things now start to get exponential with every additional qubit added, because entanglement allows the size of the working state space to double.

This chapter is about seeing how multiple qubits can behave together and then building a collection of tools to manipulate those qubits. These include the concept of entanglement, which is a requirement to do quantum computing. We also examine important 2-qubit gates like CNOT and SWAP. This will lead us into chapter 9 and chapter 10 where we look at algorithms and build circuits that use this machinery.

All vector spaces considered in this chapter are over C, the field of complex numbers introduced in section 3.9 . All bases are orthonormal unless otherwise specified.

Topics covered in this chapter

8.1 Tensor products

In this section I introduce the linear algebra construction of a tensor product. If the direct sum seems to concatenate two vector spaces, then the tensor product interleaves them. In the first case, if we start with dimensions n and m, we end up with a new vector space of n + m dimensions. For the tensor product, we get n m dimensions.

We can quickly get vector spaces with high dimensions through this multiplicative effect. This means we need to use our algebraic intuition and tools more than our geometric ones.

The initial construction is straight linear algebra but we specialize it to quantum computing and working with multiple qubits in the next section.

Let V and W be two finite dimensional vector spaces over F. Define a new vector space V ⊗ W, pronounced ‘‘V tensor W’’ or ‘‘the tensor product of V and W,’’ to be the vector space generated by addition and scalar multiplication of all objects v ⊗ w for each v in V and w in W.

Tensor products have the following properties:

• If a is a scalar in F then
  a (v ⊗ w) = (av) ⊗ w = v ⊗ (a w).
• For v₁ in V and w₁ and w₂ in W,
  v₁ ⊗ (w₁ + w₂) = v₁ ⊗ w₁ + v₁ ⊗ w₂.
• For v₁ and v₂ in V and w₁ in W,
  (v₁ + v₂) ⊗ w₁ = v₁ ⊗ w₁ + v₂ ⊗ w₁.
• If f: V × W → U is a bilinear map, then f^⊗: V ⊗ W → U is a linear map defined by
  f^⊗(v ⊗ w) = f(v, w).
• If {v₁, v₂, …, v_n} and {w₁, w₂, …, w_m } are bases for V and W, then

  v1 ⊗ w1,	v1 ⊗ w2, …, v1 ⊗ wm,
  	⋮
  vn ⊗ w1,	vn ⊗ w2, …, vn ⊗ wm

  are basis vectors of V ⊗ W. There are n m of them and this is the dimension of V ⊗ W.

For two additional vectors spaces X and Y over F, if

are linear maps, then so is where we define

If f and g are both monomorphisms, so is f ⊗ g. If they are both epimorphisms, so is f ⊗ g.

If we have

then the regular matrix product is The matrix tensor product for 2 by 2 matrices is and this is respect to the e₁ ⊗ e₁ e₁ ⊗ e₂, e₂ ⊗ e₁, and e₂ ⊗ e₁ basis. I’m abusing the notation a bit in the second line to show we get a block of elements in the new matrix by multiplying an entry of the first by every entry in the second. The same kind of construction rules applies for larger matrices.

We do something similar with vectors. If v = (v₁, v₂, v₃) in V and w = (w₁, w₂) in W, then

I’ve again taken liberties in the second term to show we get three entries by multiplying the second vector by an entry in the first. If V and W have Euclidean norms, then

This is true in general for finite dimensional vector spaces V and W with Euclidean norms.

For R² ⊗ R² or C² ⊗ C²,

Tensor products combine nicely with traditional products. For two additional matrices,

We now take a brief culinary diversion to again compare direct sums and tensor products. Let V be the vector space with basis chocolate ice cream, vanilla ice cream, and mint chocolate chip ice cream. For the second vector space W, the basis is chocolate fudge sauce, caramel sauce, mango sauce, and raspberry sauce.

Vectors in V ⊕ W are linear combinations of the 7 (= 3 + 4) foods

Vectors in V ⊗ W are linear combinations of the 12 (= 3 × 4) food combinations:

We get every possible pairing with the tensor product. I think the last three are the most questionable flavor mixtures. Now back to the math.

Consider C². Both C² ⊕ C² and C² ⊗ C² have four dimensions. These are isomorphic: we have an invertible linear map from all of the first vector space to all of the second. What is it?

Let e₁ = (1, 0) and e₂ = (0, 1) be the standard basis on C². Since C² ⊕ C² = C⁴, it has the standard basis f₁ =(1, 0, 0, 0), f₂ = (0, 1, 0, 0), f₃ = (0, 0, 1, 0), and f₄ = (0, 0, 0, 1). (I’m using ‘‘f’’ instead of ‘‘e’’ in this second case to avoid confusion.)

Define S: C² ⊕ C² = C⁴ → C² ⊗ C² by

This is not the only isomorphism but it is natural given our calculation of the coordinates of the vectors like e₁ ⊗ e₂ above.

Another interesting basis for C² ⊗ C² is

Continuing on, C² ⊕ C²⊕ C² = C⁶ but C² ⊗ C²⊗ C² has 8 dimensions. If we tensor ten copies of C² together we get 2¹⁰ = 1024 dimensions.

In the next section, we use the tensor product as the underpinning of qubit entanglement and show what they look like and how they behave with bra-ket notation.

8.2 Entanglement

We’ve now seen many gate operations that you can apply to a single qubit to change its state. In section 2.5 we worked through how to apply classical logic gates to build a circuit for addition.

While we can apply not to a single bit, all the other operations require at least two bits for input. In the same way, we need to work with multiple qubits to produce interesting and useful results.

8.2.1 Moving from one to two qubits

As discussed above, the states of a single qubit are represented by vectors of length 1 in C² and all such states that differ only by multiplication by a complex unit are considered equivalent. Each qubit starts by having its own associated copy of C².

When we have a quantum system with two qubits, we do not consider their collective states in a single C² instance. Instead, we use the tensor product of the two copies of C² and the tensor products of the quantum state vectors. This gives us a four-dimensional complex vector space where this ‘‘4’’ is 2 × 2 rather than the arithmetically equal 2 + 2.

The tensor product is the machinery that allows up to build quantum systems from two or more other systems. The notation for working with these tensor products starts out as fairly bulky but there are significant simplifications that demonstrate the advantages of bras and kets.

From the standard properties of tensor products,

First simplification: we can assume there is a tensor product between basis kets coming from the original but different qubit state spaces. We omit the ‘‘⊗’’ symbols on the right-hand side.

Second simplification: we do not multiply kets in the same state space and so we can drop the subscripts on the basis kets. We use the order in which they are listed to determine where they came from.

Third simplification: we can merge adjacent basis kets inside a single ket. This is new notation for us but shows the conciseness of what Dirac conceived.

When we use general coordinates, it looks like Since we’re going to be looking at and applying matrices, it’s handy to determine the column vector forms for the 2-qubit basis kets in C² ⊗ C²: We compute these from and observe that, for example, Note that ⟨01 | 01⟩ = 1 but ⟨01 | 11⟩ = 0. This is generally true: when both sides are equal for these four vectors, their ⟨ | ⟩ is 1. When the are unequal, they are 0. This is a restatement of saying they are an orthonormal basis.

There is a fourth form I will show you when we look at the general case.

Look at the coefficients in a₁a₂ |00⟩ + a₁b₂ |01⟩ + b₁a₂ |10⟩ + b₁b₂ |11⟩. Is it still true that the sum of the squares of the absolute values of the coefficients equals 1? Why would we expect this to be the case?

When we measure the 2-qubit system, each of their states will drop to |0⟩ or |1⟩. There are four possible outcomes: |00⟩, |01⟩, |10⟩, and |11⟩. The sum of the probabilities of each case occurring must add up to 1.0. By extension from the 1-qubit case, we would expect that in

we would have the coefficients be probability amplitudes. This means the probability of getting |01⟩, for example, is |a₁ b₂|². The sum is therefore

Does the math support this? Lo and behold, it does:

This is pretty spectacular in my view. The mathematical model we have been building up is aligning with the physical interpretation. While it is not surprising from the perspective of why I am talking about it in the first place, the pieces fall together nicely.

Measurement causes the state of each qubit to become, or collapse to, |0⟩ or |1⟩. Do they operate independently or can there be combined qubit states that express a greater linkage than might seem obvious?

If our qubits q₁ and q₂ are in the combined state

Then when we measure we expect to get |10⟩ half the time and |01⟩ the rest of the time, given a large number of measurements. We never get |00⟩ or |11⟩. I now give you q₁ and I keep q₂. I’m very excited to have my qubit and so I immediately measure it. I get a |1⟩! What do you get?

There are two possible states that could be measured to get a |1⟩ for q₂: |01⟩ and |11⟩. But the probability of getting the second is 0! So when measured, you must get |0⟩.

Before measurement, the qubits were in a state of entanglement. They were so tightly correlated so that when the measurement value of one is known, it uniquely determines the second. You cannot do this with bits. With superposition, entanglement is one of the key differentiators between quantum and classical computing.

The entangled state we just used is known as a Bell state and there are four of them:

We used |Ψ⁺⟩ in the example above. Φ is the capital Greek letter ‘‘phi’’ and Ψ is the capital Greek letter ‘‘psi’’. ϕ and ψ are their lowercase counterparts.

Together, the four states |Φ⁺⟩, |Φ⁻⟩, |Ψ⁺⟩, and |Ψ⁻⟩ are an orthonormal basis for C² ⊗ C². They are named after John Stewart Bell, a physicist from Northern Ireland.

Suppose |Ψ⁺⟩ is not entangled. Then there exist a₁, b₁, a₂, and b₂ in C as above with

This gives us four relationships

From the first, either a₁ or a₂ is 0. Assume a₁ = 0. But then 0 = a₁ b₂ = . This is a contradiction. So a₂ must be 0. Again, though, 0 = b₁ a₂ = and we have another impossibility. This means we cannot write |Ψ⁺⟩ as the tensor product of two 1-qubit kets and it is an entangled state. If a 2-qubit quantum state is not entangled then we can separate it into the tensor product of two 1-qubit states. For this reason, if a quantum state is not entangled then it is separable.

There is something I want to highlight that may be confusing at first. If we start with two 1-qubit states like a₁ |0⟩₁ + b₁ |1⟩₁ and a₂ |0⟩₂ + b₂ |1⟩₂ then we use all such tensor products (a₁ |0⟩₁ + b₁ |1⟩₁) ⊗ (a₂ |0⟩₂ + b₂ |1⟩₂) for all possible complex number coefficients to generate the state vector space C² ⊗ C².

This means we construct all possible sums of such tensor product forms. All the forms together do not constitute all of C² ⊗ C² but together with their sums they do.

8.2.2 The general case

Every time we add a qubit to a quantum system to create a new one, the state space doubles in dimension. This is because we multiply the dimension of the original system’s state space by 2 when we do the tensor product. A 3-qubit quantum system has a state space of dimension 8. An n-qubit system’s state space has 2ⁿ dimensions.

It’s much easier to use ket notation like |11010111⟩ than

Knowing we have 8 qubits, we could also write this as |215⟩₈ where the number inside the ket is a whole number in base 10. The subscript indicates how many qubits there are. In the 2-qubit case, When we use the digital form of ket, we number the probability amplitudes/coefficients using the number inside the ket symbol. For a general quantum state with n qubits, and we have

However we write the quantum state, the sum of the squares of the absolute values of the probability amplitudes add up to 1.

If we want to write a ket like

we shorthand it to |0⟩^{⊗ n}. For a given n, let |ϕ⟩ and |ψ⟩ be two computational basis kets. Then If |ϕ⟩ has a 1 in the jth position and 0 elsewhere in its full vector expansion, and |ψ⟩ has a 1 in the kth position and 0 elsewhere, then |ϕ⟩⟨ψ| is the n by n square matrix which has 0s everywhere except for the (j, k) position, where it is 1. For example, Note that |0⟩⟨0| + |1⟩⟨1| = I₂, the 2 by 2 identity matrix.

8.2.3 The density matrix again

If |ψ⟩ is a multi-qubit quantum state, its density matrix is defined in the same way as the 1-qubit case:

That is, if then

The diagonal elements are real, tr (ρ) = 1, and ρ is Hermitian and positive semi-definite. This means that ρ has a unique positive semi-definite square root matrix ρ^1/2.

8.3 Multi-qubit gates

A quantum gate operation that operates on one qubit has a 2 by 2 unitary square matrix in a given basis. For two qubits, the matrix is 4 by 4. For ten, it is 2¹⁰ by 2¹⁰, which is 1024 by 1024. I show by example how to work with common lower dimensional gates and allow you to extrapolate to larger ones.

8.3.1 The quantum H^⊗n gate

We start by looking at what it means to apply a Hadamard H to each qubit in a 2-qubit system. The H gate, or Hadamard gate, has the matrix

operating on C². Starting with the two qubit states Applying H to each qubit means to compute which is the same as for some 4 by 4 unitary matrix H^⊗2. Given the definition of H and the technique of creating a matrix tensor product in section 8.1, we can compute This matrix puts both qubits in a 2-qubit system that are each initially initialized to |0⟩ into superposition. Note the recursive definition of H^⊗2 in terms of matrix blocks of H matrices.

Though we could draw H^⊗2 as having two inputs and two outputs, we instead show it by applying H to each qubit in a circuit.

For a 3-qubit system, the corresponding H^⊗3 matrix is

Earlier I asked you to show that H |0⟩ = |+⟩. That is, From this it follows that Also, The patterns continues. This shows that applying the Hadamard gates to each qubit initialized to |0⟩ creates a balanced superposition involving all the ket basis vectors. The number out front, √2/4 in the last case, is there to ensure that the square of the absolute value of the ket is 1. It is the normalization constant. If you have three classical bits, you can represent all the following but only one at a time:

In contrast, the 3-qubit state H^⊗3 |0⟩₃ contains each of the corresponding ket basis forms at the same time.

This is a situation where the decimal expression for a basis ket is concise. We can rewrite the last equality as

Now is a good time to introduce summation notation. The capital Greek letter sigma is used to express a sum based on a formula. This means we start j at 1 and in turn consider j = 2, j = 3, and j = 4. We let the initial value of the sum be 0 and then add in each evaluation of the formula to the right of Σ with the given value of j. 1 is the lower bound for j and 4 is the upper bound. Here is another example: We don’t only need a constant value for the upper bound and we don’t have to solely use the variable j. The lower bound need not be constant either. With this we can express of the formula for the balanced superposition of n qubits. We can drop the subscript n on the kets if we know we are working with a specific number of qubits. Incidentally, we have similar notation for products. For example, if we factor a positive N in Z into a set of primes {p₁, p₂, …, p_n } and each prime p_j occurs e_i times, then Now let’s turn to 2-qubit gates that are not tensor products of 1-qubit ones. As when we considered those small gates, we examine some of the most commonly used 2-qubit operations.

8.3.2 The quantum SWAP gate

In subsection 7.6.1 we showed the X gate is a bit flip: given |ψ⟩ = a |0⟩ + b |1⟩, X |ψ⟩ = b |0⟩ + a |1⟩. Now that we are considering two qubits, is there a gate that switches the qubits? What does this even mean?

As we have seen before, given two qubits

their tensor product is If we tensor them in the reverse order, we get The first and the fourth coefficients are the same but the second and third are switched.

The matrix

is an example of a 4 by 4 permutation matrix. To create a matrix that swaps the second and third coefficient of a ket (or entries in a column vector), begin with I₄ and interchange the second and third columns. This is M. For a general vector, Therefore M(|ψ⟩₁ ⊗ |ψ⟩₂) = |ψ⟩₂ ⊗ |ψ⟩₁. When used this way, we call the quantum gate with this matrix in the standard ket basis the SWAP gate.

When I include the SWAP gate in a circuit it spans two wires. Remember the ×s!

8.3.3 The quantum CNOT / CX gate

The CNOT gate is one of the most important gates in quantum computing. It’s used to create entangled qubits. It’s not the only kind of gate that can do it, but it’s simple and very commonly used.

The ‘‘C’’ in CNOT is for ‘‘controlled.’’ Unlike the 1-qubit X gate, which unconditionally flips |0⟩ to |1⟩ and vice versa, CNOT has two qubit inputs and two outputs. Remember that quantum gates must be reversible. For this reason we must have the same number of inputs as outputs. We call the qubits q₁ and q₂ and their states |ψ⟩₁ and |ψ⟩₂, respectively.

This is the way CNOT works: it takes two inputs, |ψ⟩₁ and |ψ⟩₂.

• If |ψ⟩₁ is |1⟩, then the state of q₁ remains |ψ⟩₁ but |ψ⟩₂ becomes X |ψ⟩₂.
• Otherwise the states of q₁ and q₂ are not changed.

Put another way, CNOT always operates like ID|ψ⟩₁ for q₁. When |ψ⟩₁ = |1⟩, CNOT acts as X |ψ⟩₂ for q₂. Otherwise, it acts as ID |ψ⟩₂. The CNOT is a conditional bit flip.

In the classical case, we create a controlled not from a xor with this circuit:

The matrix for CNOT is

It is a permutation matrix that swaps the third and fourth coefficients of |ψ⟩₁ ⊗ |ψ⟩₂. Note that the upper left 2 by 2 submatrix is I₂ and the lower right 2 by 2 submatrix is the X matrix. It is more obvious if we rewrite the matrix in block form as When I include the CNOT gate in a circuit it spans two wires. The top line is the control qubit.

CNOT operates on the standard C² ⊗ C² basis as

By linearity,

Applying the change-of-basis Hadamard H gates before and after CNOT illustrates an interesting property of CNOT. The matrix form of ○ CNOT ○ is

This reduces to the simpler What can we tell about this? By inspection we can see it is a permutation operation that swaps the second and fourth coefficients of the standard ket expression in C² ⊗ C². The effect of M on the standard basis kets is Examine what happens by looking at the second qubit. If it is |1⟩ then the first qubit flips. If it is |0⟩ then the first qubit remains the same. This is the opposite behavior of CNOT yet it is constructed from it with Hadamard operations before and after. With CNOT it appeared that the state of the second qubit was controlled by the first. In this construction, it is the opposite. By doing the change of basis to and from |+⟩ and |−⟩ we’ve gotten evidence that CNOT is doing more than we perhaps expected.

If we wanted the control qubit to be the second one in this way, we would draw it with the • on the bottom. This is sometimes called a reverse CNOT.

CNOT is used to create the entangled Bell state vectors. We save the construction until subsection 9.3.2 when we have more of the circuit machinery in hand.

8.3.4 The quantum CY and CZ gates

The CNOT gate is the same as the CX gate. We can also create controlled 2-qubit gates for other 1-qubit gates. In block matrix form,

are the matrices in the standard basis for the CY and CZ gates, respectively. The CZ is a conditional sign flip. These kinds of gates are shown in the following circuit,

with the last two reversed to show that they can operate between arbitrary wires.

In general, if

is a unitary matrix, then the matrix for controlled-U is

8.3.5 The quantum CR_ϕ^z gate

Another useful set of controlled gates are the ones where the action is . The first qubit controls whether the phase change, or rotation around the Bloch sphere z axis, should happen.

The general matrix for is

When I include the gate in a circuit it has what should now be a familiar form. I specify a particular radian value of ϕ such as .

8.3.6 The quantum Toffoli CCNOT gate

The quantum Toffoli CCNOT gate is a double control gate operating on three qubits. If the states of the first two qubits are |1⟩ then it applies X to the third. Otherwise it is ID on the third. In all cases it is ID for the first two qubits.

Its matrix is an 8 by 8 permutation matrix which swaps the last two coefficients, like CNOT.

The CCNOT gate spans three wires in a circuit. The top two lines are the control qubits.

The Toffoli gate is also known as the CCX gate.

8.3.7 The quantum Fredkin CSWAP gate

The quantum Fredkin CSWAP gate is a control gate operating on three qubits. If the state of the first qubit is |1⟩ then the states of the second and third qubits are swapped, as in SWAP. If it is |0⟩, nothing is changed.

Its matrix is an 8 by 8 permutation matrix.

Like the CCNOT, the CSWAP gate spans three wires. The top line is the control qubit.

8.4 Summary

In this chapter we introduced the standard 2-qubit and 3-qubit gate operations to complement the classical forms from section 2.4. The CNOT gate allows us to entangle qubits. Entanglement, along with superposition and interference, is a key differentiator in quantum computing.

Now that we have a collection of gates, it’s time to put them into circuits and implement algorithms. We begin doing that in the next chapter.

References

[1]

Paul R. Halmos. Finite-Dimensional Vector Spaces. 1st ed. Undergraduate Texts in Mathematics. Springer Publishing Company, Incorporated, 1993.

[2]

W. Heisenberg. Across the frontiers. Ox Bow Press, 1990.

[3]

S. Lang. Algebra. 3rd ed. Graduate Texts in Mathematics 211. Springer-Verlag, 2002.

[4]

Saunders Mac Lane. Categories for the Working Mathematician. 2nd ed. Graduate Texts in Mathematics 5. Springer New York, 1998.