Solutions to Quantum Computation and Quantum Information

|ψ⟩

Rio Weil & Arnab Adhikary

This document was typeset on June 14, 2024

Introduction:

This document is a (work in progress) collection of comprehensive solutions to the exercises in Nielsen and

Chuang’s “Quantum Computation and Quantum Information”. Each solution has the involved concepts (and

hence rough pre-requisite knowledge) necessary for the problem in addition to the solution. Some problems may

contain additional remarks about implications. Any problems denoted as (Research) are left as exercises to the

reader. Starred exercises are considered to be more diﬃcult (diﬃculty is assumed for the problems at the end of

the chapter).

Contents

1 Introduction and overview 3

2 Introduction to quantum mechanics 5

3 Introduction to computer science 73

4 Quantum circuits 86

10 Quantum error-correction 113

A1 Notes on basic probability theory 146

A2 Group theory 150

1 Introduction and overview

Exercise 1.1: Probabilistic Classical Algorithm

Suppose that the problem is not to distinguish between the constant and balanced functions with certainty,

but rather, with some probability of error ϵ < 1/2. What is the performance of the best classical algorithm

for this problem?

Solution

Concepts Involved: Deutsch’s Problem, Probability.

Recall that a Boolean function f

{0, 1}

→ {0, 1} is said to be balanced if f(x) = 1 for exactly half of

all possible 2

values of x.

A single evaluation tells us no information about whether f is constant or balanced, so our success

rate/error rate after a single evaluation is ϵ =

(random guessing!). Therefore, consider the case where

we do two evaluations. If we obtain two diﬀerent results, then we immediately conclude that f is balanced.

Suppose instead that we obtain two results that are the same. If f is balanced, then the probably that

the ﬁrst evaluation returns the given result is

, and the probability that the second evaluation returns

the same result is

/2−1

−1

(as there are 2

/2 of each result of 0 and 1, 2

total results, 2

/2 − 1 of the

given result left after the ﬁrst evaluation, and 2

−1 total uninvestigated cases after the ﬁrst evaluation).

Therefore, if f is balanced, this occurs with probability

/2−1

−1

, which we can see is less than

as:

< 2

n+1

=⇒ 2

− 2 < 2

n+1

− 2 =⇒

/2 − 1

− 1

< 1 =⇒

/2 − 1

− 1

Hence, if we get the same result in two evaluations, we can conclude that f is constant with error ϵ <

We conclude that only 2 evaluations are required for this algorithm.

Exercise 1.2

Explain how a device which, upon input of one of two non-orthogonal quantum states |ψ⟩ or |φ⟩ correctly

identiﬁed the state, could be used to build a device which cloned the states |ψ⟩ and |φ⟩, in violation

of the no-cloning theorem. Conversely, explain how a device for cloning could be used to distinguish

non-orthogonal quantum states.

Solution

Concepts Involved: Quantum Distinguishability, Quantum Measurement.

Given access to a device which can distinguish non-orthogonal quantum states |ψ⟩, |φ⟩ (without mea-

surement), we can then design a quantum circuit that would map |ψ⟩ 7→ |φ⟩ (or vise versa), allowing us

to clone the states as we like.

Conversely, given a cloning device, we could clone |ψ⟩ and |φ⟩ an arbitrary number of times. Then,

performing repeated measurements of the two states in diﬀerent measurement bases, we would (given

enough measurements) be able to distinguish the two states based on the measurement statistics (there

will of course be some error ϵ based on probabilistic considerations, but given that we have access to as

many measurements of the states as we like, we are able to make this error arbitrarily low).

Problem 1.1: (Feynman-Gates conversation)

Construct a friendly imaginary discussion of about 2000 words between Bill Gates and Richard Feynman,

set in the present, on the future of computation (Comment: You might like to try waiting until you’ve

heard the rest of the book before attempting this question. See ‘History and further reading’ below for

pointers to one possible answer for this question).

Problem 1.2

What is the most signiﬁcant discovery yet made in quantum computation and quantum information? Write

an essay of about 2000 words to an educated lay audience about the discovery (Comment: As for the

previous problem, you might like to try waiting until you’ve read the rest of the book before attempting

this question.)

2 Introduction to quantum mechanics

Exercise 2.1: Linear dependence: example

Show that (1, −1), (1, 2) and (2, 1) are linearly dependent.

Solution

Concepts Involved: Linear Algebra, Linear Independence/Dependence.

We observe that:

−1

−

1 + 1 − 2

−1 + 2 − 1

showing that the three vectors are linearly dependent by deﬁnition. Alternatively, we can apply theorem

that states that for any vector space V with dim V = n, any list of m > n vectors in V will be linearly

dependent (here, V = R

, n = 2, m = 3).

Exercise 2.2: Matrix representations: example

Suppose V is a vector space with basis vectors |0⟩ and |1⟩, and A is a linear operator from V to V such

that A |0⟩ = |1⟩ and A |1⟩ = |0⟩. Give a matrix representation for A, with respect to the input basis

|0⟩, |1⟩, and the output basis |0⟩, |1⟩. Find input and output bases which give rise to a diﬀerent matrix

representation of A.

Solution

Concepts Involved: Linear Algebra, Matrix Representation of Operators.

Identifying |0⟩

∼

and |1⟩

∼

, we have that:

A =

Using the given relations, we have that:

A |0⟩ = 0 |0⟩ + 1 |1⟩ =⇒

= 0

+ 1

=⇒ a

= 0, a

= 1

A |1⟩ = 1 |0⟩ + 0 |1⟩ =⇒

= 1

+ 0

=⇒ a

= 1, a

= 0

Therefore with respect to the input basis



|0⟩, |1⟩



and output basis



|0⟩, |1⟩



, A has matrix represen-

tation:

∼

⟨0| ⟨1|

|0⟩ 0 1

|1⟩ 1 0

Suppose we instead choose the input and output basis to be

|+⟩ =

|0⟩+|1⟩

√

, |−⟩ =

|0⟩−|1⟩

√

. Identifying

|+⟩

∼

and |−⟩

∼

, we have:

A =

+−

−+

−−

Using the linearity of A, we have that:

A |+⟩ =

√

A(|0⟩ + |1⟩) =

√

(A |0⟩ + A |1⟩) =

√

(|1⟩ + |0⟩) = |+⟩

and:

A |−⟩ =

√

A( |0⟩ − |1⟩) =

√

(A |0⟩ − A |1⟩) =

√

( |1⟩ − |0⟩) = −|−⟩,

which can be used to determine the matrix elements:

A |+⟩ = 1 |+⟩ + 0 |−⟩ =⇒

+−

−+

−−

= 1

+ 0

=⇒ a

= 1, a

+−

= 0

A |−⟩ = 0 |+⟩ − 1 |−⟩ =⇒

+−

−+

−−

= 0

− 1

=⇒ a

−+

= 0, a

−−

= −1

Therefore with respect to the input basis



|+⟩, |−⟩



and output basis



|+⟩, |−⟩



, A has matrix repre-

sentation:

∼

⟨+| ⟨−|

|+⟩ 1 0

|−⟩ 0 −1

Remark: If we choose the input and output bases to be diﬀerent, we can even represent the A operator

as an identity matrix. Speciﬁcally, if the input basis to be chosen to be



|0⟩, |1⟩



and output basis as



|1⟩, |0⟩



, the matrix representation of A looks like:

∼

1 0

0 1

Exercise 2.3: Matrix representation for operator products

Suppose A is a linear operator from vector space V to vector space W , and B is a linear operator from

vector space W to vector space X. Let |v

⟩, |w

⟩, |x

⟩ be bases for the vector spaces V, W and X

respectively. Show that the matrix representation for the linear transformation BA is the matrix product

of the matrix representations for B and A, with respect to the appropriate bases.

Solution

Concepts Involved: Linear Algebra, Matrix Representation of Operators.

Taking the matrix of representations of A and B to the appropriate bases |v

⟩,





, |x

⟩ of V, W and

X, we have that:

A |v

⟩ =

⟩, B |w

⟩ =

⟩

Hence, looking at BA

V 7→ X, we have that:

BA |v

⟩ = B(A |v

⟩)

= B





⟩





B |w

⟩





⟩





⟩

(BA)

⟩

which shows that the matrix representation of BA is indeed the matrix product of the representations of

B and A.

Exercise 2.4: Matrix representation for identity

Show that the identity operator on a vector space V has a matrix representation which is one along the

diagonal and zero everywhere else, if the matrix is taken with respect to the same input and output bases.

This matrix is known as the identity matrix.

Solution

Concepts Involved: Linear Algebra, Matrix Representation of Operators.

Let V be a vector space and |v

⟩ be a basis of V . Let A

V 7→ V be a linear operator, and let its matrix

representation taken to be respect to |v

⟩ as the input and output basis. We then have that for each

i ∈ {1, . . . , n}:

A|v

⟩ = 1|v

⟩ +

j̸=i

0|v

⟩ =

⟩

From which we obtain that A has the matrix representation:

∼







1 0 0 ··· 0

0 1 0 0

0 0 1 0

0 0 0 . . . 1







Exercise 2.5

Verify that (·, ·) just deﬁned is an inner product on C

Solution

Concepts Involved: Linear Algebra, Inner Products.

Recall that on C

, (·, ·) was deﬁned as:

((y

, . . . , y

), (z

, . . . , z

)) ≡

∗

= [y

∗

. . . y

∗

]













Furthermore, recall the three conditions for the function (·, ·)

V × V 7→ C to be considered an inner

product:

(1) (·, ·) is linear in the second argument.

(2) (|v⟩, |w⟩) = (|w⟩, |v⟩)

∗

(3) (|v⟩, |v⟩) ≥ 0 with equality if and only if |v⟩ = 0.

We check that (·, ·)

× C

7→ C satisﬁes the three conditions:

(1) We see that:

((y

, . . . , y

, . . . , z

)

) =

∗

((y

, . . . , y

), (z

, . . . , z

)

(2) We have:

((y

, . . . , y

), (z

, . . . , z

)) =

∗

)

∗





∗





∗



((z

, . . . , z

), (y

, . . . , y

))



∗

(3) We observe for 0 = (0, . . . 0):

(0, 0) =

0 · 0 = 0

For y = (y

, . . . , y

) ̸= 0 we have that at least one y

(say, y

) is nonzero, and hence:

((y

, . . . , y

), (y

, . . . , y

)) =

≥ y

> 0

which proves the claim.

Exercise 2.6

Show that any inner product (·, ·) is conjugate-linear in the ﬁrst argument,





⟩, |v⟩





∗

( |w

⟩, |v⟩).

Solution

Concepts Involved: Linear Algebra, Inner Products

Applying properties (2) (conjugate symmetry), (1) (linearity in second argument), and (2) (again) in

succession, we have that:





⟩, |v⟩









|v⟩,

⟩





∗





(|v

⟩, |w

⟩)





∗

(|v

⟩, |w

⟩)

∗

(|w

⟩, |v

⟩)

Exercise 2.7

Verify that |w⟩ = (1, 1) and |v⟩ = (1, −1) are orthogonal. What are the normalized forms of these

vectors?

Solution

Concepts Involved: Linear Algebra, Inner Products, Orthogonality, Normalization

Recall that two vectors |v⟩, |w⟩ are orthogonal if ⟨v|w⟩ = 0, and the norm of |v⟩ is given by



|v⟩



⟨v|v⟩.

First we show the two vectors are orthogonal:

⟨w|v⟩ = 1 · 1 + 1 · (−1) = 0

The norms of |w⟩, |v⟩ are given by:



|w⟩



⟨w|w⟩ =

+ 1

√



|c⟩



⟨v|v⟩ =

+ (−1)

√

So the normalized forms of the vectors are:

|w⟩



|w⟩



√

|v⟩



|v⟩



√

−1

√

Exercise 2.8

Verify that the Gram-Schmidt procedure produces and orthonormal basis for V .

Solution

Concepts Involved: Linear Algebra, Linear Independence, Bases, Inner Products, Orthogonality, Normal-

ization, Gram-Schmidt Procedure, Induction.

Recall that given |w

⟩, . . . , |w

⟩ as a basis set for a vector space V , the Gram-Schmidt procedure con-

structs a basis set |v

⟩, . . . , |v

⟩ by deﬁning |v

⟩ ≡ |w

⟩/



⟩



and then deﬁning |v

k+1

⟩ inductively for

1 ≤ k ≤ d − 1 as:

k+1

⟩ ≡

k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



It is evident that each of the |v

⟩ have unit norm as they are deﬁned in normalized form. It therefore

suﬃces to show that each of the |v

⟩, . . . , |v

⟩ are orthogonal to each other, and that this set of vectors

forms a basis of V . We proceed by induction. For k = 1, we have that:

⟩ =

⟩ − ⟨v

⟩|v

⟩



⟩ + ⟨v

⟩|v

⟩



Therefore:

⟨v

⟩ =

⟨v

⟩ − ⟨v

⟩ ⟨v

⟩



⟩ + ⟨v

⟩|v

⟩



⟨v

⟩ − ⟨v

⟩



⟩ + ⟨v

⟩|v

⟩



= 0

so the two vectors are orthogonal. Furthermore, they are linearly independent; if they were linearly

dependent, we could write |v

⟩ = λ|v

⟩ for some λ ∈ C, but then multiplying both sides by ⟨v

| we get:

⟨v

⟩ = λ ⟨v

⟩ =⇒ 1 = 0

which is a contradiction. This concludes the base case. For the inductive step, let k ≥ 1 and suppose that

⟩, . . . , |v

⟩ are orthogonal and linearly independent. We then have that:

k+1

⟩ =

k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



Then for any j ∈ {1, . . . k}, we have that:

⟨v

k+1

⟩ =

⟨v

k+1

⟩ −

i=1

⟨v

k+1

⟩ ⟨v

⟩|v

⟩



k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



⟨v

k+1

⟩ − ⟨v

k+1

⟩



k+1

⟩ −

i=1

⟨v

k+1

⟩|v

⟩



= 0

where in the second equality we use the fact that







= δ

for i, j ∈ {1, . . . k} by the inductive hypoth-

esis. We therefore ﬁnd that |v

k+1

⟩ is orthogonal to all of |v

⟩, . . . , |v

⟩. Furthermore, |v

⟩, . . . , |v

⟩, |v

k+1

⟩

is lienarly independent. Suppose for the sake of contradiction that this was false. Then, there would exist

, . . . λ

not all nonzero such that:

⟩ + . . . + λ

⟩ = |v

k+1

⟩

but then multiplying both sides by ⟨v

k+1

| we have that:

⟨v

k+1

⟩ + . . . + λ

⟨v

k+1

⟩ = ⟨v

k+1

⟩ =⇒ 0 = 1

by orthonormality. This gives a contradiction, and hence |v

⟩, . . . , |v

⟩, |v

k+1

⟩ are linearly independent,

ﬁnishing the inductive step. Therefore, |v

⟩, . . . , |v

⟩ is an orthonormal list of vectors which is linearly

independent. Since |w

⟩, . . . , |w

⟩ is a basis for V , then V has dimension d. Hence, |v

⟩, . . . , |v

⟩ being

a linearly independent list of d vectors in V is a basis of V . We conclude that it is an orthonormal basis

of V , as claimed.

Exercise 2.9: Pauli operators and the outer product

The Pauli matrices (Figure 2.2 on page 65) can be considered as operators with respect to an orthonormal

basis |0⟩, |1⟩ for a two-dimensional Hilbert space. Express each of the Pauli operators in the outer product

notation.

Solution

Concepts Involved: Linear Algebra, Matrix Representation of Operators, Outer Products.

Recall that if A has matrix representation:

∼

with respect to |0⟩, |1⟩ as the input/output bases, then we can express A in outer product notation as:

A = a

|0⟩⟨0| + a

|0⟩⟨1| + a

|1⟩⟨0| + a

|1⟩⟨1|

Furthermore, recall the representation of the Pauli matrices with respect to the orthonormal basis |0⟩, |1⟩:

I =

1 0

0 1

X =

0 1

1 0

Y =

0 −i

i 0

Z =

1 0

0 −1

We immediately see that:

I = |0⟩⟨0| + |1⟩⟨1|

X = |0⟩⟨1| + |1⟩⟨0|

Y = −i |0⟩⟨1| + i |1⟩⟨0|

Z = |0⟩⟨0| − |1⟩⟨1|

Exercise 2.10

Suppose |v

⟩ is an orthonormal basis for an inner product space V . What is the matrix representation for

the operator |v

⟩⟨v

|, with respect to the |v

⟩ basis?

Solution

Concepts Involved: Linear Algebra, Matrix Representation of Operators, Outer Products.

The matrix representation of |v

⟩⟨v

| with respect to the |v

⟩ basis is a matrix with 1 in the jth column

and row (i.e. the (j, j)th entry in the matrix) and 0 everywhere else.

Exercise 2.11

Find the eigenvectors, eigenvalues, and diagonal representations of the Pauli matrices X, Y and Z.

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors, Diagonalization.

Given an operator A on a vector space V , recall that an eigenvector |v⟩ of A and its corresponding

eigenvalue λ are deﬁned by:

A|v⟩ = λ|v⟩

Furthermore, recall the diagonal representation of A is given by

A =

|i⟩⟨i|

Where |i⟩ form an orthonormal set of eigenvectors for A, and λ

are the corresponding eigenvalues.

We start with X. Solving for the eigenvalues, we have:

det(X − Iλ) = 0 =⇒ det

−λ 1

1 −λ

= 0 =⇒ λ

− 1 = 0

From which we obtain λ

= 1, λ

= −1. Solving for the eigenvectors, we then have that:

(X − Iλ

)|v

⟩ = 0 =⇒

−1 1

1 −1

=⇒ v

= 1, v

= 1

(X − Iλ

)|v

⟩ = 0 =⇒

1 1

=⇒ v

= 1, v

= −1

Hence we ﬁnd that |v

⟩ = |0⟩ + |1⟩, |v

⟩ = |0⟩ − |1⟩. Normalizing these eigenvectors (Also see Exercise

2.7), we divide by



⟩



⟩



√

2, giving us:

⟩ = |+⟩ =

|0⟩ + |1⟩

√

, |v

⟩ = |−⟩ =

|0⟩ − |1⟩

√

The diagonal representation of X is then given by:

X = λ

⟩⟨v

| + λ

⟩⟨v

| = |+⟩⟨+| − |−⟩⟨−|

We do the same for Y . Solving for the eigenvalues:

det(A − Iλ) = 0 =⇒ det

−λ −i

i −λ

= 0 =⇒ λ

− 1 = 0

From which we obtain λ

= 1, λ

= −1. Solving for the eigenvectors, we then have that:

(Y − Iλ

)|v

⟩ = 0 =⇒

−1 −i

i −1

=⇒ v

= 1, v

= i

(Y − Iλ

)|v

⟩ = 0 =⇒

1 −i

i 1

=⇒ v

= 1, v

= −i

We therefore have that |v

⟩ = |0⟩ + i|1⟩, |v

⟩ = |0⟩ − i|1⟩. Normalizing by dividing by



⟩



⟩



we obtain that:

⟩ = |y

⟩ =

|0⟩ + i|1⟩

√

, |v

⟩ = |y

−

⟩ =

|0⟩ − i|1⟩

√

The diagonal representation of Y is then given by:

Y = |y

⟩⟨y

| − |y

−

⟩⟨y

−

For Z, the process is again the same. We give the results and omit the details:

= 1, |v

⟩ = |0⟩ λ

= −1, |v

⟩ = |1⟩

Z = |0⟩⟨0| − |1⟩⟨1|

Exercise 2.12

Prove that the matrix

1 0

1 1

is not diagonalizable.

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors, Diagonalization.

Solving for the eigenvalues of the matrix, we have:

det

1 − λ 0

1 1 − λ

= 0 =⇒ (1 − λ)

= 0 =⇒ λ

, λ

= 1

But since the eigenvalue 1 is degenerate, the matrix only has one eigenvector; it therefore cannot be

diagonalized.

Exercise 2.13

If |w⟩ and |v⟩ are any two vectors, show that (|w⟩⟨v|)

†

= |v⟩⟨w|.

Solution

Concepts Involved: Linear Algebra, Adjoints.

We observe that:

(( |w⟩⟨v|)

†

|x⟩, |y⟩) = (|x⟩, ( |w⟩⟨v|)|y⟩) = (|x⟩, ⟨v|y⟩|w⟩) = ⟨x|⟨v|y⟩|w⟩

= ⟨x|w⟩⟨v|y⟩

= ⟨x|w⟩(|v⟩, |y⟩)

= (⟨x|w⟩

∗

|v⟩, |y⟩)

= (⟨w|x⟩|v⟩, |y⟩)

= (( |v⟩⟨w|)|x⟩, |y⟩)

Where in the third-to last equality we use the conjugate linearity in the ﬁrst argument (see Exercise 2.6)

and in the second-to last equality we use that ⟨a|b⟩

∗

= ⟨b|a⟩. Comparing the ﬁrst and last expressions,

we conclude that ( |w⟩⟨v|)

†

= |v⟩⟨w|.

Exercise 2.14: Anti-linearity of the adjoint

Show that the adjoint operator is anti-linear,









†

∗

†

Solution

Concepts Involved: Linear Algebra, Adjoints.

We observe that:















†

|a⟩, |b⟩











|a⟩,

|b⟩







|a⟩, A

|b⟩





†

|a⟩, |b⟩







∗

†

|a⟩, |b⟩





where we invoke the deﬁnition of the adjoint in the ﬁrst and third equalities, the linearity in the second

argument in the second equality, and the conjugate linearity in the ﬁrst argument in the last equality. The

claim is proven by comparing the ﬁrst and last expressions.

Exercise 2.15

Show that (A

†

)

†

= A.

Solution

Concepts Involved: Linear Algebra, Adjoints

Applying the deﬁnition of the Adjoint twice (and using the conjugate symmetry of the inner product) we

have that:

((A

†

)

†

|a⟩, |b⟩) = (|a⟩, A

†

|b⟩) = (A

†

|b⟩, |a⟩)

∗

= (|b⟩, A|a⟩)

∗



(A|a⟩, |b⟩)

∗



∗

= (A|a⟩, |b⟩).

The claim follows by comparison of the ﬁrst and last expressions.

Exercise 2.16

Show that any projector P satisﬁes the equation P

= P .

Solution

Concepts Involved: Linear Algebra, Projectors.

Let |1⟩, . . . , |k⟩ be an orthonormal basis for the subspace W of V . Then, using the deﬁnition of the

projector onto W , we have that:

= P · P =





i=1

|i⟩⟨i|









′



′



′







i=1

′

|i⟩⟨i|i

′

⟩⟨i

′

| =

i=1

′

|i⟩δ

′

⟨i

′

| =

i=1

|i⟩⟨i| = P

where in the fourth/ﬁfth equality we use the orthonormality of the basis to collapse the double sum.

Exercise 2.17

Show that a normal matrix is Hermitian if and only if it has real eigenvalues.

Solution

Concepts Involved: Linear Algebra, Hermitian Operators, Normal Operators, Spectral Decomposition.

=⇒ Let A be a Normal and Hermitian matrix. Then, it has a diagonal representation A =

|i⟩⟨i|

where |i⟩ is an orthonormal basis for V and each |i⟩ is an eigenvector of A with eigenvalue λ

. By the

Hermicity of A, we have that A = A

†

. Therefore, we have that:

†





|i⟩⟨i|





†

∗

|i⟩⟨i| = A =

|i⟩⟨i|

where we use the results of Exercises 2.13 and 2.14 in the second equality. Comparing the third and last

expressions, we have that λ

= λ

∗ and hence the eigenvalues are real.

⇐= Let A be a Normal matrix with real eigenvalues. Then, A has diagonal representation A =

|i⟩⟨i| where λ

are all real. We therefore have that:

†





|i⟩⟨i|





†

= λ

∗

|i⟩⟨i| =

|i⟩⟨i| = A

where in the third equality we use that λ

∗

= λ

. We conclude that A is Hermitian.

Exercise 2.18

Show that all eigenvalues of a unitary matrix have modulus 1, that is, can be written in the form e

iθ

for

some real θ.

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Spectral Decomposition

Let U be a unitary matrix. It is then normal as U

†

U = U

†

U = I. It therefore has spectral decomposition

U =

|i⟩⟨i| where |i⟩ is an orthonormal basis of V , and |i⟩ are the eigenvectors of U with eigenvalues

. We then have that:

†

= I =⇒





|i⟩⟨i|









′

⟩⟨i

′





†

= I

=⇒





|i⟩⟨i|









′

∗

′

⟩⟨i

′





= I

=⇒

′

|i⟩⟨i|i

′

⟩⟨i

′

| = I

=⇒

′

∗

′

|i⟩δ

′

⟨i

′

| = I

=⇒

′

|i⟩⟨i| = I

=⇒

|λ

|i⟩⟨i| =

1 |i⟩⟨i|

From which we obtain that |λ

= 1, and hence |λ

| = 1, proving the claim.

Exercise 2.19: Pauli matrices: Hermitian and unitary

Show that the Pauli matrices are Hermitian and unitary.

Solution

Concepts Involved: Linear Algebra, Hermitian Matrices, Unitary Matrices

We check I, X, Y, Z in turn.

†





1 0

0 1





∗

1 0

0 1

∗

1 0

0 1

= I

†

I = II = I

†





0 1

1 0





∗

0 1

1 0

∗

0 1

1 0

= X

†

X = XX =

0 1

1 0

0 1

1 0

0 1

= I

†





0 −i

i 0





∗

0 i

−i 0

∗

0 −i

i 0

= Y

†

Y = Y Y =

0 −i

i 0

0 −i

i 0

1 0

0 1

†





1 0

0 −1





∗

1 0

0 −1

∗

1 0

0 −1

= Z

†

Z =

1 0

0 −1

1 0

0 −1

1 0

0 1

= I

Exercise 2.20: Basis changes

Suppose A

′

and A

′′

are matrix representations of an operator A on a vector space A on a vector space

V with respect to two diﬀerent orthonormal bases, |v

⟩ and |w

⟩. Then the elements of A

′

and A

′′

are

′

= ⟨v

|A|v

⟩ and A

′′

= ⟨w

|A|w

⟩. Characterize the relationship between A

′

and A

′′

Solution

Concepts Involved: Linear Algebra, Matrix Representations of Operators, Completeness Relation

Using the completeness relation twice, we get:

′

= ⟨v

|A|v

⟩ = ⟨v

|IAI|v

⟩ = ⟨v





′

⟩⟨w

′









′

⟩⟨w

′





⟩

′

⟨v

′

⟩⟨w

′

|A|w

′

⟩⟨w

′

⟩

′

⟨v

′

⟩A

′′

⟨w

′

⟩

Exercise 2.21

Repeat the proof of the spectral decomposition in Box 2.2 for the case when M is Hermitian, simplifying

the proof wherever possible.

Solution

Concepts Involved: Linear Algebra, Hermitian Operators, Spectral Decomposition.

For the converse, we have that if M is diagonalizable, then it has a representation M =

|i⟩⟨i| where

|i⟩ is an orthonormal basis of V , and |i⟩ are eigenvectors of M with associated eigenvalues of λ

. We then

have that:

†





|i⟩⟨i|





†

∗

|i⟩⟨i| =

|i⟩⟨i| = M

where in the second equality we apply the result of Exercise 2.13 and in the third equality we use that

Hermitian matrices have real eigenvalues. For the forwards implication, we proceed by induction on the

dimension d of V . The d = 1 case is trivial as M is already diagonal in any representation in this

case. Let λ be an eigenvalue of M, P the projector onto the λ subspace, and Q the projector onto the

orthogonal complement. Then M = (P + Q)M(P + Q) = P MP + QM P + P MQ + QMQ. Obviously

P M P = λP. Furthermore, QMP = 0, as M takes the subspace P into itself. We claim that P M Q = 0

also. To see this, we recognize that (P MQ)

†

= Q

†

= QMP = 0. and hence P MQ = 0. Thus

M = P MP + QMQ. QM Q is normal, as (QMQ)

†

= Q

†

= QMQ (and Hermiticity implies that

the operator is normal). By induction, QMQ is diagonal with respect to some orthonormal basis for the

subspace Q, and P MP is already diagonal with respect to some orthonormal basis for P . It follows that

M = P M P + QMQ is diagonal with respect to some orthonormal basis for the total vector space.

Exercise 2.22

Prove that two eigenvectors of a Hermitian operator with diﬀerent eigenvalues are necessarily orthogonal.

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors, Hermitian Operators.

Let A be a Hermitian operator, and let |v

⟩, |v

⟩ be two eigenvectors of A with corresponding eigenvalues

, λ

such that λ

̸= λ

. We then have that:

⟨v

|A|v

⟩ = ⟨v

|λ

⟩ = λ

⟨v

⟩

⟨v

|A|v

⟩ = ⟨v

†

⟩ = ⟨v

|λ

⟩ = λ

⟨v

⟩

where we use the Hermiticity of A in the second line. Substracting the ﬁrst line from the second, we have

that:

0 = (λ

− λ

)⟨v

⟩.

Since λ

̸= λ

by assumption, the only way this equality is satisﬁed is if ⟨v

⟩ = 0. Hence, |v

⟩, |v

⟩ are

orthogonal.

Exercise 2.23

Show that the eigenvalues of a projector P are all either 0 or 1.

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors, Projectors.

Let P be a projector, and |v⟩ be an eigenvector of P with corresponding eigenvalue λ. From Exercise

2.16, we have that P

= P , and using this fact, we observe:

P |v⟩ = λ|v⟩

P |v⟩ = P

|v⟩ = P P |v⟩ = P λ|v⟩ = λP |v⟩ = λ

|v⟩.

Subtracting the ﬁrst line from the second, we get:

0 = (λ

− λ)|v⟩ = λ(λ − 1)|v⟩.

Since |v⟩ is not the zero vector, we therefore obtain that either λ = 0 or λ = 1.

Exercise 2.24: Hermiticity of positive operator

Show that a positive operator is necessarily Hermitian. (Hint: Show that an arbitrary operator A can be

written A = B + iC where B and C are Hermitian.)

Solution

Concepts Involved: Linear Algebra, Hermitian Operators, Positive Operators

Let A be an operator. We ﬁrst make the observation that we can write A as:

A =

†

−

†

A + A

†

+ i

A − A

†

So let B =

A+A

†

and C =

A−A

†

. B and C are Hermitian, as:

†

A + A

†

+ (A

†

)

†

+ A

= B

†

A − A

†

− (A

†

)

†

−2i

A − A

†

= C

so we have hence proven that we can write A = B + iC for hermitian B, C for any operator A. Now,

assume that A is positive. We then have that for any vector |v⟩:

⟨v|A|v⟩ ≥ 0.

Using the identity derived above, we have that:

⟨v|B|v⟩ + i⟨v|C|v⟩ ≥ 0.

The positivity forces C = 0. Therefore, A = B and hence A is Hermitian.

Exercise 2.25

Show that for any operator A, A

†

A is positive.

Solution

Concepts Involved: Linear Algebra, Adjoints, Positive Operators

Let A be an operator. Let |v⟩ be an arbitrary vector, and then we then have that:



|v⟩, A

†

A|v⟩





†

)

†

|v⟩, A|v⟩





A|v⟩, A|v⟩



By the property of inner products, the expression must be greater than zero.

Exercise 2.26

Let |ψ⟩ = ( |0⟩ + |1⟩)/

√

2. Write out |ψ⟩

⊗2

and |ψ⟩

⊗3

explicitly, both in terms of tensor products like

|0⟩|1⟩ and using the Kronecker product.

Solution

Concepts Involved: Linear Algebra, Tensor Products, Kronecker Products.

Using the deﬁnition of the tensor product, we have:

|ψ⟩

⊗2

|0⟩|0⟩ + |0⟩|1⟩ + |1⟩|0⟩ + |1⟩|1⟩

∼







√



















|ψ⟩

⊗3

|0⟩|0⟩|0⟩ + |0⟩|0⟩|1⟩ + |0⟩|1⟩|0⟩ + |0⟩|1⟩|1⟩ + |1⟩|0⟩|0⟩ + |1⟩|0⟩|1⟩ + |1⟩|1⟩|0⟩ + |1⟩|1⟩|1⟩

√

= |ψ⟩ ⊗ |ψ⟩

⊗2

∼







√













√

























√







Exercise 2.27

Calculate the matrix representation of the tensor products of the Pauli operators (a) X and Z; (b) I and

X; (c)X and I. Is the tensor product commutative?

Solution

Concepts Involved: Linear Algebra, Tensor Products, Kronecker Products.

Using the Kronecker product, we have:

(a)

X ⊗ Z =

0Z 1Z

1Z 0Z







1 0

0 −1

1 0

0 −1

1 0

0 −1

1 0

0 −1













0 0 1 0

0 0 0 −1

1 0 0 0

0 −1 0 0







(b)

I ⊗ X =

1X 0X

0X 1X







0 1

1 0

0 1

1 0

0 1

1 0

0 1

1 0













0 1 0 0

1 0 0 0

0 0 0 1

0 0 1 0







(c)

X ⊗ I =

0I 1I

1I 0I







1 0

0 1

1 0

0 1

1 0

0 1

1 0

0 1













0 0 1 0

0 0 0 1

1 0 0 0

0 1 0 0







Comparing (b) and (c), we conclude that the tensor product is not commutative.

Exercise 2.28

Show that the transpose, complex conjugation and adjoint operations distribute over the tensor product,

(A ⊗ B)

∗

= A

∗

⊗ B

∗

; (A ⊗ B)

= A

⊗ B

; (A ⊗ B)

†

= A

†

⊗ B

†

Solution

Concepts Involved: Linear Algebra, Adjoints, Tensor Products, Kronecker Products.

Using the Kronecker product representaton of a ⊗ B, we have:

(A ⊗ B)

∗







B A

B . . . A

B A

B . . . A

B A

B . . . A







∗







∗

. . . A

∗

. . . A

∗

. . . A

∗







= A

∗

⊗ B

∗

(A ⊗ B)







B A

B . . . A

B A

B . . . A

B A

B . . . A













. . . A

B . . . A

. . . A







= A

⊗ B

The relation for the distributivity of the hermitian conjugate over the tensor product then follows from the

former two relations:

(A ⊗ B)

†

= ((A ⊗ B)

)

∗

= (A

⊗ B

)

∗

= (A

)

∗

⊗ (B

)

∗

= A

†

⊗ B

†

Exercise 2.29

Show that the tensor product of two unitary operators is unitary.

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Tensor Products

Suppose A, B are unitary. Then, A

†

A = I and B

†

B = I. Using the result of the Exercise 2.28, we then

have that:

(A ⊗ B)

†

(A ⊗ B) = (A

†

⊗ B

†

)(A ⊗ B) = (A

†

A ⊗ B

†

B) = I ⊗ I

Exercise 2.30

Show that the tensor product of two Hermitian operators is Hermitian.

Solution

Concepts Involved: Linear Algebra, Hermitian Operators, Tensor Products

Suppose A, B are Hermitian. Then, A

†

= A and B

†

= B. Then, using the result of Exercise 2.28, we

have:

(A ⊗ B)

†

= A

†

⊗ B

†

= A ⊗ B

Exercise 2.31

Show that the tensor product of two positive operators is positive.

Solution

Concepts Involved: Linear Algebra, Positive Operators

Suppose A, B are positive operators. We then have that ⟨v|A|v⟩ ≥ 0 and ⟨w|B|w⟩ ≥ 0. Therefore, for

any |v⟩ ⊗ |w⟩:



|v⟩ ⊗ |w⟩, A ⊗ B(|v⟩ ⊗ |w⟩)



= ⟨v|A|v⟩⟨w|B|w⟩ ≥ 0

Exercise 2.32

Show that the tensor product of two projectors is a projector.

Solution

Concepts Involved: Linear Algebra, Projectors

Let P

, P

be projectors. We then have that P

= P

and P

= P

by Exercise 2.16. Therefore:

⊗ P

)

= (P

⊗ P

)(P

⊗ P

) = P

⊗ P

= P

⊗ P

so P

⊗ P

is a projector.

Exercise 2.33

The Hadamard operator on one qubit may be written as

H =

√

[(|0⟩ + |1⟩)⟨0| + (|0⟩ − |1⟩)⟨1|]

Show explicitly that the Hadamard transform on n qubits, H

⊗n

, may be written as

⊗n

√

x,y

(−1)

x·y

|x⟩⟨y|

Write out an explicit matrix representation for H

⊗2

Solution

Concepts Involved: Linear algebra, Matrix Representation of Operators, Outer Products.

Looking at the form of the Hadamard operator on one qubit, we observe that:

H =

√



|0⟩⟨0| + |0⟩⟨1| + |1⟩⟨0| − |1⟩⟨1|



Hence:

H =

√

x,y

(−1)

x·y

|x⟩⟨y|

Where x, y run over 0 and 1. Taking the n-fold tensor product of this expression, we get:

⊗

√

x,y

(−1)

x·y

|x⟩⟨y| ⊗

√

x,y

(−1)

x·y

|x⟩⟨y| ⊗ . . . ⊗

√

x,y

(−1)

x·y

|x⟩⟨y|

√

x,y

(−1)

x·y

|x⟩⟨y|

Where x, y are length n-binary strings. This proves the claim.

Now explicitly writing H

⊗2

, we have:

⊗2

√

x,y

(−1)

(x·y)

|x⟩⟨y|

∼







1 1 1 1

1 −1 1 −1

1 1 −1 −1

1 −1 −1 1







Note that here, x, y are binary length 2 strings. The sum goes through all pairwise combinations of

x, y ∈ {00, 01, 10, 11}.

Remark: Sylvester’s Construction gives an interesting recursive construction of Hadamard matrices.

See https://en.wikipedia.org/wiki/Hadamard_matrix. Discussion on interesting (related) open

problem concerning the maximal determinant of matrices consisting of entries of 1 and −1 can be found

here https://en.wikipedia.org/wiki/Hadamard%27s_maximal_determinant_problem.

Exercise 2.34

Find the square root and logarithm of the matrix

4 3

3 4

Solution

Concepts Involved: Linear Algebra, Spectral Decomposition, Operator Functions

We begin by diagonalizing the matrix (which we call A) as to be able to apply the deﬁnition of oper-

ator functions. By inspection, A is Hermitian as it is equal to its conjugate transpose, so the spectral

decomposition exists. Solving for the eigenvalues, we consider the characterstic equation:

det(A − λI) = 0 =⇒ det

4 − λ 3

3 4 − λ

= 0 =⇒ (4 − λ)

− 9 = 0 =⇒ λ

− 8λ + 7 = 0

Using the quadratic equation, we get λ

= 1, λ

= 7. Using this to ﬁnd the eigenvectors of the matrix,

we have:

4 − 1 3

3 4 − 1

= 0 =⇒ v

= 1, v

= −1

4 − 7 3

3 4 − 7

= 0 =⇒ v

= 1, v

= 1

Hence our normalized eigenvectors are:

⟩ =

√

−1

√

, |v

⟩ =

√

Therefore the spectral composition of the matrix is given by:

A = 1 |v

⟩⟨v

| + 7 |v

⟩⟨v

Calculating the square root of A, we then have:

√

A =

√

1 |v

⟩⟨v

| +

√

7 |v

⟩⟨v

| =

1 −1

−1 1

√

1 1

1 +

√

7 −1 +

√

−1 +

√

7 1 +

√

Calculating the logarithm of A, we have:

log(A) = log(1) |v

⟩⟨v

| + log(7) |v

⟩⟨v

| =

log(7)

1 1

Exercise 2.35: Exponential of Pauli matrices

Let v be any real, three-dimensional unit vector and θ a real number. Prove that

exp(iθv · σ) = cos(θ)I + i sin(θ)v · σ

Where v · σ ≡

i=1

. This exercise is generalized in Problem 2.1 on page 117.

Solution

Concepts Involved: Linear Algebra, Spectral Decomposition, Operator Functions.

Recall that σ

≡ X, σ

≡ Y , and σ

≡ Z.

First, we compute v · σ in matrix form:

v · σ = v

+ v

= v

0 1

1 0

+ v

0 −i

i 0

+ v

1 0

0 −1

− iv

+ iv

−v

In order to compute the complex exponential of this matrix, we will want to ﬁnd its spectral decomposition.

Using the characterstic equation to ﬁnd the eigenvalues, we have:

det(v · σ − Iλ) = 0 =⇒ det

− λ v

− iv

+ iv

−v

− λ

= 0

=⇒ (v

− λ)(−v

− λ) − (v

− iv

)(v

+ iv

) = 0

=⇒ λ

− v

= λ

− (v

+ v

) = 0

=⇒ λ

− 1 = 0

=⇒ λ

= 1, λ

= −1

where in the second-to-last implication we use the fact that v is a unit vector. Letting |v

⟩, |v

⟩ be the

associated eigenvectors, v · σ has spectral decomposition:

v · σ = |v

⟩⟨v

| − |v

⟩⟨v

Applying the complex exponentiation operator, we then have that:

exp(iθv · σ) = exp(iθ) |v

⟩⟨v

| + exp(−iθ) |v

⟩⟨v

Using Euler’s formula, we then have that:

exp(iθv · σ) = (cos θ + i sin θ) |v

⟩⟨v

| + (cos θ − i sin θ) |v

⟩⟨v

= cos(θ)



⟩⟨v

| + |v

⟩⟨v



+ i sin(θ)



⟩⟨v

| − |v

⟩⟨v



= cos(θ)I + i sin(θ)v · σ.

Where in the last line we use the completeness relation and the spectral decomposition.

Exercise 2.36

Show that the Pauli matrices except for I have trace zero.

Solution

Concepts Involved: Linear Algebra, Trace.

We have that:

tr(X) = tr

0 1

1 0

= 0 + 0 = 0

tr(Y ) = tr

0 −i

i 0

= 0 + 0 = 0

tr(Z) = tr

1 0

0 −1

= 1 − 1 = 0

Exercise 2.37: Cyclic property of the trace

If A and B are two linear operators show that

tr(AB) = tr(BA)

Solution

Concepts Involved: Linear Algebra, Trace.

Let A, B be linear operators. Then, C = AB has matrix representation with entries C

and D = BA has matrix representation with entries D

. We then have that:

tr(AB) = tr(C) =

= tr(D) = tr(BA)

Exercise 2.38: Linearity of the trace

If A and B are two linear operators, show that

tr(A + B) = tr(A) + tr(B)

and if z is an arbitrary complex number show that

tr(zA) = z tr(A).

Solution

Concepts Involved: Linear Algebra, Trace.

From the deﬁnition of trace, we have that:

tr(A + B) =

(A + B)

+ B

= tr(A) + tr(B)

tr(zA) =

(zA)

= z

= z tr(A)

Exercise 2.39: The Hilbert-Schmidt inner product on operators

The set L

of linear operators on Hilbert space V is obviously a vector space - the sum of two linear

operators is a linear operator, zA is a linear operator if A is a linear operator and z is a complex number,

and there is a zero element 0. An important additional result is that the vector space L

can be given a

natural inner product structure, turning it into a Hilbert space.

(1) Show that the function (·, ·) on L

× L

deﬁned by

(A, B) ≡ tr



†



is an inner product function. This inner product is known as the Hilbert-Schmidt or trace inner

product.

(2) If V has d dimensions show that L

has dimension d

(3) Find an orthonormal basis of Hermitian matrices for the Hilbert space L

Solution

Concepts Involved: Linear Algebra, Trace, Inner Products, Hermitian Operators, Bases

(1) We show that (·, ·) satisﬁes the three properties of an inner product. Showing that it is linear in the

second argument, we have that:









= tr









tr(AB

) =

(A, B

)

where in the second to last equality we use the result of Exercise 2.38. To see that it is conjugate-

symmetric, we have that:

(A, B) = tr



†



= tr



†



= tr



†



∗

= (B, A)

∗

Finally, to show positive deﬁnitness, we have that:

(A, A) = tr



†



†

∗

≥ 0

so we conclude that (·, ·) is an inner product function.

(2) Suppose V has d dimensions. Then, the elements of L

which consist of linear operators A

V 7→ V

have representations as d × d matrices. There are d

such linearly independent matrices (take the

matrices with 1 in one of the d

entries and 0 elsewhere), and we conclude that L

has d

linearly

independent vectors and hence dimension d

(3) As discussed in the previous part of the question, one possible basis for this vector space would

be |v

⟩⟨v

| where |v

⟩ form an orthonormal basis of V with i, j ∈ {1, . . . d}. These of course are

just matrices with 1 in one entry and 0 elsewhere. It is easy to see that this is a basis as for any

A ∈ L

we can write A =

⟩⟨v

|. We can verify that these are orthonormal; suppose

⟩⟨v

| ̸= |v

⟩⟨v

|. Then, we have that:



⟩⟨v

|, |v

⟩⟨v



= tr



( |v

⟩⟨v

†

⟩⟨v



= tr



⟩⟨v



If |v

⟩ ̸= |v

⟩, then the above expression reduces to tr(0) = 0. If |v

⟩ = |v

⟩, then it follows that

⟩ ̸= |v

⟩ (else this would contradict |v

⟩⟨v

| ̸= |v

⟩⟨v

|) and in this case we have that:



⟩⟨v

|, |v

⟩⟨v



= tr



⟩⟨v



= tr



⟩⟨v



= 0

So we therefore have that the inner product of two non-identical elements in the basis is zero.

Furthermore, we have that:



⟩⟨v

|, |v

⟩⟨v



= tr



⟩⟨v

| |v

⟩⟨v



= tr



⟩⟨v



= 1

so we conﬁrm that this basis is orthonormal. However, evidently this basis is not Hermitian as if

i ̸= j, then ( |v

⟩⟨v

†

= |v

⟩⟨v

| ̸= |v

⟩⟨v

|. To ﬁx this, we can modify our basis slightly. We keep

the diagonal entries as is (as these are indeed Hermitian!) but for the oﬀ-diagonals, we replace every

pair of basis vectors |v

⟩⟨v

|, |v

⟩⟨v

| with:

⟩⟨v

| + |v

⟩⟨v

√

, i

⟩⟨v

| − |v

⟩⟨v

√

A quick veriﬁcation shows that these are indeed Hermitian:



⟩⟨v

| + |v

⟩⟨v

√



†

( |v

⟩⟨v

†

+ ( |v

⟩⟨v

†

√

⟩⟨v

| + |v

⟩⟨v

√



⟩⟨v

| − |v

⟩⟨v

√



†

= −i

( |v

⟩⟨v

†

− ( |v

⟩⟨v

†

√

= i

⟩⟨v

| − |v

⟩⟨v

√

It now suﬃces to show that these new vectors (plus the diagonals) form a basis and are orthonormal.

To see that these form a basis, observe that:

√

⟩⟨v

| + |v

⟩⟨v

√

−

√



⟩⟨v

| − |v

⟩⟨v

√



= |v

⟩⟨v

√

⟩⟨v

| + |v

⟩⟨v

√



⟩⟨v

| − |v

⟩⟨v

√



= |v

⟩⟨v

and since we know that |v

⟩⟨v

| for all i, j ∈ {1, . . . d} form a basis, this newly deﬁned set of vectors

must be a basis as well. Furthermore, since the new basis vectors are constructed from orthogonal

⟩⟨v

|, the newly deﬁned vectors will be orthogonal to each other if i

, j

̸= i

, j

. The only things

left to check is that for any choice of i, j that:

⟩⟨v

| + |v

⟩⟨v

√

and i

⟩⟨v

| − |v

⟩⟨v

√

are orthogonal, and that these vectors are normalized. Checking the orthogonality, we have:



⟩⟨v

| + |v

⟩⟨v

√

, i

⟩⟨v

| − |v

⟩⟨v

√



= tr



⟩⟨v

| + |v

⟩⟨v

√



⟩⟨v

| − |v

⟩⟨v

√



√



⟩⟨v

| − |v

⟩⟨v



= 0.

And checking the normalization, we have that:



⟩⟨v

| + |v

⟩⟨v

√

⟩⟨v

| + |v

⟩⟨v

√



= tr



⟩⟨v

| + |v

⟩⟨v

√



⟩⟨v

| + |v

⟩⟨v

√





⟩⟨v

| + |v

⟩⟨v



= 1



⟩⟨v

| − |v

⟩⟨v

√

, i

⟩⟨v

| − |v

⟩⟨v

√



= tr



⟩⟨v

| − |v

⟩⟨v

√



⟩⟨v

| − |v

⟩⟨v

√



= −



−|v

⟩⟨v

| − |v

⟩⟨v



= 1

Exercise 2.40: Commutation relations for the Pauli matrices

Verify the commutation relations

[X, Y ] = 2iZ; [Y, Z] = 2iX; [Z, X] = 2iY

There is an elegant way of writing this using ϵ

jkl

, the antisymmetric tensor on three indices, for which

jkl

= 0 except for ϵ

123

= ϵ

231

= ϵ

312

= 1, and ϵ

321

= ϵ

213

= ϵ

132

= −1:

[σ

, σ

] = 2i

l=1

jkl

Solution

Concepts Involved: Linear Algebra, Commutators.

We verify the proposed relations via computation in the computational basis:

[X, Y ] = XY −Y X =

0 1

1 0

0 −i

i 0

−

0 −i

i 0

0 1

1 0

i 0

0 −i

−

−i 0

0 i

= 2iZ

[Y, Z] = Y Z − ZY =

0 −i

i 0

1 0

0 −1

−

1 0

0 −1

0 −i

i 0

0 i

i 0

−

0 −i

−i 0

= 2iX

[Z, X] = ZX − XZ =

1 0

0 −1

0 1

1 0

−

0 1

1 0

0 −1

0 1

−1 0

−

0 −1

1 0

= 2iY

Exercise 2.41: Anti-commutation relations for the Pauli matrices

Verify the anticommutation relations

{σ

, σ

} = 0

Where i ̸= j are both chosen from the set 1, 2, 3. Also verify that (i = 0, 1, 2, 3)

= I

Solution

Concepts Involved: Linear Algebra, Anticommutators.

We again verify the proposed relations via computation in the computational basis:

{X, Y } = XY + Y X =

0 1

1 0

0 −i

i 0

0 −i

i 0

0 1

1 0

i 0

0 −i

−i 0

0 i

0 0

{Y, Z} = Y Z + ZY =

0 −i

i 0

1 0

0 −1

1 0

0 −1

0 −i

i 0

0 i

i 0

0 −i

−i 0

0 0

{Z, X} = ZX + XZ =

1 0

0 −1

0 1

1 0

0 1

1 0

0 −1

0 1

−1 0

0 −1

1 0

0 0

This proves the ﬁrst claim as {A, B} = AB + BA = BA + AB = {B, A} and the other 3 relations are

equivalent to the ones already proven. Verifying the second claim, we have:

1 0

0 1

1 0

0 1

1 0

0 1

1 0

0 1

1 0

0 1

0 −i

i 0

0 −i

i 0

1 0

0 1

1 0

0 −1

1 0

0 −1

1 0

0 1

Remark: Note that we can write this result consicely as {σ

, σ

} = 2δ

Exercise 2.42

Verify that

AB =

[A, B] + {A, B}

Solution

Concepts Involved: Linear Algebra, Commutators, Anticommutators.

By algebraic manipulation we obtain:

AB =

AB + AB

BA − BA

(AB − BA) + (AB + BA)

[A, B] + {A, B}

Exercise 2.43

Show that for j, k = 1, 2, 3,

= δ

I + i

l=1

jkl

Solution

Concepts Involved: Linear Algebra, Commutators, Anticommutators.

Applying the results of Exercises 2.40, 2.41, and 2.42, we have:

[σ

, σ

] + {σ

, σ

}

l=1

jkl

+ 2δ

= δ

I + i

l=1

jkl

Exercise 2.44

Suppose [A, B] = 0, {A, B} = 0, and A is invertible. Show that B must be 0.

Solution

Concepts Involved: Linear Algebra, Commutators, Anticommutators.

By assumption, we have that:

[A, B] = AB − BA = 0

{A, B} = AB + BA = 0.

Adding the ﬁrst line to the second we have:

2AB = 0 =⇒ AB = 0.

−1

exists by the invertibility of A, so multiplying by A

−1

on the left we have:

−1

AB = A

−1

0 =⇒ IB = 0 =⇒ B = 0.

Exercise 2.45

Show that [A, B]

†

= [B

†

, A

†

Solution

Concepts Involved: Linear Algebra, Commutators, Adjoints.

Using the properties of the adjoint, we have:

[A, B]

†

= (AB − BA)

†

= (AB)

†

− (BA)

†

= B

†

− A

†

= [B

†

, A

†

]

Exercise 2.46

Show that [A, B] = −[B, A].

Solution

Concepts Involved: Linear Algebra, Commutators

By the deﬁnition of the commutator:

[A, B] = AB − BA = −(BA − AB) = −[B, A]

Exercise 2.47

Suppose A and B are Hermitian. Show that i[A, B] is Hermitian.

Solution

Concepts Involved: Linear Algebra, Commutators, Hermitian Operators

Suppose A, B are Hermitian. Using the results of Exercises 2.45 and 2.46, we have:

(i[A, B])

†

= −i([A, B])

†

= −i[B

†

, A

†

] = i[A

†

, B

†

] = i[A, B].

Exercise 2.48

What is the polar decomposition of a positive matrix P ? Of a unitary matrix U? Of a Hermitian matrix,

Solution

Concepts Involved: Linear Algebra, Polar Decomposition, Positive Operators, Unitary Operators, Her-

mitian Operators

If P is a positive matrix, then no calculation is required; P = IP = P I is the polar decomposition (as I is

unitary and P is positive). If U is a unitary matrix, then J =

√

†

U =

√

I = I and K =

√

†

√

I = I

so the polar decomposition is U = UI = IU (where U is unitary and I is positive). If H is hermitian, we

then have that:

J =

√

†

H =

√

|i⟩⟨i| =

|λ

||i⟩⟨i|

and K =

√

†

|λ

||i⟩⟨i| in the same way. Hence the polar decomposition is H = U

|λ

||i⟩⟨i| =

|λ

||i⟩⟨i|U.

Exercise 2.49

Express the polar decomposition of a normal matrix in the outer product representation.

Solution

Concepts Involved: Linear Algebra, Polar Decomposition, Outer Products

Let A be a normal matrix. Then, A has spectral decomposition A =

|i⟩⟨i|. Therefore, we have that:

†

A = AA

†

′

∗

′

|i⟩⟨i|



′



′



′

∗

′

|i⟩⟨i

′

|δ

′

|λ

|i⟩⟨i|

We then have that:

J =

√

†

A =

|λ

|i⟩⟨i| =

|λ

||i⟩⟨i|

and K =

|λ

||i⟩⟨i| identically. Furthermore, U is unitary, so it also has a spectral decomposition of

|j⟩⟨j|. Hence we have the polar decomposition in the outer product representation as:

A = UJ = KU

A = U

|λ

||i⟩⟨i|

|λ

||i⟩⟨i|

A =

|λ

||j⟩⟨j|i⟩⟨i| =

|λ

|µ

|i⟩⟨i|j⟩⟨j|

Exercise 2.50

Find the left and right polar decompositions of the matrix

1 0

1 1

Solution

Concepts Involved: Linear Algebra, Polar Decomposition.

Let A =

1 0

1 1

. We start with the left polar decomposition, and hence ﬁnd J =

√

†

A. In order to do

this, we ﬁnd the spectral decompositions of A

†

A and AA

†

det



†

A − Iλ



= 0 =⇒ det





1 1

0 1

1 0

1 1

−

λ 0

0 λ





= 0 =⇒ det

2 − λ 1

1 1 − λ

= 0

=⇒ λ

− 3λ + 1 = 0

=⇒ λ

3 +

√

, λ

3 −

√

Solving for the eigenvectors, we have:

2 −

√

1 1 −

√

⟩ = 0 =⇒ |v

⟩ =

1 +

√

2 −

3−

√

1 1 −

3−

√

⟩ = 0 =⇒ |v

⟩ =

1 −

√

Normalizing, we get:

⟩ =

10 + 2

√

1 +

√

, |v

⟩ =

10 − 2

√

1 −

√

The spectral decomposition of A

†

A is therefore:

†

A = λ

⟩⟨v

| + λ

⟩⟨v

Calculating J, we therefore have:

J =

√

†

A =

⟩⟨v

| +

⟩⟨v

| =

√

3 1

1 2

The last equality is not completely trivial, but the algebra is tedious so we invite the reader to use a

symbolic calculator, as we have. We make the observation that:

A = UJ =⇒ U = AJ

−1

So calculating J

−1

, we have:

−1

√

⟩⟨v

| +

√

⟩⟨v

| =

√

2 −1

−1 3

Where we again have used the help of a symbolic calculator. Calculating U, we then have that:

U = AJ

−1

1 0

1 1

√

2 −1

−1 3

√

2 −1

1 2

Hence the left polar decomposition of A is given by:

A = UJ =





√

2 −1

1 2









√

3 1

1 2





We next solve for the right polar decomposition. We could repeat the procedure of solving for the spectral

decomposition of AA

†

, but we take a shortcut; since we know the K that satisﬁes:

A = KU

will be unique, and U is unitary, we can simply multiply both sides of the above equation on the right by

−1

= U

†

to obtain K. Hence:

K = AU

†

1 0

1 1

√

2 1

−1 2

√

2 1

1 3

Therefore the right polar decomposition of A is given by:

A = KU =





√

2 1

1 3









√

2 −1

1 2





Exercise 2.51

Verify that the Hadamard gate H is unitary.

Solution

Concepts Involved: Linear Algebra, Unitary Operators

We observe that:

†

H =

√

1 1

1 −1

√

1 1

1 −1

1 0

0 1

showing that H is indeed unitary.

Remark: The above calculation shows that H is also Hermitian and Idempotent.

Exercise 2.52

Verify that H

= I.

Solution

Concepts Involved: Linear Algebra

See the calculation and remark in the previous exercise.

Exercise 2.53

What are the eigenvalues and eigenvectors of H?

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors

Using the characteristic equation to ﬁnd the eigenvalues, we have:

det(H − Iλ) = 0 =⇒ det

√

− λ

√

−

√

− λ

= 0 =⇒ λ

− 1 = 0

=⇒ λ

= 1, λ

= −1

Finding the eigenvectors, we then have:

√

− 1

√

−

√

− 1

⟩ = 0 =⇒ |v

⟩ =

1 +

√

+ 1

√

−

√

+ 1

⟩ = 0 =⇒ |v

⟩ =

−1 +

√

Normalizing, we have:

⟩ =

2 +

√

1 +

√

, |v

⟩ =

2 −

√

−1 +

√

Exercise 2.54

Suppose A and B are commuting Hermitian operators. Prove that exp(A) exp(B) = exp(A + B). (Hint:

Use the results of Section 2.1.9.)

Solution

Concepts Involved: Linear Algebra, Operator Functions, Simultaneous Diagonalization

Since A, B commute, they can be simulatneously diagonalized; that is, there exists some orthonormal

basis |i⟩ of V such that A =

|i⟩⟨i| and B =

|i⟩⟨i|. Hence, using the deﬁnition of operator

functions, we have that:

exp(A) exp(B) = exp





|i⟩⟨i|





exp





′

⟩⟨i

′





′

exp(a

) exp(b

′

)|i⟩⟨i|i

′

⟩⟨i

′

exp(a

) exp(b

′

)|i⟩⟨i

′

|δ

′

exp(a

) exp(b

) |i⟩⟨i|

exp(a

+ b

) |i⟩⟨i|

= exp





+ b

) |i⟩⟨i|





= exp(A + B)

Exercise 2.55

Prove that U(t

, t

) deﬁned in Equation (2.91) is unitary.

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Spectral Decomposition, Operator Functions.

Since the Hamiltonian H is Hermitian, it is normal and hence has spectral decomposition:

H =

E |E⟩⟨E|

where all E are real by the Hermicity of H, and |E⟩ is an orthonormal basis of the Hilbert space. We

then have that:

U(t

, t

) ≡ exp



−iH(t

− t

)

ℏ



= exp



−i

E |E⟩⟨E|(t

− t

)

ℏ



exp



−iE(t

− t

)

ℏ



|E⟩⟨E|

Hence calculating U

†

, t

) we have:

†

, t

) =





exp



−iE(t

− t

)

ℏ



|E⟩⟨E|





†

exp



−iE(t

− t

)

ℏ



∗



|E⟩⟨E|



†

exp



iE(t

− t

)

ℏ



|E⟩⟨E|

Therefore computing U

†

, t

)U(t

, t

) we have:

†

, t

)U(t

, t

) =





exp



−iE(t

− t

)

ℏ



|E⟩⟨E|









′

exp



′

− t

)

ℏ



′

⟩⟨E

′





′

exp



−iE(t

− t

)

ℏ



exp



′

− t

)

ℏ



′

|E⟩⟨E

′

exp



−iE(t

− t

)

ℏ



exp



iE(t

− t

)

ℏ



|E⟩⟨E|

= I

where in the second equality we use the fact that the eigenstates are orthogonal. We conclude that U is

unitary.

Exercise 2.56

Use the spectral decomposition to show that K ≡ −i log(U ) is Hermitian for any unitary U, and thus

U = exp(iK) for some Hermitian K.

Solution

Concepts Involved: Linear Algebra, Hermitian Operators, Unitary Operators, Spectral Decomposition,

Operator Functions.

Suppose U is unitary. Then, U is normal and hence has spectral decomposition:

U =

|j⟩⟨j|

where |j⟩ are eigenvectors of U with eigenvalues λ

, and |j⟩ forms an orthonormal basis of the Hilbert

space. By Exercise 2.18, all eigenvalues of unitary operators have eigenvalues of modulus 1, so we can let

= exp



iθ



where θ

∈ R and hence write the above as:

U =

exp



iθ



|j⟩⟨j|

We then have that:

K ≡ −i log(U) = −i log





exp



iθ



|j⟩⟨j|





−i log



exp



iθ





|j⟩⟨j| =

−i(iθ

) |j⟩⟨j|

|j⟩⟨j|

We then observe that:

†





|j⟩⟨j|





†

|j⟩⟨j|

as the θ

s are real and (|j⟩⟨j|)

†

= |j⟩⟨j|. Hence K is Hermitian. Then, multiplying both sides in

K = −i log(U) by i and exponentiating both sides, we obtain the desired relation.

Exercise 2.57: Cascaded measurements are single measurements

Suppose {L

} and {M

} are two sets of measurement operators. Show that a measurement deﬁned

by the measurement operators {L

} followed by a measurement deﬁned by the measurement operators

} is physically equivalent to a single measurement deﬁned by measurement operators {N

} with

the representation N

≡ M

Solution

Concepts Involved: Linear Algebra, Quantum Measurement.

Suppose we have (normalized) initial quantum state |ψ

⟩. Then, the state after measurement of L

given by deﬁnition to be:

|ψ

⟩ 7→ |ψ

⟩ =

|ψ

⟩

⟨ψ

†

|ψ

⟩

The state after measurement of M

on |ψ

⟩ is then given to be:

|ψ

⟩ 7→ |ψ

⟩ =

|ψ

⟩

⟨ψ

†

|ψ

⟩

|ψ

⟩

⟨ψ

†

|ψ

⟩

†

⟨ψ

†

|ψ

⟩

†

|ψ

⟩

⟨ψ

†

|ψ

⟩

|ψ

⟩

⟨ψ

†

|ψ

⟩

⟨ψ

†

|ψ

⟩

⟨ψ

†

|ψ

⟩

|ψ

⟩

⟨ψ

†

|ψ

⟩

Conversely, the state of |ψ

⟩ after measurement of N

= M

is given by:

|ψ

⟩ 7→ |ψ

⟩ =

|ψ

⟩

⟨ψ

†

|ψ

⟩

We see that |ψ

⟩ = |ψ

⟩ (that is, the cascaded measurment produces the same result as the single

measurement), proving the claim.

Exercise 2.58

Suppose we prepare a quantum system in an eigenstate |ψ⟩ of some observable M with corresponding

eigenvalue m. What is the average observed value of M , and the standard deviation?

Solution

Concepts Involved: Linear Algebra, Quantum Measurement, Expectation, Standard Deviation.

By the deﬁnition of expectation, we have that:

⟨M⟩

|ψ⟩

= ⟨ψ|M|ψ⟩ = ⟨ψ|m|ψ⟩ = m⟨ψ|ψ⟩ = m

Where in the second equality we use that |ψ⟩ is an eigenstate of M with eigenvalue m, and in the last

equality we use that |ψ⟩ is a normalized quantum state. Next, calculating





|ψ⟩

, we have:

|ψ⟩

= ⟨ψ|M

|ψ⟩ = ⟨ψ|MM|ψ⟩ = ⟨ψ|M

†

M|ψ⟩ = ⟨ψ|m

∗

m|ψ⟩ = ⟨ψ|m

|ψ⟩ = m

⟨ψ|ψ⟩ = m

Note that we have used the fact that M is Hermitian (it is an observable) to use that M

†

= M and

∗

= m as all eigenvalues of Hermitian operators are real. Now calculating the standard deviation, we

have:

∆(M) =

⟨M

⟩ − ⟨M⟩

− (m)

= 0

Exercise 2.59

Suppose we have qubit in the state |0⟩, and we measure the observable X. What is the average value of

X? What is the standard deviation of X?

Solution

Concepts Involved: Linear Algebra, Quantum Measurement, Projective Measurement, Expectation, Stan-

dard Deviation.

By the deﬁnition of expectation, we have:

⟨X⟩

|0⟩

= ⟨0|X|0⟩ = ⟨0|1⟩ = 0

Next calculating





|0⟩

, we have:

|0⟩

= ⟨0|XX|0⟩ = ⟨1|1⟩ = 1

Hence the standard deviation of X is given by:

∆(X) =

⟨X

⟩ − ⟨X⟩

√

1 − 0 = 1

Exercise 2.60

Show that v ·σ has eigenvalues ±1, and that the projectors into the corresponding eigenspaces are given

by P

= (I ± v · σ)/2.

Solution

Concepts Involved: Eigenvalues, Projectors.

Let |v⟩ be a unit vector. We already showed in Exercise 2.35 that v ·σ has eigenvalues λ

= 1, λ

−

= −1.

We next prove a general statement; namely, that for a observable on a 2-dimensional Hilbert space with

eigenvalues λ

= ±1 has projectors

I ± O

To see this is the case, let P

= |o

⟩⟨o

|, P

−

= |o

−

⟩⟨o

−

|, I = |o

⟩⟨o

| + |o

−

⟩⟨o

−

|, and O =

⟩⟨o

| − |o

−

⟩⟨o

−

|. We then have that:

I + O

⟩⟨o

| − |o

−

⟩⟨o

−

= |o

⟩⟨o

| = P

I − O

−

⟩⟨o

−

| + |o

−

⟩⟨o

−

| − |o

⟩⟨o

| + |o

−

⟩⟨o

−

= |o

−

⟩⟨o

−

| = P

−

Hence the general statement is proven. Applying this to O = v ·σ (which is indeed Hermitian and hence

an observable as each of X, Y, Z are Hermitian), we get that:

I ± v · σ

as claimed.

Exercise 2.61

Calculate the probability of obtaining the result +1 for a measurement of v ·σ, given that the state prior

to measurement is |0⟩. What is the state of the system after measurement if +1 is obtained?

Solution

Concepts Involved: Quantum Measurement, Projective Measurement.

The probability of obtaining the result +1 is given by:

p(+) = ⟨0|P

|0⟩ = ⟨0|

I + v · σ

|0⟩

We recall from from Exercise 2.35 that:

v · σ =

− iv

+ iv

−v

= v

|0⟩⟨0| + (v

− iv

) |0⟩⟨1| + (v

+ iv

) |1⟩⟨0| − v

|1⟩⟨1|.

Hence computing p(+), we get:

p(+) = ⟨0|



|0⟩ +



|0⟩ + (v

+ iv

)|1⟩





= ⟨0|



1 + v

|0⟩ +

+ iv

|1⟩



1 + v

⟨0|0⟩ +

+ iv

⟨0|1⟩ =

1 + v

so the probability of measuring the +1 outcome is

1+v

. The state after the measurement of the +1

outcome is given by:

|0⟩ 7→

|0⟩

p(+)

1+v

|0⟩ +

+iv

|1⟩

1+v

2(1 + v

)



(1 + v

)|0⟩ + (v

+ iv

)|1⟩



Exercise 2.62

Show that any measurement where the measurement operators and the POVM elements coincide is a

projective measurement.

Solution

Concepts Involved: Quantum Measurement, Projective Measurement, POVM Measurement.

Suppose we have that the measurement operators M

are equal to the POVM elements E

. In this case,

we have that:

= E

≡ M

†

is positive by Exercise 2.25, so it follows that M

is positive and hence Hermitian by Exercise

2.24. Hence, M

†

= M

, and therefore:

= M

†

= M

From which we conclude that M

are projective measurement operators.

Exercise 2.63

Suppose a measurement is described by measurement operators M

. Show that there exist unitary

operators U

such that M

= U

√

, where E

is the POVM associated to the measurement.

Solution

Concepts Involved: Quantum Measurement, POVM Measurement, Polar Decomposition.

Since M

is a linear operator, by the left polar decomposition there exists unitary U such that:

= U

†

= U

where in the last equality we use that M

†

= E

Exercise 2.64

(∗) Suppose Bob is given a quantum state chosen from a set |ψ

⟩, . . . , |ψ

⟩ of linearly independent

states. Construct a POVM {E

, E

, . . . , E

m+1

} such that if outcome E

occurs, 1 ≤ i ≤ m, then Bob

knows with certainty that he was given the state |ψ

⟩. (The POVM must be such that ⟨ψ

|ψ

⟩ > 0

for each i.)

Solution

Concepts Involved: POVM Measurement, Orthogonality

Let H be the Hilbert space where the given states lie, and let V be the m-dimensional subspace spanned

by |ψ

⟩, . . . , |ψ

⟩. For each i ∈ {1, . . . , m}, let W

be the subspace of V spanned by



|ψ

⟩

j ̸= i



. Let

⊥

be the orthogonal complement of W

which consists of all states in H orthogonal to all states in W

We then have that any vector in V can be written as the sum of a vector in W

and W

⊥

∩ V (see for

example Theorem 6.47 in Axler’s Linear Algebra Done Right). Therefore, for any |ψ

⟩ we can write:

|ψ

⟩ = |w

⟩ + |p

⟩

Where |w

⟩ ∈ W

and |p

⟩ ∈ W

⊥

∩ V . Deﬁne E

⟩⟨p

. By construction, we have that for any

|ψ⟩ ∈ H:

⟨ψ|E

|ψ⟩ =



⟨ψ|p

⟩



≥ 0

so the E

s are positive are required. Furthermore, deﬁning E

i+1

= I −

i=1

we again see that for any

|ψ⟩ ∈ H:

⟨ψ|E

i+1

|ψ⟩ = ⟨ψ|I|ψ⟩ −

i=1

⟨ψ|E

|ψ⟩ = 1 −

i=1

⟨ψ|E

|ψ⟩ ≥ 1 −

i=1

= 0

so E

i+1

is also positive as required. Finally, to see that the E

, . . . E

have the desired properties, observe

by construction that since |p

⟩ ∈ W

⊥

∩ V , it follows that ⟨ψ

⟩ = 0 for any j ̸= i (as the |p

⟩ will be

orthogonal to all the vectors in



|ψ

⟩

j ̸= i



by construction). Calculating ⟨ψ

|ψ

⟩, we observe that:

⟨ψ

|ψ

⟩ =



⟨w

| + ⟨p



⟩⟨p



⟩ + |p

⟩





⟨p

⟩



≥ 0

so if Bob measures E

, he can be certain that he was given the state |ψ

⟩.

Exercise 2.65

Express the states (|0⟩ + |1⟩)/

√

2 and (|0⟩ − |1⟩)/

√

2 is a basis in which they are not the same up to a

relative phase shift.

Solution

Concepts Involved: Linear Algebra, Phase

Let us deﬁne our basis to be |+⟩

= (|0⟩ + |1⟩)/

√

2 and |−⟩

= (|0⟩ − |1⟩)/

√

2. Our two states are then

just the basis vectors of this basis (|+⟩, |−⟩) and are not the same up to relative phase shift.

Exercise 2.66

Show that the average value of the observable X

for a two qubit system measured in the state

(|00⟩ + |11⟩)/

√

2 is zero.

Solution

Concepts Involved: Quantum Measurement, Expectation, Composite Systems

Computing the expectation value of X

, we get:

⟨X

⟩ =



⟨00| + ⟨11|

√





|00⟩ + |11⟩

√





⟨00| + ⟨11|

√



|00⟩ + X

|11⟩

√





⟨00| + ⟨11|

√



|10⟩ − |01⟩

√





⟨00|10⟩ − ⟨00|01⟩ + ⟨11|10⟩ − ⟨11|01⟩



(0 + 0 + 0 + 0)

= 0.

Exercise 2.67

Suppose V is a Hilbert space with a subspace W . Suppose U

W 7→ V is a linear operator which

preserves inner products, that is, for any |w

⟩ and |w

⟩ in W ,

⟨w

†

U|w

⟩ = ⟨w

⟩

Prove that there exists a unitary operator U

′

V 7→ V which extends U. That is, U

′

|w⟩ = U |w⟩ for all

|w⟩ in W , but U

′

is deﬁned on the entire space V . Usually we omit the prime symbol

′

and just write U

to denote the extension.

Solution

Concepts Involved: Linear Algebra, Inner Products, Unitary Operators

By assumption we have that U is unitary on W as ⟨w

†

U|w

⟩ = ⟨w

⟩ and hence U

†

U = I

Hence, it has spectral decomposition:

U =

|j⟩⟨j|

where



|j⟩



is an orthonormal basis of the subspace W . Then, let



|j⟩



∪



|i⟩



be an orthnormal basis

of the full space V . We then deﬁne:

′

|j⟩⟨j| +

|i⟩⟨i| = U +

|i⟩⟨i|

We can then see that for any |w⟩ ∈ W that:

′

|w⟩ =





U +

|i⟩⟨i|





|w⟩ = U |w⟩ +

|i⟩⟨i|w⟩ = U |w⟩

where in the last line we use that ⟨i|w⟩ = 0 as |i⟩ are not in the subspace W . Finally, verifying the

unitarity of U

′

we have that:

′†

′





∗

|j⟩⟨j| +

|i⟩⟨i|









′

|j⟩⟨j| +

′

|i⟩⟨i|





′

|j⟩⟨j|j

′

⟩⟨j

′

| +

′

|j⟩⟨j|i

′

⟩⟨i

′

| +

′

|i⟩⟨i|j

′

⟩⟨j

′

| +

′

|i⟩⟨i|i

′

⟩⟨i

′

⟨j|j

′

⟩δ

′

⟨i|i

′

⟩δ

′

|j⟩⟨j| +

|i⟩⟨i|

= I

Exercise 2.68

Prove that |ψ⟩ ̸= |a⟩|b⟩ for all single qubit states |a⟩ and |b⟩.

Solution

Concepts Involved: Linear Algebra, Composite Systems, Entanglement.

Recall that:

|ψ⟩ =

|00⟩ + |11⟩

√

have that |a⟩ = α|0⟩ + β|1⟩ and |b⟩ = γ|0⟩ + δ|1⟩ for some α, β, γ, δ ∈ C such that |α|

+ |β|

= 1 and

|γ|

+ |δ|

= 1. We then have that:

|a⟩|b⟩ = (α|0⟩ + β|1⟩)(γ|0⟩ + δ|1⟩) = αγ|00⟩ + αδ|01⟩ + βγ|10⟩ + βδ|11⟩.

Where we have used the linearity of the tensor product (though we supress the ⊗ symbols in the above

expression). We then have that:

|ψ⟩ =

|00⟩ + |11⟩

√

= αγ|00⟩ + αδ|01⟩ + βγ|10⟩ + βδ|11⟩

which forces αδ = 0 and βγ = 0. However, we then have that at least one of αγ or βδ is also zero, and

we thus reach a contradiction.

Exercise 2.69

Verify that the Bell basis forms an orthonormal basis for the two qubit state space.

Solution

Concepts Involved: Linear Algebra, Orthogonality, Bases, Composite Systems.

Recall that the bell basis is given by:

⟩ =

|00⟩ + |11⟩

√

, |B

⟩

|00⟩ − |11⟩

√

, |B

⟩ =

|01⟩ + |10⟩

√

, |B

⟩ =

|01⟩ − |10⟩

√

We ﬁrst verify orthonormality. We observe that:

⟨B

⟩ =



⟨00| + ⟨11|

√



|00⟩ + |11⟩

√





⟨00|00⟩ + ⟨00|11⟩ + ⟨11|00⟩ + ⟨11|11⟩



= 1

⟨B

⟩ =



⟨00| + ⟨11|

√



|00⟩ − |11⟩

√





⟨00|00⟩ − ⟨00|11⟩ + ⟨11|00⟩ − ⟨11|11⟩



= 0

⟨B

⟩ =



⟨00| + ⟨11|

√



|01⟩ + |10⟩

√





⟨00|01⟩ + ⟨00|10⟩ + ⟨11|01⟩ + ⟨11|10⟩



= 0

⟨B

⟩ =



⟨00| + ⟨11|

√



|01⟩ − |10⟩

√





⟨00|01⟩ − ⟨00|10⟩ + ⟨11|01⟩ − ⟨11|10⟩



= 0

⟨B

⟩ =



⟨00| − ⟨11|

√



|00⟩ − |11⟩

√





⟨00|00⟩ − ⟨00|11⟩ − ⟨11|00⟩ + ⟨11|11⟩



= 1

⟨B

⟩ =



⟨00| − ⟨11|

√



|01⟩ + |10⟩

√





⟨00|01⟩ + ⟨00|10⟩ − ⟨11|01⟩ − ⟨11|10⟩



= 0

⟨B

⟩ =



⟨00| − ⟨11|

√



|01⟩ − |10⟩

√





⟨00|01⟩ − ⟨00|10⟩ − ⟨11|01⟩ + ⟨11|10⟩



= 0

⟨B

⟩ =



⟨01| + ⟨10|

√



|01⟩ + |10⟩

√





⟨01|01⟩ + ⟨01|10⟩ + ⟨10|01⟩ + ⟨10|10⟩



= 1

⟨B

⟩ =



⟨01| + ⟨10|

√



|01⟩ − |10⟩

√





⟨01|01⟩ − ⟨01|10⟩ + ⟨10|01⟩ − ⟨10|10⟩



= 0

⟨B

⟩ =



⟨01| − ⟨10|

√



|01⟩ − |10⟩

√





⟨01|01⟩ − ⟨01|10⟩ − ⟨10|01⟩ + ⟨10|10⟩



= 1

so orthonormality is veriﬁed. We know show that it is a basis. Recall that we can write any vector |ψ⟩ in

the 2 qubit state space as:

|ψ⟩ = α|00⟩ + β|01⟩ + γ|10⟩ + δ|11⟩

where α, β, γ, δ ∈ C and |α|

+ |β|

+ |γ|

+ |δ|

= 1. We then observe that this is equivalent to:



α + δ

√



⟩ +



α − δ

√



⟩ +



β + γ

√



⟩ +



β − γ

√



⟩ (∗)

as:



α + δ

√



|00⟩ + |11⟩

√



α − δ

√



|00⟩ − |11⟩

√



β + γ

√



|01⟩ + |10⟩

√



β − γ

√



|01⟩ − |10⟩

√



−



|00⟩ +



−



|11⟩



−



|01⟩ +



−



|10⟩

= α|00⟩ + β|01⟩ + γ|10⟩ + δ|11⟩ = |ψ⟩

Hence (∗) shows that the Bell states form a basis.

Exercise 2.70

Suppose E is any positive operator acting on Alice’s qubit Show that ⟨ψ|E ⊗ I|ψ⟩ takes the same value

when |ψ⟩ is any of the four Bell states. Suppose some malevolent third party (‘Eve’) intercepts Alice’s

qubit on the way to Bob in the superdense coding protocol. Can Eve infer anything about which of the

four possible bit strings 00, 01, 10, 11 Alice is trying to send? If so, how, or if not, why not?

Solution

Concepts Involved: Linear Algebra, Superdense Coding, Quantum Measurement

Let E be a positive operator. We have that E for a single qubit can be written as a linear combination

of the Pauli matrices:

E = a

I + a

X + a

Y + a

To see that this is the case, consider that the vector space of linear operators acting on a single qubit

has dimension 4 (one easy way to see this is that the matrix representations of these operators have 4

entries). Hence, any set of 4 linearly independent linear operators form a basis for the space. As I, X, Y, Z

are linearly independent, it follows that they form a basis of the space of linear operators on one qubit.

Hence any E can be written as above (Remark: the above decomposition into Paulis is possible regardess

of whether E is positive or not).

We then have that:

⟨B

|E ⊗ I|B

⟩ =



⟨00| + ⟨11|

√



E ⊗ I



|00⟩ + |11⟩

√





⟨00| + ⟨11|

√



I + a

X + a

Y + a

Z) ⊗ I



|00⟩ + |11⟩

√





⟨00| + ⟨11|

√



|00⟩ + |11⟩

√

+ a

|10⟩ + |01⟩

√

+ a

i|10⟩ − i|01⟩

√

+ a

|00⟩ − |11⟩

√



+ a

− a

)

= a

where in the second last equality we use the orthonormality of



|00⟩, |01⟩, |10⟩, |11⟩



. Repeating the same

process for the other Bell states, we have:

⟨B

|E ⊗ I|B

⟩ =



⟨00| − ⟨11|

√



I + a

X + a

Y + a

Z) ⊗ I



|00⟩ − |11⟩

√





⟨00| − ⟨11|

√



|00⟩ − |11⟩

√

+ a

|10⟩ − |01⟩

√

+ a

i|10⟩ + i|01⟩

√

+ a

|00⟩ + |11⟩

√



+ a

− a

)

= a

⟨B

|E ⊗ I|B

⟩ =



⟨01| + ⟨10|

√



I + a

X + a

Y + a

Z) ⊗ I



|01⟩ + |10⟩

√





⟨01| + ⟨10|

√



|01⟩ + |10⟩

√

+ a

|11⟩ + |00⟩

√

+ a

i|11⟩ − i|00⟩

√

+ a

|01⟩ − |10⟩

√



+ a

− a

)

= a

⟨B

|E ⊗ I|B

⟩ =



⟨01| − ⟨10|

√



I + a

X + a

Y + a

Z) ⊗ I



|01⟩ − |10⟩

√





⟨01| − ⟨10|

√



|01⟩ − |10⟩

√

+ a

|11⟩ − |00⟩

√

+ a

i|11⟩ + i|00⟩

√

+ a

|01⟩ + |10⟩

√



+ a

− a

)

= a

Now, suppose that Eve intercepts Alice’s qubit. Eve cannot infer anything about which of the four

possible bit strings that Alice is trying to send, as any single-qubit measurement that Eve can perform on

the intercepted qubit will return the value:

⟨ψ|M

†

M ⊗ I|ψ⟩

Where M is the (single-qubit) measurement operator. But, M

†

M is positive, so by the above argument,

the measurement outcome will be the same regardless of which Bell state |ψ⟩ is. Hence, Eve cannot obtain

the information about the bit string.

Exercise 2.71: Criterion to decide if a state is mixed or pure

Let ρ be a density operator. Show that tr





≤ 1, with equality if and only if ρ is a pure state.

Solution

Concepts Involved: Linear Algebra, Trace, Density Operators, Pure States, Mixed States.

Recall that a density operator ρ is pure if:

ρ = |ψ⟩⟨ψ|

for some normalized quantum state vector |ψ⟩.

Since ρ is a positive operator, by the spectral decomposition we have that:

ρ =

|i⟩⟨i|

where p

≥ 0 (due to positivity) and |i⟩ are orthonormal. Furthermore, by the property of density operators,

we have that tr(ρ) = 1, hence:

tr(ρ) = tr





|i⟩⟨i|







|i⟩⟨i|



= 1

where in the second equality we use the linearity of the trace. We obtain that 0 ≤ p

≤ 1 for each i.

Calculating ρ

, we have that:





|i⟩⟨i|









′

⟩⟨i

′





′

|i⟩⟨i|i

′

⟩⟨i| =

′

|i⟩⟨i

′

|δ

′

|i⟩⟨i|

Hence:







|i⟩⟨i|



≤

= 1

where in the inequality we use the fact that p

≤ p

as 0 ≤ p

≤ 1. The inequality becomes an equality

when p

= p

, that is, when p

= 0 or p

= 1. In order for tr(ρ) = 1 to hold, we have that p

= 1 for

one i and zero for all others. Hence, ρ in this case is a pure state. Conversely, suppose ρ is a pure state.

Then:





= tr



|ψ⟩⟨ψ|ψ⟩⟨ψ|



= tr



|ψ⟩⟨ψ|



= 1.

Exercise 2.72: Bloch sphere for mixed states

The Bloch sphere picture for pure states of a single qubit was introduced in Section 1.2. This description

has an important generalization to mixed states as follows.

(1) Show that an arbitrary density matrix for a mixed state qubit may be written as

ρ =

I + r · σ

Where r is a real three-dimensional vector such that ∥r∥ ≤ 1. This vector is known as the Bloch

vector for the state ρ.

(2) What is the Bloch vector representation for the state ρ = I/2?

(3) Show that a state ρ is pure if and only if ∥r∥ = 1.

(4) Show that for pure states the description of the Bloch vector we have given coincides with that in

Section 1.2.

Solution

Concepts Involved: Linear Algebra, Trace, Density Operators, Pure States, Mixed States

(1) Since {I, X, Y, Z} form an basis the vector space of single-qubit linear operators, we can write (for

any ρ, regardless of whether it is a density operator or not):

ρ = a

I + a

X + a

Y + a

for constants a

, a

∈ C. Since ρ is a Hermitian operator, we ﬁnd that each of these constants

are actually real, as:

I + a

X + a

Y + a

Z = ρ = ρ

†

= a

∗

†

+ a

∗

†

+ a

∗

†

+ a

∗

†

= a

∗

I + a

∗

X + a

∗

Y + a

∗

Now, we require that tr(ρ) = 1 for any density operator, hence:

tr(ρ) = tr(a

I + a

X + a

Y + a

Z) = a

tr(I) + a

tr(X) + a

tr(Y ) + a

tr(Z) = 2a

= 1

from which we obtain that a

. Note that in the second equality we use the linearity of the

trace, and in the third equality we use that tr(I) = 2 and tr(σ

) = 0 for i ∈ {1, 2, 3} (Exercise

2.36). Calculating ρ

, we have that:

I +

X +

Y +

Z +

X + a

+ a

XY + a

Y + a

Y X + a

+ a

Y Z +

Z + a

ZX + a

ZY + a

Now, using that



, σ



= 0 for i, j ∈ {1, 2, 3}, i ̸= j and that σ

= I for any i ∈ {1, 2, 3}

(Exercise 2.41), the above simpliﬁes to:



+ a



I + a

X + a

Y + a

Taking the trace of ρ

we have that:







+ a



tr(I) + a

tr(X) + a

tr(Y ) + a

tr(Z) = 2



+ a



From the previous exercise (Exercise 2.71) we know that tr





≤ 1, so:



+ a



≤ 1 =⇒ a

+ a

≤

=⇒

+ a

≤

Hence we can write:

ρ =

I + r

X + r

Y + r

I + r · σ

with ∥r∥ ≤ 1.

(2) The Bloch representation for the state ρ =

is the above form with r = 0. This vector corresponds

to the center of the Bloch sphere, which is a maximally mixed state (tr





is minimized, with





(3) From the calculation in part (1), we know that for any ρ:





= 2

1 + r

+ r

1 + r

+ r

if ∥r∥ = 1, then r

+ r

= 1. Hence, tr





= 1 and ρ is pure by Exercise 2.71. Conversely,

suppose ρ is pure. Then, tr





= 1, so:

1 + r

+ r

= 1 =⇒ r

+ r

= 1 =⇒ ∥r∥ = 1.

(4) In section 1.2, we looked at states that lie on the surface of the Bloch sphere, which we parameterized

as:

|ψ⟩ = cos





|0⟩ + e

iφ

sin





|1⟩.

Calculating the density operator corresponding to |ψ⟩, we have:

ρ = |ψ⟩⟨ψ| = cos





|0⟩⟨0| + cos





sin





−iφ

|0⟩⟨1|

+ cos





sin





iφ

|1⟩⟨0| + sin





|1⟩⟨1|

= cos





|0⟩⟨0| +

sin(θ)e

−iφ

|0⟩⟨1| +

sin(θ)e

iφ

|1⟩⟨0| + sin





|1⟩⟨1|

Conversely, we have that (in the computational basis) our proposed form of ρ =

I+r·σ

can be

represented as:

ρ =

1 + r

|0⟩⟨0| +

− ir

|0⟩⟨1| +

+ ir

|1⟩⟨0| +

1 − r

|1⟩⟨1|

Solving for r

, r

by equating the two expressions for ρ (using Euler’s formula and sin(2θ) =

2 cos(θ) sin(θ)), we have:

= cos(φ) sin(θ), r

= sin(φ) sin(θ), r

= 2 cos





− 1 = cos(θ)

Calculating ∥r∥ we have that:

∥r∥ =

+ r

cos

(φ) sin

(θ) + sin

(φ) cos

(θ) + cos

(θ)

sin

(θ) + cos

(θ)

= 1

so we see that indeed, the two deﬁnitions coincide for pure states (as ∥r∥ = 1).

Exercise 2.73

(∗) Let ρ be a density operator. A minimal ensemble for ρ is an ensemble



, |ψ

⟩



containing a number

of elements equal to the rank of ρ. Let |ψ⟩ be any state in the support of ρ. (The support of a Hermitian

operator A is the vector space spanned by the eigenvectors of A with non-zero eigenvalues.) Show that

there is a minimal ensemble for ρ that contains |ψ⟩, and moreover that in any such ensemble |ψ⟩ must

appear with probability

⟨ψ

|ρ

−1

|ψ

⟩

where ρ

−1

is deﬁned to be the inverse of ρ, when ρ is considered as an operator acting only on the support

of ρ. (This deﬁnition removes the problem that ρ may not have an inverse.)

Solution

Concepts Involved: Below, we will use the unitary freedom in the ensemble for density matrices which

is also known as Uhlmann’s theorem. Speciﬁcally recall that ρ =

|ψ

⟩⟨ψ

| =

|φ

⟩⟨φ

| for

ensembles



, |ψ

⟩



and



, |φ

⟩



if and only if

√

|ψ

⟩ =

√





for some unitary matrix u

Using the spectral decomposition of the density matrix we have

ρ =

k=1

|k⟩⟨k| with λ

> 0

where all the eigenvectors with eigenvalue 0 have been removed. Thus, the set of vectors S =



|k⟩



k=1

forms a spanning set set for the support of ρ. An element in the support of ρ can thus be decomposed as

|ψ

⟩ =

|k⟩ =

⟨k|ψ

⟩|k⟩

Assuming that |ψ

⟩ occurs with probability p

, we can use the Uhlmann’s theorem quoted above to arrive

at the relation

√

|ψ

⟩

|k⟩ =

√

⟨k|ψ

⟩|k⟩,

which allows us relate the elements of one of the columns (i th) of the unitary matrix to

√

⟨k|ψ

⟩.

Such a relation can always be satisﬁed for a unitary matrix with dimension r. As u is unitary, we have

= 1 =⇒ 1 =

⟨ψ

|k⟩⟨k|ψ

⟩

=⇒ p

⟨ψ

|k⟩⟨k|ψ

⟩

⟨ψ

|k⟩⟨k|ψ

⟩

⟨ψ

|ρ

−1

|ψ

⟩

|ψ

⟩ = ρρ

−1

|ψ

⟩

i=1

|ψ

⟩⟨ψ

|ρ

−1

|ψ

⟩

i=1

⟨ψ

|ρ

−1

|ψ

⟩|ψ

⟩.

But now note that {|ψ

⟩}

j=1

are linearly independent and |ψ

⟩

i=1

|ψ

⟩.

=⇒ p

⟨ψ

|ρ

−1

|ψ

⟩ = 1.

Thus, the probability associated with the state |ψ

⟩ in the ensemble is given by

⟨ψ

|ρ

−1

|ψ

⟩

Exercise 2.74

Suppose a composite of systems A and B is in the state |a⟩ |b⟩, where |a⟩ is a pure state of system A,

and |b⟩ is a pure state of system B. Show that the reduced density operator of system A alone in a pure

state.

Solution

Concepts Involved: Linear Algebra, Density Operators, Reduced Density Operators, Partial Trace, Pure

States.

Suppose we have |a⟩|b⟩ ∈ A ⊗ B. Then, the density operator of the combined system is given as

= (|a⟩|b⟩)(⟨a|⟨b|) = |a⟩⟨a| ⊗ |b⟩⟨b|. Calculating the reduced density operator of system A by tracing

out system B, we have

= tr

(ρ

) = tr

( |a⟩⟨a| ⊗ |b⟩⟨b|) = |a⟩⟨a|tr



|b⟩⟨b|



= |a⟩⟨a|⟨b|b⟩ = |a⟩⟨a|.

Hence we ﬁnd that ρ

= |a⟩⟨a| is indeed a pure state.

Exercise 2.75

For each of the four Bell states, ﬁnd the reduced density operator for each qubit.

Solution

Concepts Involved: Linear Algebra, Density Operators, Reduced Density Operators, Partial Trace.

For the bell state |B

⟩, we have the density operator:

ρ =



|00⟩ + |11⟩

√



⟨00| + ⟨11|

√



|00⟩⟨00| + |11⟩⟨00| + |00⟩⟨11| + |11⟩⟨11|

Obtaining the reduced density operator for qubit A, we have:

= tr

(ρ) =

( |00⟩⟨00|) + tr

( |00⟩⟨11|) + tr

( |11⟩⟨00|) + tr

( |11⟩⟨11|)

|0⟩⟨0|⟨0|0⟩ + |0⟩⟨1|⟨1|0⟩ + |1⟩⟨0|⟨0|1⟩ + |1⟩⟨1|⟨1|1⟩

|0⟩⟨0| + |1⟩⟨1|

Obtaining the reduced density operator for qubit B, we have:

= tr

(ρ) =

( |00⟩⟨00|) + tr

( |00⟩⟨11|) + tr

( |11⟩⟨00|) + tr

( |11⟩⟨11|)

⟨0|0⟩|0⟩⟨0| + ⟨1|0⟩|0⟩⟨1| + ⟨0|1⟩|1⟩⟨0| + ⟨1|1⟩|1⟩⟨1|

|0⟩⟨0| + |1⟩⟨1|

We repeat a similar process for the other four bell states. For |B

⟩, we have:

ρ =



|00⟩ − |11⟩

√



⟨00| − ⟨11|

√



|00⟩⟨00| − |00⟩⟨11| − |11⟩⟨00| + |11⟩⟨11|

( |00⟩⟨00|) − tr

( |00⟩⟨11|) − tr

( |11⟩⟨00|) + tr

( |11⟩⟨11|)

|0⟩⟨0|⟨0|0⟩ − |0⟩⟨1|⟨1|0⟩ − |1⟩⟨0|⟨0|1⟩ + |1⟩⟨1|⟨1|1⟩

( |00⟩⟨00|) − tr

( |00⟩⟨11|) − tr

( |11⟩⟨00|) + tr

( |11⟩⟨11|)

⟨0|0⟩|0⟩⟨0| + ⟨1|0⟩|0⟩⟨1| + ⟨0|1⟩|1⟩⟨0| + ⟨1|1⟩|1⟩⟨1|

For |B

⟩, we have:

ρ =



|01⟩ + |10⟩

√



⟨01| + ⟨10|

√



|01⟩⟨01| + |01⟩⟨10| + |10⟩⟨01| + |10⟩⟨10|

( |01⟩⟨01|) + tr

( |01⟩⟨10|) + tr

( |10⟩⟨01|) + tr

( |10⟩⟨10|)

|0⟩⟨0|⟨1|+⟩|0⟩⟨1|⟨0|1⟩ + |1⟩⟨0|⟨1|0⟩ + |1⟩⟨1|⟨0|0⟩

( |01⟩⟨01|) + tr

( |01⟩⟨10|) + tr

( |10⟩⟨01|) + tr

( |10⟩⟨10|)

⟨0|0⟩|1⟩⟨1| + ⟨1|0⟩|1⟩⟨0| + ⟨0|1⟩|0⟩⟨1| + ⟨1|1⟩|1⟩⟨1|

Finally, for |B

⟩ we have:

ρ =



|01⟩ − |10⟩

√



⟨01| − ⟨10|

√



|01⟩⟨01| − |01⟩⟨10| − |10⟩⟨01| + |10⟩⟨10|

( |01⟩⟨01|) − tr

( |01⟩⟨10|) − tr

( |10⟩⟨01|) + tr

( |10⟩⟨10|)

|0⟩⟨0|⟨1|−⟩|0⟩⟨1|⟨0|1⟩ − |1⟩⟨0|⟨1|0⟩ + |1⟩⟨1|⟨0|0⟩

( |01⟩⟨01|) − tr

( |01⟩⟨10|) − tr

( |10⟩⟨01|) + tr

( |10⟩⟨10|)

⟨0|0⟩|1⟩⟨1| − ⟨1|0⟩|1⟩⟨0| − ⟨0|1⟩|0⟩⟨1| + ⟨1|1⟩|1⟩⟨1|

Exercise 2.76

Extend the proof of the Schmidt decomposition to the case where A and B may have state space of

diﬀerent dimensionality.

Solution

Concepts Involved: Schmidt Decomposition, Singular Value Decomposition.

Note that for this problem we will use a more general form of the Singular Value Decomposition than

proven in Nielsen and Chuang (that may have been encountered in a linear algebra course). Given an

arbitrary m × n rectangular matrix A, there exists an m × m unitary matrix U and n × n unitary matrix

V such that A = UΣV where Σ is a m × n rectangular diagonal matrix with non-negative reals on the

diagonal (see https://en.wikipedia.org/wiki/Singular_value_decomposition).

Let |m⟩, |n⟩ be orthonormal bases for A and B. We can then write:

A =

|m⟩|n⟩

for some m × n matrix of complex numbers a. Using the generalized SVD, we can write:

A =

min

|m⟩|n⟩

where d

is a rectangular diagonal matrix. We can then deﬁne |i

⟩ =

|m⟩, |i

⟩ =

|n⟩,

and λ

= d

to yield the Schmidt decomposition. Note that we take i = min(m, n) and our sum only

has as many terms as the dimensionality of the smaller space.

Exercise 2.77

(∗) Suppose ABC is a three component quantum system. Show by example that there are quantum

states |ψ⟩ of such systems which can not be written in the form

|ψ⟩ =

⟩|i

⟩

where λ

are real numbers, and |i

⟩, |i

⟩ are orthonormal bases of the respective systems.

Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition.

Consider the state:

|ψ⟩ = |0⟩ ⊗ |B

⟩ =

|000⟩ + |011⟩

√

we claim that this state cannot be written in the form:

|ψ⟩ =

⟩|i

⟩

for orthonormal bases |i

⟩, |i

⟩. Suppose for the sake of contradiction that we could write it in this

form. We then make the observation that:

= tr

( |ψ⟩⟨ψ|) =

⟩⟨i

= tr

( |ψ⟩⟨ψ|) =

⟩⟨i

= tr

( |ψ⟩⟨ψ|) =

⟩⟨i

From this, we conclude that if it is possible to write |ψ⟩ in such a form, then the eigenvalues of the reduced

density matrices must all agree and be equal to λ

. Computing the density matrix of the proposted

|ψ⟩ = |0⟩ ⊗ |B

⟩, we have:

ρ =

|000⟩⟨000| + |000⟩⟨011| + |011⟩⟨000| + |011⟩⟨011|

Computing the reduced density matrices ρ

and ρ

, we ﬁnd that:

= tr

(ρ) = |0⟩⟨0|

= tr

(ρ) =

|0⟩⟨0| + |1⟩⟨1|

However, the former reduced density matrix has eigenvalues λ

= 1, λ

= 0, and the latter has λ

. This contradicts the fact that the λ

s must match.

Remark: Necessary and Suﬃcient conditions for the tripartite (and higher order) Schmidt decompositions

can be found here https://arxiv.org/pdf/quant-ph/9504006.pdf.

Exercise 2.78

Prove that a state |ψ⟩ of a composite system AB is a product state if and only if it has a Schmidt number

1. Prove that |ψ⟩ is a product state if and only if ρ

(and thus ρ

) are pure states.

Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition, Schmidt Number, Reduced Density Oper-

ators.

Suppose |ψ⟩ is a product state. Then, |ψ⟩ = |0

⟩|0

⟩ for some |0

⟩, |0

⟩, and we therefore have that

|ψ⟩ has Schmidt number 1 (it is already written in Schmidt decomposition form, and has one nonzero λ).

Conversely, suppose |ψ⟩ has Schmidt number 1. Then, |ψ⟩ = 1|0

⟩|0

⟩+ 0|1

⟩|1

⟩ when writing |ψ⟩ in

its Schmidt decomposition. Therefore, |ψ⟩ = |i

⟩|i

⟩ and |ψ⟩ is a product state.

Next, take any |ψ⟩ and write out its Schmidt decomposition. We then get:

|ψ⟩ =

⟩|i

⟩.

Hence:

ρ =

⟩⟨i

| ⊗ |i

⟩⟨i

Taking the partial trace of ρ to obtain ρ

, we have:

= tr

(ρ) =

( |i

⟩⟨i

| ⊗ |i

⟩⟨i

|) =

⟩⟨i

|tr



⟩⟨i



⟩⟨i

Identically:

= tr

(ρ) =

⟩⟨i

Now, suppose that |ψ⟩ is a product state. Then, |ψ⟩ has Schmidt number 1. Hence, only one of λ

, λ

nonzero. Hence, ρ

= |i

⟩⟨i

| and ρ

= |i

⟩⟨i

|, so ρ

, ρ

are pure. Conversely, suppose ρ

, ρ

are

pure. Then, we have that ρ

= |i

⟩⟨i

| and ρ

= |i

⟩⟨i

|, so it follows that one of λ

, λ

in the above

equations for ρ

, ρ

must be zero. Therefore, |ψ⟩ has Schmidt number 1, and is hence a product state.

Exercise 2.79

Consider a composite system consisting of two qubits. Find the Schmidt decomposition of the states

|00⟩ + |11⟩

√

;

|00⟩ + |01⟩ + |10⟩ + |11⟩

; and

|00⟩ + |01⟩ + |10⟩

√

Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition, Reduced Density Matrices, Partial Trace.

For the ﬁrst two expressions, by inspection we ﬁnd that:

|00⟩ + |11⟩

√

|0⟩|0⟩ +

√

|1⟩|1⟩

|00⟩ + |01⟩ + |10⟩ + |11⟩

= 1|+⟩|+⟩ + 0|−⟩|−⟩

For the third expression, we require a little more work. We ﬁrst note that the existence of the

Schmidt decomposition guarantees that the state |ψ⟩ =

|00⟩+|01⟩+|10⟩

√

can be written in the form

|ψ⟩ =

i=1

⟩|i

⟩ for some choice of orthonormal bases |i

⟩, |i

⟩. By the deﬁnition of reduced

density matrices/partial trace, we can make the observation that:

= tr

(ρ) = tr

( |ψ⟩⟨ψ|) =

i=1

⟩⟨i

|tr

( |i

⟩⟨i

|) =

i=1

⟩⟨i

and similarly that ρ

i=1

⟩⟨i

|. Hence, to ﬁnd the Schmidt decomposition of |ψ⟩, we can

compute the reduced density matrices and then solve for their eigenvalues λ

and eigenvectors |i⟩. First

solving for ρ, we have:

ρ =

|00⟩⟨00| + |00⟩⟨01| + |00⟩⟨10| + |01⟩⟨00| + |01⟩⟨01| + |01⟩⟨10| + |10⟩⟨00| + |10⟩⟨01| + |10⟩⟨10|

Solving for the reduced density matrix ρ

we have:

= tr

(ρ) =

2 |0⟩⟨0| + |0⟩⟨1| + |1⟩⟨0| + |1⟩⟨1|

∼

2 1

1 1

Solving for the eigenvalues and (normalized) eigenvectors, we have:

3 +

√

, |1

⟩ =

10 + 2

√



(1 +

√

5)|0⟩ + 2|1⟩



3 −

√

, |2

⟩ =

10 − 2

√



(1 −

√

5)|0⟩ + 2|1⟩



Next solving for the reduced density matrix ρ

, we have:

= tr

(ρ) =

2 |0⟩⟨0| + |0⟩⟨1| + |1⟩⟨0| + |1⟩⟨1|

∼

2 1

1 1

This (of course) has the same eigenvectors and eigenvalues:

3 +

√

, |1

⟩ =

10 + 2

√



(1 +

√

5)|0⟩ + 2|1⟩



3 −

√

, |2

⟩ =

10 − 2

√



(1 −

√

5)|0⟩ + 2|1⟩



Hence the Schmidt decomposition of |ψ⟩ is given by:

|ψ⟩ = λ

⟩|1

⟩ + λ

⟩|2

⟩

where the expressions for the eigenvalues/eigenvectors are given above.

Exercise 2.80

Suppose |ψ⟩ and |φ⟩ are two pure states of a composite quantum system with components A and B, with

identical Schmidt coeﬃcients. Show that there are unitary transformations U on a system A and V on

system B such that |ψ⟩ = (U ⊗ V )|φ⟩.

Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition, Unitary Operators.

We ﬁrst prove a Lemma. Suppose we have two (orthonormal) bases



|i⟩





′

⟩



of a (n-dimensional)

vector space A. We claim that the change of basis transformation U where |i

′

⟩ = U|i⟩ is unitary.

To see this is the case, let U =

′

⟩⟨i|. By orthonormality, we see that U|i⟩ = |i

′

⟩ as desired.

Computing U

†

, we have that U

†

( |i

′

⟩⟨i|)

†





′



. By orthonormality, we then see that

†

U =

|i⟩⟨i| = I and hence U is unitary.

We now move onto the actual problem. By assumption, we can write |ψ⟩ =

⟩|i

⟩ and |φ⟩ =

⟩|j

⟩ where λ

= λ

if i = j. By the lemma, there exists unitary change-of-basis matrices U, V

such that |i

⟩ = U|j

⟩ and |i

⟩ = V |j

⟩. Hence, we have that:

|ψ⟩ =

⟩|i

⟩ =

(U|j

⟩)(V |j

⟩) = (U ⊗ V )

⟩|j

⟩ = (U ⊗ V )|φ⟩

which is what we wanted to prove.

Exercise 2.81: Freedom in puriﬁcations

Let |AR

⟩ and |AR

⟩ be two puriﬁcations of a state ρ

to a composite system AR. Prove that there

exists a unitary transformation U

acting on system R such that |AR

⟩ = (I

⊗ U

)|AR

⟩.

Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition, Puriﬁcation, Unitary Operators

Let |AR

⟩, |AR

⟩ be two puriﬁcations of ρ

to a composite system AR. We can write the orthonormal

decomposition of ρ

as ρ

⟩⟨i

|, from which it follows that we can write:

|AR

⟩ =

√

⟩|i

⟩

|AR

⟩ =

√

⟩|i

′R

⟩

for some bases



|i⟩





′

⟩



of R. By the Lemma proven in the previous exercise, the transformation U

such that |i⟩ = U

′

⟩ is unitary, so hence:

|AR

⟩ =

√

⟩|i

⟩ =

√

⟩(U

′R

⟩) =

√

⟩)(U

′R

⟩)

= (I

⊗ U

)

√

⟩|i

′R

⟩

= (I

⊗ U

)|AR

⟩

which proves the claim.

Exercise 2.82

Suppose



, |ψ

⟩



is an ensemble of states generating a density matrix ρ =

|ψ

⟩⟨ψ

| for a quantum

system A. Introduce a system R with orthonormal basis |i⟩.

(1) Show that

√

|ψ

⟩|i⟩ is a puriﬁcation of ρ.

(2) Suppose we measure R in the basis |i⟩, obtained outcome i. With what probability do we obtain

the result i, and what is the corresponding state of system A?

(3) Let |AR⟩ be any puriﬁcation of ρ to the system AR. Show that there exists an orthonormal basis

|i⟩ in which R can be measured such that the corresponding post-measurement state for system A

is |ψ

⟩ with probability p

Solution

Concepts Involved: Linear Algebra, Puriﬁcation, Schmidt Decomposition.

(1) To verify that

√

|ψ

⟩|i⟩ is a puriﬁcation, we see that:











√

|ψ

⟩|i⟩









√

⟨ψ

|⟨j|











√

|ψ

⟩⟨ψ

|tr

(|i⟩⟨j|)

√

|ψ

⟩⟨ψ

|δ

|ψ

⟩⟨ψ

|ψ

⟩⟨ψ

= ρ

(2) We measure the observable M

= I

⊗

= I

⊗

|i⟩⟨i|. The probability of obtaining outcome

i is given by p(i) = ⟨AR|(I

⊗P

)|AR⟩ (where |AR⟩ =

√

|ψ

⟩|i⟩), which we can calculate to

be:

p(i) = ⟨AR|(I

⊗ |i⟩⟨i|)|AR⟩





√

⟨ψ

|⟨j|





⊗ |i⟩⟨i|)





√

|ψ

⟩|k⟩





√

⟨ψ

|ψ

⟩δ

= p

The post measurement state is given by:

⊗ P

)|AR⟩

p(i)

⊗ |i⟩⟨i|)

√

|ψ

⟩|j⟩

√

|ψ

⟩|j⟩δ

√

|ψ

⟩|i⟩

√

= |ψ

⟩|i⟩

so the corresponding state of system A is |ψ

⟩.

(3) Let |AR⟩ be any puriﬁcation of ρ to the combined system AR. We then have that |AR⟩ has Schmidt

Decomposition:

|AR⟩ =

⟩|i

⟩

for orthonormal bases |i

⟩, |i

⟩ of A and R respectively. Deﬁne a linear transformation U such that

⟩ =

|ψ

⟩. We then have that:

|AR⟩ =





|ψ

⟩





⟩ =

|ψ

⟩

⟩.

We note that we can move the U

to system R as R has the same state space as A by construction.

Letting |j⟩ =

⟩ be our orthonormal basis of R, the claim follows (by part (2) of the

question.

Problem 2.1: Functions of the Pauli matrices

Let f(·) be any function from complex numbers to complex numbers. Let n be a normalized vector in

three dimensions, and let θ be real. Show

f(θn · σ) =

f(θ) + f(−θ)

I +

f(θ) − f(−θ)

n · σ

Solution

Concepts Involved: Linear Algebra, Spectral Decomposition, Operator Functions.

From Exercise 2.35, we recall that n · σ has spectral decomposition n · σ = |n

⟩⟨n

| − |n

−

⟩⟨n

−

|. We

then have that (by the deﬁnition of operator functions):

f(θn · σ) = f



θ( |n

⟩⟨n

| − |n

−

⟩⟨n

−



= f(θ) |n

⟩⟨n

| + f(−θ) |n

−

⟩⟨n

−

We then use the fact proven in the solution to Exercise 2.60 that we can write the projectors P

= |n

⟩⟨n

in terms of the operator n · σ as:

⟩⟨n

| =

I ± n · σ

Hence making this substitution we have:

f(θn · σ) = f(θ)



I + n · σ



+ f(−θ)



I − n · σ



Grouping terms, we obtain the desired relation:

f(θn · σ) =

f(θ) + f(−θ)

I +

f(θ) − f(−θ)

n · σ.

Remark:

Arguably, the most used application of the above identity in quantum information is when f(θn · σ) =

exp



i(θ/2)n · σ



. In this case (as in Exercise 2.35), we have

exp



i(θ/2)n · σ



exp



θ/2



+ exp



−θ/2



I +

exp



θ/2



− exp



−θ/2



n · σ

= cos





I + i sin





n · σ .

Problem 2.2: Properties of Schmidt numbers

Suppose |ψ⟩ is a pure state of a composite system with components A and B.

(1) Prove that the Schmidt number of |ψ⟩ is equal to the rank of the reduced density matrix ρ

≡

(|ψ⟩⟨ψ|). (Note that the rank of a Hermitian operator is equal to the dimension of its support.)

(2) Suppose |ψ⟩ =

|α

⟩|β

⟩ is a representation for |ψ⟩, where |α

⟩ and |β

⟩ are (un-normalized)

states for systems A and B, respectively. Prove that the number of terms in a such a decomposition

is greater than or equal to the Schmidt number of |ψ⟩, Sch(ψ).

(3) Suppose |ψ⟩ = α|φ⟩ + β|γ⟩. Prove that

Sch(ψ) ≥



Sch(φ) − Sch(γ)



Solution

Concepts Involved: Linear Algebra, Schmidt Decomposition, Schmidt Number, Reduced Density Oper-

ators.

(1) We write the Schmidt decomposed |ψ⟩, and therefore the density matrix ρ

as:

|ψ⟩ =

⟩|i

⟩ =⇒ |ψ⟩⟨ψ| =

′

⟩⟨i

| ⊗ |i

⟩⟨i

Taking the partial trace of subsystem B in the |i

⟩ basis, we obtain the reduced density matrix ρ

to be:

= tr

(|ψ⟩⟨ψ|) =

⟩⟨i

Sch(ψ) of the λ

s are nonzero, and therefore ρ

has Sch(ψ) nonzero eigenvalues - therefore the

rank of its support is Sch(ψ).

(2) Suppose for the sake of contradiction that some decomposition |ψ⟩ =

j=1









had less terms

than the Schmidt decomposition of |ψ⟩, i.e. N < Sch(ψ).

The density matrix of |ψ⟩ is:

= |ψ⟩⟨ψ| =

j=1,k=1







⊗







(1)

Tracing out subsystem B, we obtain the reduced density matrix of subsystem A:

= Tr

(ρ

) =

j=1,k=1













(2)

where we have used that Tr



|β

⟩⟨β



= ⟨β

|β

⟩. From the above, it is clear that ρ

has rank at

most N , as the support of ρ

is spanned by



|α

⟩, . . . , |α

⟩



. But then the rank of ρ

is less than

Sch(ψ), which contradicts our ﬁnding in part (a).

(3) If Sch(φ) = Sch(γ) then there is nothing to prove as Sch(ψ) is non-negative by deﬁnition. Suppose

then that Sch(φ) ̸= Sch(γ). WLOG suppose Sch(φ) > Sch(γ). We can then write:

|φ⟩ =

|γ⟩ −

|ψ⟩

If we Schmidt decompose |φ⟩ and |ψ⟩, we have written |φ⟩ as the sum of Sch(γ) + Sch(ψ) (unnor-

malized) bipartite states. Applying the result from part (2) of this problem, we then have that:

Sch(φ) ≤ Sch(γ) + Sch(ψ)

which we rearrange to obtain:

Sch(ψ) ≥ Sch(φ) − Sch(γ) =



Sch(φ) − Sch(γ)



which proves the claim.

Problem 2.3: Tsirelson’s inequality

Suppose Q = q · σ, R = r · σ, S = s · σ, T = t · σ, where q, r, s, and t are real unit vectors in three

dimensions. Show that

(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )

= 4I + [Q, R] ⊗ [S, T ]

Use this result to prove that

⟨Q ⊗ S⟩ + ⟨R ⊗ S⟩ + ⟨R ⊗ T ⟩ − ⟨Q ⊗ T ⟩ ≤ 2

√

so the violation of the Bell inequality found in Equation (2.230) is the maximum possible in quantum

mechanics.

Solution

Concepts Involved: Tensor Products, Commutators

We ﬁrst show that N

= I for any N = n ·σ where n is a unit vector in three dimensions. We have that:

= (

i=1

)

= n

+ n

(σ

+ σ

) + n

n3(σ

+ σ

) + n

(σ

+ σ

)

By Exercise 2.41, σ

= I and



, σ



= 0 for i ̸= j, so the above reduces to:

= n

I + n

I = (n

+ n

)I = I

where we use the fact that n is of unit length. Using this fact, we have that:

(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )

= Q

⊗ S

+ QR ⊗ S

+ QR ⊗ ST − Q

⊗ ST

+ RQ ⊗ S

+ R

⊗ S

+ R

⊗ ST − RQ ⊗ ST

+ RQ ⊗ T S + R

⊗ T S + R

⊗ T

− RQ ⊗ T

− Q

⊗ T S − QR ⊗ T S − QR ⊗ T

+ Q

⊗ T

= I ⊗ I + QR ⊗ I + QR ⊗ ST − I ⊗ ST

+ RQ ⊗ I + I ⊗ I + I ⊗ ST − RQ ⊗ ST

+ RQ ⊗ T S + I ⊗ T S + I ⊗ I − RQ ⊗ I

− I ⊗ T S − QR ⊗ T S − QR ⊗ I + I ⊗ I

= 4I ⊗ I + RQ ⊗ T S − RQ ⊗ ST + QR ⊗ ST − QR ⊗ T S

= 4I + QR ⊗ (ST − T S) − RQ ⊗ (ST − T S)

= 4I + [Q, R] ⊗ [S, T ]

which proves the ﬁrst equation. We have that ⟨4I⟩ = 4 ⟨I⟩ = 4. Since each of Q, R, S, T have eigenvalues

±1 (Exercise 2.35), we also ave that



[Q, R] ⊗ [S, T ]



≤ 4 as the tensor product of commutators consists

of 4 terms, each of which has expectation less than or equal to 1. We therefore have by the linearity of

expectation (Exercise A1.4) that:

(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )



4I + [QR] ⊗ [S, T ]



≤ 8.

Furthermore, we have that:



(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )



≤

(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )

so combining the two inequalities we obtain:



(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )



≤ 8.

Taking square roots on both sides, we have:



(Q ⊗ S + R ⊗ S + R ⊗ T − Q ⊗ T )



≤ 2

√

and again by the linearity of expectation:

⟨Q ⊗ S⟩ + ⟨R ⊗ S⟩ + ⟨R ⊗ T ⟩ − ⟨Q ⊗ T ⟩ ≤ 2

√

which is the desired inequality.

3 Introduction to computer science

Exercise 3.1: Non-computable processes in Nature

How might we recognize that a process in Nature computes a function not computable by a Turing

machine?

Solution

Concepts Involved: Turing Machines.

One criteria is natural phenomena that appear to be truly random; Turing machines as deﬁned in the text

are deterministic (though there are probabilistic variations that would solve this issue) and hence would

not be able to compute a random function. From a more direct point, if a process in Nature was to

be found to compute a known non-computable problem (e.g. solve the Halting problem or the Tiling

problem) then we may conclude (trivially) that the process would not be computable. However since the

domain of inputs that we could provide top such a natural process would have to be ﬁnite, there would be

no concrete method in which one could actually test if such a process was truly computing a non-Turing

computable function (as a Turing machine that works on a ﬁnite subset of inputs for an uncomputable

problem could be devised).

Exercise 3.2: Turing numbers

(∗) Show that single-tape Turing machines can each be given a number from the list 1, 2, 3, . . . in such a way

that the number uniquely speciﬁes the corresponding machine. We call this number the Turing number

of the corresponding Turing machine. (Hint: Every positive integer has a unique prime factorization

. . . p

, where p

are distinct prime numbers, and a

, . . . a

are non-negative integers.)

Solution

Concepts Involved: Turing Machines, Cardinality.

Lemma 1. If {A

}

∞

n=1

is a sequence of sets that are countably inﬁnite (that is, they can be put in bijection

with the natural numbers N) then their union A =

∞

n=1

is also countably inﬁnite.

Proof. Write A

= {x

, x

, . . .} (which we can do as each of the A

s are countably inﬁnite).

Then, we form an array:

= x

···

= x

···

= x

···

Then, we can re-number the elements along the diagonal lines (i.e. x

, x

, . . .). This

new enumeration corresponds to a countably inﬁnite set. From there, we let T ⊂ N be the remaining

labels in the enumeration after removing the repeated elements from the sequence. Then, |T | = |A|, and

hence A is at most countably inﬁnite. A cannot be ﬁnite as A

⊂ A and A

is not ﬁnite. Hence A is

countably inﬁnite.

Lemma 2. The set of all ﬁnite sequences of elements from a countably inﬁnite set B is also countably

inﬁnite.

Proof. Denote B

the set of length n sequences consisting of elements from B. We show that B

countably inﬁnite by induction.

Base Case: |B| = |B

|, so B

is countably inﬁnite.

Inductive Step: Suppose that B

is countably inﬁnite for k ≥ 1. Then, deﬁne B

k,i

which is the set of

k + 1 length sequences, consisting of all sequences in B

and then terminating with the ith element of B.



k,i



= |B

| so B

k,i

is countably inﬁnite, and then B

k+1

∞

i=1

k,i

is countably inﬁnite by Lemma 1.

This concludes the argument by induction.

Finally, the set of all ﬁnite sequences of elements from B is simply

∞

k=1

, which is a union of countably

inﬁnite sets and therefore countably inﬁnite again by Lemma ‘.

Solution. A single-tape Turing machine can be uniquely speciﬁed by a ﬁnite integer sequence as follows.

First, we state the number of states |Q| = N, then enumerate the states q

= −1, q

= 0, q

1, . . . , q

N−2

= N − 2. We then state the size of the alphabet |Γ| = L and enumerate the alphabet

▷ = −2, b = −1, 0 = 0, 1 = 1, . . . , L − 3 = L − 3. We then write the sequence of symbols appearing on

the initial tape, starting from square 0, stopping when we encounter the last non-blank symbol. Finally, we

list the program lines, each of which is a ﬁve-tuple of integers (as each of the states and symbols appearing

in the program line we have associated to an integer, and the action s is one of −1, 0, 1). Between each

part of this sequence we put a “space integer” -3.

As an example, the Turing machine in the text which computes the constant function (and let us say for

the sake of example the tape starts with the number 7 on it, so 110 in binary followed by inﬁnite blanks)

has the associated ﬁnite integer sequence:

|{z}

|Q|

, −1

|{z}

, 0

|{z}

, 1

|{z}

, 2

|{z}

, 3

|{z}

, −3, 4

|{z}

|Σ|

, −2

|{z}

▷

, −1

|{z}

, 0, 1, −3, 1, 1, 0

|{z}

, −3, −1, −2, 1, −2, 1

| {z }

⟨q

,▷,q

,▷,+1⟩

1, 0, 1, −1, 1

| {z }

⟨q

,0,q

,b,+1⟩

, 1, 1, 1, −1, 1

| {z }

⟨q

,1,q

,b,+1⟩

, 1, −1, 2, −1, −1

| {z }

⟨q

,b,q

,b,−1⟩

, 2, −1, 2, −1, −1

| {z }

⟨q

,b,q

,b,−1⟩

, 2, −2, 3, −2, 1

| {z }

⟨q

,▷,q

,▷,+1⟩

, 3, −1, 0, 1, 0

| {z }

⟨q

,b,q

,1,0⟩

Because the number of states is ﬁnite, the size of the alphabet is ﬁnite, the number of non-blank squares

on the initial tape is ﬁnite, and there is a ﬁnite number of lines in the program, the above algorithm

produces a ﬁnite sequence of integers for a given Turing machine.

Now, observe that the integers are countably inﬁnite, as:

N −→ Z

n 7−→







n even

−

n−1

n odd

(3)

is a bijection. So too then is the set of all ﬁnite integer sequences by the Lemma 2. Since the ﬁnite

integer sequences describing Turing machines as produced by the above prescription are a subset of all

ﬁnite integer sequences, we must therefore be able to associate any single-tape Turing machine to a unique

natural number, as claimed.

Exercise 3.3: Turing machine to reverse a bit string

Describe a Turing machine which takes a binary number x as input, and outputs the bits of x in reverse

order. (Hint: In this exercise and the next it may help to use a multi-tape Turing machine and/or symbols

other than ▷, 0, 1 and the blank.)

Exercise 3.4: Turing machine to add modulo 2

Describe a Turing machine to add two binary numbers x and y modulo 2. The numbers are input on the

Turing machine tape in binary, in the form x, followed by a single blank, followed by a y. If one number

is not as long as the other then you may assume that it has been padded with leading 0s to make the two

numbers the same length.

Exercise 3.5: Halting problem with no inputs

Show that given a Turing machine M there is no algorithm to determine whether M halts when the input

to the machine is a blank tape.

Exercise 3.6: Probabilistic halting problem

Suppose we number the probabilistic Turing machines using a scheme similar to that found in Exercise 3.2

and deﬁne the probabilistic halting function h

(x) to be 1 if machine x halts on input of x with probability

at least 1/2 and 0 if machine x halts on input of x with probability less than 1/2. Show that there is no

probabilistic Turing machine which can output h

(x) with probability of correctness strictly greater than

1/2 for all x.

Exercise 3.7: Halting oracle

Suppose a black box is made available to us which takes a non-negative integer x as input, and then

outputs the value of h(x), where h(·) is the halting function deﬁned in Box 3.2 on page 130. This type

of black box is sometimes known as an oracle for the halting problem. Suppose we have a regular Turing

machine which is augmented by the power to call the oracle. One way of accomplishing this is to use a

two-tape Turing machine, and add an extra program instruction to the Turing machine which results in the

oracle being called, and the value of h(x) being printed on the second tape, where x is the current contents

of the second tape. It is clear that this model for computation is more powerful than the conventional

Turing machine model, since it can be used to compute the halting function. Is the halting problem for

this model of computation undecidable? That is, can a Turing machine aided by an oracle for the halting

problem decide whether a program for the Turing machine with oracle will halt on a particular input?

Exercise 3.8: Universality of NAND

Show that the NAND gate can be used to simulate the AND, XOR, and NOT gates, provides wires, ancilla bits

and FANOUT are available.

Solution

Concepts Involved: Logic Gates.

We start by showing how we can get a 1 qubit using two 0 ancilla bits and a NAND gate.

We will now show how to simulate the NOT, AND, and XOR gates. We note that we will use “1” to denote

as shorthand a 1 bit constructed using two ancilla bits (as above). a/b represent the input bits. We start

with the NOT gate.

¬a

Next, we simulate the AND gate.

a ∧ b

For the XOR simulated gate, we note that we ﬁrst use FANOUT twice to copy both input bits.

a ⊕ b

Having simulated the three gates using the NAND gate only, we conclude that the NAND is universal.

Exercise 3.9

Prove that f (n) is O(g(n)) if and only if g(n) is Ω(f(n)). Deduce that f (n) is Θ(g(n)) if and only if

g(n) is Θ(f(n)).

Solution

Concepts Involved: Asymptotic Notation.

Suppose f(n) is O(g(n)). Then, there exists c > 0 such that for all n > n

, f(n) ≤ cg(n). Therefore,

we have

> 0 such that for all n > n

f(n) ≤ g(n). Hence, g(n) is Ω(f(n)). Conversely, if g(n) is

Ω(f(n)), there exists c > 0 such that for all n > n

, cf(n) ≤ g(n). Hence, we have

> 0 such that for

all n > n

, f(n) ≤

g(n) and hence f(n) is O(g(n)).

Therefore, if f(n) is Θ(g(n)) then f (n) is O(g(n)) and Ω(g(n)), and by the above argument, g(n) is

O(f(n)) and Ω(f(n)) and hence g(n) is Θ(f(n)). The converse holds in the same way.

Exercise 3.10

Suppose g(n) is a polynomial of degree k. Show that g(n) is O(n

) for any l ≥ k.

Solution

Concepts Involved: Asymptotic Notation.

By assumption, g(n) = a

+ a

+ . . . + a

with a

̸= 0. For n ≥ 1 we have that n

≥ n

l ≥ k, and hence if l ≥ k we have that a

≥ a

for all i ∈ {0, . . . , k}. Therefore, we have that:

+ a

+ . . . + a

≥ a

+ a

+ . . . + a

= g(n)

for n ≥ 1 and hence g(n) is O(n

Exercise 3.11

Show that log n is O(n

) for any k > 0.

Solution

Concepts Involved: Asymptotic Notation.

Let k > 0 and c > 0. By the deﬁnition of the exponential we have that:

exp





∞

j=0

(an

)

∞

j=0

now, there exists some j

∈ Z for which kj

> 1. Since for n ≥ 0 the terms in the above sum are

non-negative, we ﬁnd:

exp





≥

Now, choose c suﬃciently large such that c

≥ j

!. We then ﬁnd that:

exp





≥

≥ n

Then for n ≥ 1 it follows that n

≥ n as kj

≥ 1 and so:

exp





≥ n

Since the logarithm is monotonic, we may take the log of both sides and preserve the inequality:

≥ log n

So we have shown that for any k > 0, there exists c > 0 such that for all n > 1, cn

≥ log n. Hence,

log n is O(n

) for any k > 0.

Exercise 3.12: n

log n

is super-polynomial

Show that n

is O(n

logn

) for any k, but that n

log n

is never O(n

Solution

Concepts Involved: Asymptotic Notation.

First, note that for any k, e

≤ n for suﬃciently large n > n

and so k ≤ log n by monotonicity of the

logarithm. Therefore, for n > n

it follows by monotonicity (of exponentiation) that n

≤ n

log n

and so

is O(n

log n

Now, consider an arbitrary a > 0. It still follows for suﬃciently large n > n

that e

≤ n and so

ak ≤ log n and n

≤ n

log n

. But for any c > 0 n

> c for suﬃciently large n and so:

≤ n

log n

So since for any c > 0 there exists some n

′

for which n > n

′

implies cn

≤ n

log n

, it follows that n

log n

is never O(n

Exercise 3.13: n

log n

is sub-exponential

Show that c

is Ω(n

log n

) for any c > 1, but that n

log n

is never Ω(c

Solution

Concepts Involved: Asymptotic Notation.

First note from Exercise 1.11 that log n is O(n

) for any k > 0. Speciﬁcally, take k = 1/2; then there

exists a > 0 such that for n > n

1/2

≥ log n

and therefore squaring both sides:

n ≥ log n log n = log n

log n

Now for any c > 1, we can deﬁne a

′

log c

> 0 and write:

′

log c = log c

′

≥ log n

log n

Exponentiating both sides preserves the inequality, and so:

′

= c

′

≥ n

log n

and so there exists a constant

′

> 0 such that for n > n

, c

≥

′

log n

and therefore c

is Ω(n

log n

Now, let b > 0 be some arbitrarily small constant. For suﬃciently large n, we have that na

′

logc+log b > 0

and so for suﬃciently large n it further follows that:

log b + na

′

log c = log



′



≥ log n

log n

where a

′

is deﬁned as it was previously. Therefore exponentiating both sides:

′

= bc

′

≥ n

log n

so for suﬃciently large n, for any arbitrarily small constant b

′

it follows that b

′

≥ n

log n

and so n

log n

never Ω(c

Exercise 3.14

Suppose e(n) is O(f(n)) and g(n) is O(h(n)). Show that e(n)g(n) is O(f(n)h(n)).

Solution

Concepts Involved: Asymptotic Notation.

By assumption, we have that e(n) ≤ c

f(n) for some c

> 0 and for all n > n

and that g(n) ≤ c

h(n)

for some c

> 0 and for all n > n

. Let n

= max n

, n

. We then have that for n > n

that:

e(n)g(n) ≤ c

f(n)c

h(n) = (c

)(f(n)h(n))

so therefore e(n)g(n) is O(f(n)h(n)).

Exercise 3.15: Lower bound for compare-and-swap based sorts

Suppose an n element list is sorted by applying some sequence of compare-and-swap operations to the list.

There are n! possible initial orderings of the list. Show that after k of the compare-and-swap operations

have been applied, at most 2

of the possible initial orderings will have been sorted into the correct order.

Conclude that Ω(n log n) compare and swap operations are required to sort all possible initial orderings

into the correct order.

Solution

Concepts Involved: Asymptotic Notation, Compare-and-Swap.

We prove the ﬁrst statement by induction. After 0 steps, we have that 1 = 2

out of the n! possible

orderings are already sorted. Let k ∈ N, k ≥ 0 and suppose that after k swaps, at most 2

of the initial

orderings have been sorted into the correct order. We now consider the state of the list after the k + 1th

swap. Each of the 2

initial orderings from the previous step are correctly sorted already (so the swap does

nothing), and there are a further 2

initial orderings that are one swap away from the 2

from the previous

step, and hence the k + 1th swap will put 2

more initial orderings into the correct order. Therefore, after

k+1

compare and swaps, there are at most 2

+ 2

= 2

k+1

possible initial orderings that are sorted into

the correct order. This proves the claim.

Using the above fact, we have that in order to have all n! possible initial orderings correct after k

steps that 2

≥ n!. Taking logarithms on both sides, we have that log





≥ log(n!) and hence k ≥

log(n!). Using Stirling’s approximation for factorials (https://en.wikipedia.org/wiki/Stirling%

27s_approximation), we have that:

k ≥ n log n − n log e + O(log n)

from which we conclude that k is Ω(n log n) and hence Ω(n log n) compare and swap operations are

required to sort all possible initial orderings into the correct order.

Exercise 3.16: Hard-to-compute functions exist

Show there exist Boolean functions on n inputs which require at least 2

/ log n logic gates to compute.

Exercise 3.17

Prove that a polynomial-time algorithm for ﬁnding the factors of a number m exists if and ony if the

factoring decision problem is in P.

Exercise 3.18

Prove that if coNP ̸= NP then P ̸= NP.

Exercise 3.19

The Reachability problem is to determine whether there is a path between two speciﬁed vertices in a

graph. Show that Reachability can be solved using O(n) operations if the graph has n vertices. Use

the solution to Reachability to show that it is possible to decide whether a graph is connected in O(n

)

operations.

Exercise 3.20: Euler’s theorem

Prove Euler’s theorem. In particular, if each vertex has an even number of incident edges, give a construc-

tive procedure for ﬁnding an Euler cycle.

Exercise 3.21: Transitive property of reduction

Show that if a language L

is reducible to the language L

and the language L

is reducible to L

then

the language L

is reducible to the language L

Exercise 3.22

Suppose L is complete for a complexity class, and L

′

is another language in the complexity class such

that L reduces to L

′

. Show that L

′

is complete for the complexity class.

Exercise 3.23

Show that SAT is NP-complete by ﬁrst showing that the SAT is in NP, and then showing that CSAT

reduces to SAT.

Exercise 3.24: 2SAT has an eﬃcient solution

Suppose φ is a Boolean formula in conjunctive normal form, in which each clause contains only two literals.

(1) Construct a (directed) graph G(φ) with directed edges in the following way: the vertices of G

correspond to variables x

and their negations ¬x

in φ. There is a (directed) edge (α, β) in G if

and only if the clause (¬α ∨β) or the clause (β ∧¬α) is present in φ. Show that φ is not satisﬁable

if and only if there exists a variable x such that there are paths from x and ¬x and from ¬x to x

in G(φ).

(2) Show that given a directed graph G containing n vertices it is possible to determine whether two

vertices v

and v

are connected in polynomial time.

(3) Find an eﬃcient algorithm to solve 2SAT.

Exercise 3.25: PSPACE ⊆ EXP

The complexity class EXP (for exponential time) contains all decision problems which may be decided

by a Turing machine running in exponential time, that is time O(2

), where k is any constant. Prove

that PSPACE ⊆ EXP. (Hint: If a Turing machine has l internal states, an m letter alphabet, and uses

space p(n), argue that the machine can exist in one of at most lm

p(n)

diﬀerent states, and that if the

Turing machine is to avoid inﬁnite loops then it must halt before revisiting a state.)

Exercise 3.26: L ⊆ P

The complexity class L (for logarithmic space) contains all decision problems which may be decided by a

Turing machine running in logarithmic space, that is, in space O(log(n)). More precisely, the class L is

deﬁned using a two-tape Turing machine. The ﬁrst tape contains the problem instance, of size n, and is a

read-only tape, in the sense that only program lines which don’t change the contents of the ﬁrst tape are

allowed. The second tape is a working tape which initially contains only blanks. The logarithmic space

requirement is imposed on the second, working tape only. Show that L ⊆ P.

Exercise 3.27: Approximation algorithm for VERTEX COVER

Let G = (V, E) be an undirected graph. Prove that the following algorithm ﬁnds a vertex cover for G

that is within a factor of two of being a minimial vertex cover.

V C = ∅

′

= E

while E

′

= ∅ do

let (α, β) be any edge of E

′

V C = V C ∪ {α, β}

remove from E

′

every edge incident on α or β

end

return VC

Exercise 3.28: Arbitrariness of the constant in the deﬁnition of BPP

Suppose k is a ﬁxed constant, 1/2 < k ≤ 1. Suppose L is a language such that there exists a Turing

machine M with the property that whenever x ∈ L, M accepts x with probability at least k, and whenever

x /∈ L, M rejects x with probability at least k. Show that L ∈ BPP.

Exercise 3.29: Fredkin gate is self-inverse

Show that applying two consecutive Fredkin gates gives the same outputs as inputs.

Solution

Concepts Involved: Fredkin Gates. Recall the input/output table of the Fredkin gate:

Inputs Outputs

a b c a

′

0 0 0 0 0 0

0 0 1 0 0 1

0 1 0 0 1 0

0 1 1 1 0 1

1 0 0 1 0 0

1 0 1 0 1 1

1 1 0 1 1 0

1 1 1 1 1 1

We check for all possible 8 input states that applying the Fredkin gate returns the original input state.

F [F [(0, 0, 0)]] = F [(0, 0, 0)] = (0, 0, 0)

F [F [(0, 0, 1]] = F [(0, 0, 1)] = (0, 0, 1)

F [F [(0, 1, 0]] = F [(0, 1, 0)] = (0, 1, 0)

F [F [(0, 1, 1)]] = F [(1, 0, 1)] = (0, 1, 1)

F [F [(1, 0, 0)]] = F [(1, 0, 0)] = (1, 0, 0)

F [F [(1, 0, 1)]] = F [(0, 1, 1)] = (1, 0, 1)

F [F [(1, 1, 0)]] = F [(1, 1, 0)] = (1, 1, 0)

F [F [(1, 1, 1)]] = F [(1, 1, 1)] = (1, 1, 1)

We conclude that the Fredkin gate is self-inverse.

Exercise 3.30

Verify that the billiard ball computer in Figure 3.14 computes the Fredkin gate.

Exercise 3.31: Reversible half-adder

Construct a reversible circuit which, when two bits x and y are input, outputs (x, y, c, x ⊕ y), where c is

the carry bit when x and y are odd.

Exercise 3.32: From Fredkin to Toﬀoli and back again

What is the smallest number of Fredkin gates needed to simulate a Toﬀoli gate? What is the smallest

number of Toﬀoli gates needed to simulate a Fredkin gate?

Problem 3.1: Minsky machines

A Minsky machine consists of a ﬁnite set of registers, r

, r

, . . . , r

, each capable of holding an arbitrary

non-negative integer, and a program, made up of orders of one of two types. The ﬁrst type has the form:

The interpretation is that at point m in the program register rj is incremented by one, and execution

proceeds to point n in the program. The second type of order has the form:

The interpretation is that at point m in the program, register r

is decremented if it contains a positive

integer, and execution proceeds to point n in the program. If register r

is zero then execution simply

proceeds to point p in the program. The program for the Minsky machine consists of a collection of such

orders, of a form like:

The starting and all possible halting points for the program are conventionally labeled zero. This program

takes the contents of register r

and adds them to register r

, while decrementing r

to zero.

(1) Prove that all (Turing) computable functions can be computed on a Minsky machine, in the sense

that given a computable function f(·) there is a Minsky machine program that when the registers

start in the state (n, 0, . . . , 0) gives as output (f (n), 0, . . . , 0).

(2) Sketch a proof that any function which can be computed on a Minsky machine, in the sense just

deﬁned, can also be computed on a Turing machine.

Problem 3.2: Vector games

A vector game is speciﬁed by a ﬁnite list of vectors, all of the same dimension, and with integer co-

ordinates. The game is to start with a vector x of non-negative integer co-ordinates and to add to x

the ﬁrst vector from the list which preserves the non-negativity of all the components, and to repeat this

process until it is no longer possible. Prove that for any computable function f(·) there is a vector game

which when started with the vector (n, 0, . . . , 0) reaches (f(n), 0, . . . , 0) (Hint: Show that a vector game

in k + 2 dimensions can simulate a Minsky machine containing k registers.)

Problem 3.3: Fractran

A Fractran program is deﬁned by a list of positive rational numbers q

, . . . , q

. It acts on a positve integer

m by replacing it by q

m where i is the least number such that q

m is an integer. If there is ever a time

when there is no i such that q

m is an integer, then execution stops. Prove that for any computable

function f(·) there is a Fractran program which when started with 2

reaches 2

f(n)

without going through

any intermediate powers of 2. (Hint: use the previous problem.)

Problem 3.4: Undecidability of dynamical systems

A Fractran program is essentially just a very simple dynamical system taking positive integers to positive

integers. Prove that there is no algorithm to decide whether such a dynamical system ever reaches 1.

Problem 3.5: Non-universality of two bit reversible logic

Suppose we are trying to build circuits using only one and two bit reversible logic gates, and ancilla bits.

Prove that there are Boolean functions which cannot be computed in this fashion. Deduce that the Toﬀoli

gate cannot be simulated using one and two bit reversible gates, even with the aid of ancilla bits.

Problem 3.6: Hardness of approximation of TSP

Let r ≥ 1 and suppose that there is an approximation algorithm for TSP which is guaranteed to ﬁnd the

shorted tour among n cities to within a factor r. Let G = (V, E) be any graph on n vertices. Deﬁne

an instance of TSP by identifying cities with vertices in V , and deeﬁnign the distance between cities i

and j to be 1 if (i, j) is an edge of G, and to be ⌈r⌉|V | + 1 otherwise. Show that if the approximation

algorithm is applied to this instance of TSP then it returns a Hamiltonian cycle for G if one exists, and

otherwise returns a tour of length more than ⌈r⌉|V |. From the NP-completeness of HC it follows that no

such approximation algorithm can exist unless P = NP.

Problem 3.7: Reversible Turing machines

(1) Explain how to construct a reversible Turing machine that can compute the same class of functions

as is computable on an ordinary Turing machine. (Hint: It may be helpful to use a multi-tape

construction.)

(2) Give general space and time bounds for the operation of your reversible Turing machine, in terms

of the time t(x) and space s(x) required on an ordinary single-tape Turing machine to compute a

function f(x).

Problem 3.8: Find a hard-to-compute class of functions (Research)

Find a natural class of functions on n inputs which requires a super-polynomial number of Boolean gates

to compute.

Problem 3.9: Reversible PSPACE = PSPACE

It can be shown that the problem ‘quantiﬁed satisﬁability’, or QSAT, is PSPACE-complete. That is, every

other language in PSPACE can be reduced to QSAT in polynomial time. The language QSAT is deﬁned

to consist of all Boolean formulae φ in n variables x

, . . . , x

, and in conjunctive normal form, such that:

∃

∀

∃

. . . ∀

φ if n is even;

∃

∀

∃

. . . ∃

φ if n is odd.

Prove that a reversible Turing machine operating in polynomial space can be used to solve QSAT. Thus, the

class of languages decidable by a computer operating reversibly in polynomial space is equal to PSPACE.

Problem 3.10: Ancilla bits and eﬃciency of reversible computation

Let p

be the mth prime number. Outline the construction of a reversible circuit which, upon the input of

m and n such that n > m, outputs the product p

, that is (m, n) 7→ (p

, g(m, n)) where g(m, n)

is the ﬁnal state of the ancilla bits used by the circuit. Estimate the number of ancilla qubits your circuit

requires. Prove that if a polynomial (in log n) size reversible circuit can be found that uses O(log(log n))

ancilla bits then the problem of factoring a product of two prime numbers is in P.

4 Quantum circuits

Exercise 4.1

In Exercise 2.11, which you should do now if you haven’t already done it, you computed the eigenvectors of

the Pauli matrices. Find the points on the Bloch sphere which correspond to the normalized eigenvectors

of the diﬀerent Pauli matrices.

Solution

Concepts Involved: Linear Algebra.

Recall that a single qubit in the state |ψ⟩ = a|0⟩ + b|1⟩ can be visualized as a point (θ, φ) on the Bloch

sphere, where a = cos



θ/2



and b = e

iφ

sin



θ/2



We recall from 2.11 that Z (and I) has eigenvectors |0⟩, |1⟩, X has eigenvectors |+⟩ =

|0⟩+|1⟩

√

, |−⟩ =

|0⟩−|1⟩

√

, and Y has eigenvectors |y

⟩ =

|0⟩+i|1⟩

√

, |y

−

⟩ =

|0⟩−i|1⟩

√

. Expressing these vectors as points on the

Bloch sphere (using spherical coordinates), we have:

|0⟩

∼

(0, 0) ; |1⟩

∼

(π, 0) ; |+⟩

∼



, 0



;

|−⟩

∼



, π



; |y

⟩

∼





; |y

−

⟩

∼



3π



Exercise 4.2

Let x be a real number and A a matrix such that A

= I. Show that

exp(iAx) = cos(x)I + i sin(x)A

Use this result to verify Equations (4.4) through (4.6).

Solution

Concepts Involved: Linear Algebra, Operator Functions.

Let |v⟩ be an eigenvector of A with eigenvalue λ. It then follows that A

|v⟩ = λ

|v⟩, and furthermore

we have that A

|v⟩ = I|v⟩ = |v⟩ by assumption. We obtain that λ

= 1 and therefore the only possible

eigenvalues of A are λ = ±1. Let |v

⟩, . . . , |v

⟩ be the eigenvectors with eigenvalue 1 and |v

k+1

⟩, . . . , |v

⟩

be the eigenvectors with eigenvalue −1. By the spectral decomposition, we can write:

A =

i=1

⟩⟨v

| −

i=k+1

⟩⟨v

so by the deﬁnition of operator functions we have:

exp(iAx) =

i=1

exp(ix) |v

⟩⟨v

| +

i=k+1

exp(−ix) |v

⟩⟨v

By Euler’s identity we have:

exp(iAx) =

i=1



cos(x) + i sin(x)



⟩⟨v

| +

i=k+1



cos(x) − i sin(x)



⟩⟨v

Grouping terms, we obtain:

exp(iAx) = cos(x)

i=1

⟩⟨v

| + i sin(x)





i=1

⟩⟨v

| −

i=k+1

⟩⟨v





Using the spectral decomposition and deﬁnition of I, we therefore obtain the desired relation:

exp(iAx) = cos(x)I + i sin(x)A.

Since all of the Pauli matrices satisfy A

= I (Exercise 2.41), for θ ∈ R we can apply this obtained relation

to obtain:

exp



−iθX/2



= cos





I − i sin





X =

cos

−i sin

cos

exp



−iθY/2



= cos





I − i sin





Y =

cos

−sin

sin

cos

exp



−iθZ/2



= cos





I − i sin





Z =

cos

− i sin

0 cos

− i sin

−iθ/2

0 e

iθ/2

which veriﬁes equations (4.4)-(4.6).

Exercise 4.3

Show that, up to a global phase, the π/8 gate satisﬁes T = R

(π/4)

Solution

Concepts Involved: Linear Algebra, Quantum Gates.

Recall that the T gate is deﬁned as:

T =

1 0

0 exp



iπ/4



We observe that:

(π/4) =

−iπ/8

0 e

iπ/8

= e

−iπ/8

1 0

0 e

iπ/4

= e

−iπ/8

Exercise 4.4

Express the Hadamard gate H as a product of R

and R

rotations and e

iφ

for some φ.

Solution

Concepts Involved: Linear algebra, Quantum Gates

We claim that H = R

(π/2)R

(π/2) up to a global phase of e

−iπ/2

. Doing a computation to

verify this claim, we see that:

(π/2)R

(π/2) =

−iπ/4

0 e

iπ/4

cos

−i sin

cos

−iπ/4

0 e

iπ/4

−iπ/4

0 e

iπ/4

√

−

√

−

√

−iπ/4

0 e

iπ/4

√

−iπ/4

0 e

iπ/4

−iπ/4

−ie

iπ/4

−ie

−iπ/4

iπ/4

√

−iπ/2

−i

−i e

iπ/2

√

−iπ/2

−e

−iπ/2

−e

−iπ/2

iπ/2

−iπ/2

√

1 1

1 −1

= e

−iπ/2

Remark: If you are more algebraically minded, the following may appeal to you.

(π/2)R

(π/2) =

√

(1 − iZ) (1 − iX) (1 − iZ)

√

(1 − iZ − iX − ZX) (1 − iZ)

√

(1 − iZ − iX − ZX − iZ − XZ − 1 + iZXZ)

√

(−2iX − 2iZ) (using ZXZ = −X)

−iH

Exercise 4.5

Prove that (ˆn · σ)

= I, and use this to verify Equation (4.8)

Solution

Concepts Involved: Linear Algebra

Expanding out the expression, we see that:

(ˆn · σ)

= (n

X + n

Y + n

= n

+ n

(XY + Y X) + n

(XZ + ZX) + n

(Y Z + ZY )

Using the result from Exercise 2.41 that



, σ



= 0 if i ̸= j and σ

= I, we have that:

(ˆn · σ)

= (n

+ n

)I = I

where we use the fact that ˆn is a vector of unit length. With this shown, we can use the result of Exercise

4.2 to conclude that:

exp



−iθˆn · σ/2



= cos





− i sin





(ˆn · σ)

which veriﬁes equation (4.8).

Exercise 4.6: Bloch sphere interpretation of rotations

(∗) One reason why the R

ˆn

(θ) operators are referred to as rotation operators is the following fact, which

you are to prove. Suppose a single qubit has a state represented by the Bloch vector λ. Then, the eﬀects

of the rotation R

ˆn

(θ) on the state is to rotate it by an angle θ about the ˆn axis of the Bloch sphere. This

fact explains the rather mysterious looking factors of two in the deﬁnition of the rotation matrices.

Solution

Concepts Involved: Linear Algebra, Quantum Gates.

Let λ be an arbitrary Bloch vector. WLOG, we can express λ in a coordinate system such that ˆn is

aligned with the ˆz axis, so it suﬃces to consider how the state behaves under application R

(θ). Let

λ = (λ

, λ

) be the vector expressed in this coordinate system. By Exercise 2.72, the density operator

corresponding to this Bloch vector is given by:

ρ =

I + λ · σ

We now observe how ρ transforms under conjugation by R

(θ):

(θ)ρR

(θ)

†

= R

(θ)ρR

(−θ)

= R

(θ)



I + λ

X + λ

Y + λ



(−θ)

Using that XZ = −ZX from Exercise 2.41, we make the observation that:

(θ)X =

cos





I − i sin





= X

cos





I + i sin





= X

cos



−θ



I − i sin



−θ



= XR

(−θ)

Similarly, we ﬁnd that R

(θ)Y = R

(−θ)Y (same anticommutation) and that R

(θ)Z = ZR

(θ) (all

terms commute). With this, the expression for R

(θ)ρR

(θ)

†

simpliﬁes to:

(θ)ρR

(θ)

†

= R

(θ)



I + λ

X + λ

Y + λ



(−θ)



(θ) + λ

(−θ) + λ

Y R

(−θ) + λ

(θ)



(−θ)

I + λ

(−2θ) + λ

Y R

(−2θ) + λ

Calculating each of the terms in the above expression, we have:

(−2θ) = X

cos



−2θ



− i sin



−2θ



= X



cos(θ) + i sin(θ)Z



= cos(θ)X + i sin(θ)XZ

= cos(θ)X + i sin(θ)(−iY )

= cos(θ)X + sin(θ)Y

Y R

(−2θ) = Y



cos(θ) + i sin(θ)Z



= cos(θ)Y + i sin(θ)Y Z

= cos(θ)Y + i sin(θ)(iX)

= cos(θ)Y − sin(θ)X.

Plugging these back into the expression for R

(θ)ρR

(θ)

†

and collecting like terms, we have:

(θ)ρR

(θ)

†

I + (λ

cos(θ) − λ

sin(θ))X + (λ

sin(θ) + λ

cos(θ))Y + λ

From this expression, we can read oﬀ the new Bloch vector λ

′

after conjugation by R

(θ) to be:

′

= (λ

cos(θ) − λ

sin(θ), λ

sin(θ) + λ

cos(θ), λ

Alternatively, suppose we apply the 3-dimensional rotation matrix A

(θ) to the original bloch vector λ.

We have that:

(θ)λ =







cos θ −sin θ 0

sin θ cos θ 0

0 0 1

























cos θ − λ

sin θ

sin θ + λ

cos θ







We see that we end up with the same resulting vector λ

′

. We conclude that the conjugation of ρ under

(θ) has the equivalent eﬀect to rotating the Bloch vector by θ about the ˆz-axis, and hence the eﬀect

of R

ˆn

(θ) on a one qubit state is to rotate it by an angle θ about ˆn.

Exercise 4.7

Show that XY X = −Y and use this to prove that XR

(θ)X = R

(−θ).

Solution

Concepts Involved: Linear Algebra, Quantum Gates.

For the ﬁrst claim, we use that XY = −Y X and X

= I (Exercise 2.41) to obtain that:

XY X = −Y XX = −Y I = −Y.

Using this, we have that:

(θ)X = X

cos





I − i sin





= cos





XIX − i sin





XY X

= cos





I + i sin





= cos



−



I − i sin



−



= R

(−θ).

Exercise 4.8

An arbitrary single qubit unitary operator can be written in the form

U = exp(iα)R

ˆn

(θ)

for some real numbers α and θ, and a real three-dimensional unit vector ˆn.

1. Prove this fact.

2. Find values for α, θ, and ˆn giving the Hadamard gate H.

3. Find values for α, θ, and ˆn giving the phase gate

S =

1 0

0 i

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Quantum Gates

1. By deﬁnition, for any unitary operator U we have that U

†

U = I, so for any state vector ⟨ψ|ψ⟩ =

⟨ψ|U

†

U|ψ⟩. Therefore, all unitary Us are norm-preserving, and hence for a single qubit correspond

to some reﬂection/rotation in 3-dimensional space (up to a global phase factor). Hence, we can

write U = exp(iα)R

ˆn

(θ) for some ˆn (rotation axis), θ (rotation angle) and α (global phase).

2. Using the fact that H =

X+Z

√

, and that modulo a factor of i that X/Z correspond to rotations

(π) and R

(π), we ﬁnd that:

H =

(π) + iR

(π)

√

= i

2 cos





I − i sin





X − i sin





√

= i

cos





I − i sin





√

X + 0Y +

√



= e

iπ/2

cos





I − i sin





√

X + 0Y +

√



Note that in the second last equality we use that cos





= 0 and hence

√

cos





= cos





. From

the last expression, we can read oﬀ using the deﬁnition of R

ˆn

(θ) that ˆn =



√

, 0,

√



, θ = π, and

α =

3. We observe that:





−iπ/4

0 e

iπ/4

= e

−iπ/4

1 0

0 i

Hence:

S = e

iπ/4





from which we obtain that ˆn = ˆz = (0, 0, 1), θ =

, and α =

Remark: For part (2), one just can use the deﬁnition

ˆn

(θ) ≡ exp



−iθˆn ·⃗σ/2



= cos





I − i sin







X + n

Y + n



and the fact H = (X + Z) /

√

2, to arrive at cos





= 0, n

= n

√

, n

= 0.

Exercise 4.9

Explain why any single qubit unitary operator may be written in the form (4.12).

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Quantum Gates.

Recall that (4.12) states that we can write any single qubit unitary U as:

U =

i(α−β/2−δ/2)

cos

−e

i(α−β/2+δ/2)

sin

i(α+β/2−δ/2)

sin

i(α+β/2+δ/2)

cos

where α, β, γ, δ ∈ R.

Let U be a single qubit unitary operator. We then have that U

†

U = I, so identifying:

U =

a b

c d

we obtain that:

|a|

+ |c|

∗

b + c

∗

+ cd

∗

|b|

+ |d|

1 0

0 1

From the diagonal entries we obtain that |v

| = |v

| = 1 and from the oﬀ diagonal entries we obtain that

⟨v

, v

⟩ = 0 and hence the columns of U are orthonormal. From the fact that |v|

is normalized, we can

parameterize the magnitude of the entries with γ ∈ R such that:

|a| = cos

, |c| = sin

From the orthogonality, we further obtain that b = −c

∗

and d = a

∗

, from which we have that |b| = |c|

and |d| = |a|. Furthermore, (also from the orthogonality) we can parameterize arg(a) = −

−

and

arg(b) =

−

For β, δ ∈ R. Finally, multiplying U by a complex phase e

iα

for α ∈ R preserves the

unitarity of U and the orthonormality of the colums. Combining these facts gives the form of (4.12) as

desired.

Exercise 4.10: X − Y decomposition of rotations

Give a decomposition analogous to Theorem 4.1 but using R

instead of R

Exercise 4.11

Suppose ˆm and ˆn are non-parallel real unit vectors in three dimensions. Use Theorem 4.1 to show that

an arbitrary single qubit unitary U may be written

U = e

iα

ˆn

(β)R

ˆm

(γ)R

ˆn

(δ)

Exercise 4.12

Give A, B, C, and α for the Hadamard gate.

Solution

Concepts Involved: Linear Algebra, Decomposition of Rotations.

Recall that any single qubit unitary U can be written as U = e

iα

AXBXC where ABC = I and α ∈ R.

First, observe that we can write:

H =

√

1 1

1 −1

= i

−i 0

0 i

√

−1

√

1 0

0 1

= e

iπ/2

(π)R

(−π/2)R

(0)

so deﬁning A, B, C according to the proof of Corollary 4.2, we have:

A = R

(π)R

(−π/4)

B = R

(π/4)R

(−π/2)

C = R

(−π/2)

and α =

Exercise 4.13: Circuit identities

It is useful to be able to simplify circuits by inspection, using well-known identities. Prove the following

three identities:

HXH = Z; HY H = −Y ; HZH = X.

Solution

Concepts Involved: Linear Algebra, Quantum Gates.

By computation, we ﬁnd:

HXH =

1 1

1 −1

0 1

1 0

1 1

1 −1

2 0

0 −2

1 0

0 −1

= Z

HY H =

1 1

1 −1

0 −i

i 0

1 1

1 −1

0 −2i

2i 0

= −

0 −i

i 0

= −Y

HZH =

1 1

1 −1

1 0

0 −1

1 1

1 −1

0 2

2 0

0 1

1 0

= X

Remark: Notice once we have proved HXH = Z, we can directly say HZH = H(HXH)H = X as

= I. If one wants to prove everything algebraically, the following calculation suﬃces.

HXH

(X + Z) X (X + Z) =

(I + ZX) (X + Z) =

(X + Z + Z + XZX) = Z

HY H

(X + Z) Y (X + Z) =

(XY + ZY ) (X + Z) =

(XY X + ZXY + ZY X + ZY Z) = −Y

Exercise 4.14

Use the previous exercise to show that HT H = R

(π/4), up to a global phase.

Solution

Concepts Involved: Linear Algebra, Quantum Gates.

From Exercise 4.3, we know that T = R

(π/4) up to a global phase e

−iπ/8

. We hence have that:

HT H = e

−iπ/8

(π/4)H

= e

−iπ/8

cos





I − i sin





= e

−iπ/8

cos





I − i sin





= e

−iπ/8

(π/4)

where in the second last equality we use the previous exercise, as well as the fact that HIH = H

= I

from Exercise 2.52.

Exercise 4.15: Composition of single qubit operations

The Bloch representation gives a nice way to visualize the eﬀect of composing two rotations.

(1) Prove that if a rotation through an angle β

about the axis ˆn

is followed by a rotation through an

angle β

about an axis ˆn

, then the overall rotation is through an angle β

about an axis ˆn

given

= c

− s

ˆn

· ˆn

ˆn

= s

ˆn

+ c

ˆn

− s

ˆn

× ˆn

where c

= cos





, s

= sin





, c

= cos





, and s

= sin





(2) Show that if β

= β

and ˆn

= ˆz these equations simplify to

= c

− s

ˆz · ˆn

ˆn

= sc(ˆz + ˆn

) − s

ˆn

×ˆz

Solution

Concepts Involved: Linear Algebra

(1) It suﬃces to show that R

ˆn

(β

ˆn

(β

) is equivalent to R

ˆn

(β

ˆn

(β

ˆn

(β

) = (c

I − is

ˆn

· σ) · (c

I − is

ˆn

· ˆσ)

= c

I − i (c

ˆn

· σ + c

ˆn

· σ) − s

(ˆn

· σ) · (ˆn

· σ)

| {z }

(ˆn

·ˆn

)I + i(ˆn

×ˆn

)·σ



− s

(ˆn

· ˆn

)



I − i



ˆn

+ c

ˆn

+ s

(ˆn

× ˆn

)



· σ

Identifying this operation to a single rotation R

ˆn

(β

) ≡ c

I − is

ˆn

· σ, we arrive at the

required relations (up to a presumable typesetting error)

= c

− s

(ˆn

· ˆn

)

ˆn

= c

ˆn

+ c

ˆn

+ s

(ˆn

× ˆn

)

(2) Setting β

= β

and ˆn

= ˆz in the formulas proven above combined with the fact that c = c

cos





= cos





= c

(and similiarly s = s

= s

), we have:

= c

− s

ˆz · ˆn

ˆn

= scˆz + csˆn

− s

ˆn

×ˆz = sc(ˆz + ˆn

) − s

ˆn

×ˆz.

Remark: For the sake of completeness, we provide a proof of the identity used in part 1 of the solution.

First note the familiar Pauli matrix relation σ

= δ

I + iϵ

ijk

(Exercise 2.43). Now massaging this

equation gives

= a

+ i



ijk



= (a · b) I + i (a × b)

where we have used standard Einstein index notation. Thus in matrix form, we have

(a · σ) · (b · σ) = (a · b) I + i (a × b) · σ .

Exercise 4.16

What is the 4 × 4 unitary matrix for the circuit

in the computational basis? What is the unitary matrix for the circuit

Solution

Concepts Involved: Linear Algebra, Quantum Gates, Tensor Products.

The unitary matrix for the ﬁrst circuit is given by:

⊗ H

1 0

0 1

⊗

√

1 1

1 −1

√







1 1 0 0

1 −1 0 0

0 0 1 1

0 0 1 −1







The unitary matrix for the second circuit is given by:

⊗ I

√

1 1

1 −1

⊗

1 0

0 1

√







1 0 1 0

0 1 0 1

1 0 −1 0

0 1 0 −1







Exercise 4.17: Building a CNOT from controlled-Z gates

Construct a CNOT gate from one controlled-Z gate, that is, the gate whose action in the computational

basis is speciﬁed by the unitary matrix







1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 −1







Solution

Concepts Involved: Linear Algebra, Quantum Gates, Controlled Operations.

We showed in Exercise 4.13 that HZH = X. Hence, to obtain a CNOT gate from a single controlled Z

gate, we can conjugate the target qubit with Hadamard gates:

H Z H

We can verify this via matrix multiplication, using the result from the previous exercise:

⊗ H

)(CZ

1,2

)(I

⊗ H

) =







1 1 0 0

1 −1 0 0

0 0 1 1

0 0 1 −1













1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 −1













1 1 0 0

1 −1 0 0

0 0 1 1

0 0 1 −1













2 0 0 0

0 2 0 0

0 0 0 2

0 0 2 0







= CX

1,2

Remark:

1,2

= |0⟩⟨0| ⊗ I + |0⟩⟨0| ⊗ X

= |0⟩⟨0| ⊗ HH + |0⟩⟨0| ⊗ HZH

(I ⊗ H)(CZ

1,2

)(I ⊗ H).

Exercise 4.18

Show that

Solution

Concepts Involved: Linear Algebra, Quantum Gates, Controlled Operations.

It suﬃces to verify that the two gates have the same eﬀect on the 2-qubit computational basis states (as

it will then follow by linearity that they will have the same eﬀect on any such superposition of the basis

states). Checking the 8 necessary cases, we then have that:

1,2

(|0⟩

⊗ |0⟩

) = |0⟩

⊗ |0⟩

2,1

(|0⟩

⊗ |0⟩

) = |0⟩

⊗ |0⟩

1,2

(|1⟩

⊗ |0⟩

) = |1⟩

⊗ Z|0⟩

= |1⟩

⊗ |0⟩

2,1

(|1⟩

⊗ |0⟩

) = |1⟩

⊗ |0⟩

1,2

(|0⟩

⊗ |1⟩

) = |0⟩

⊗ |1⟩

2,1

(|0⟩

⊗ |1⟩

) = Z|0⟩

⊗ |1⟩

= |0⟩

⊗ |1⟩

1,2

(|1⟩

⊗ |1⟩

) = |1⟩

⊗ Z|1⟩

= |1⟩

⊗ −|1⟩

= −(|1⟩

⊗ |1⟩

)

2,1

(|1⟩

⊗ |1⟩

) = Z|1⟩

⊗ |1⟩

= −|1⟩

⊗ |1⟩

= −(|1⟩

⊗ |1⟩

)

from which we observe equality for each. The claim follows.

Remark: More compactly, we have CZ

1,2

⟩ = |b

⟩ ⊗ Z

⟩ = (−1)

⟩ for computational

basis states b

, b

∈ {0, 1}.

Using this form we can write

1,2

⟩ = (−1)

⟩

= (−1)

⟩

= Z

⟩ ⊗ |b

⟩

2,1

⟩.

Exercise 4.19: CNOT action on unitary matrices

The CNOT gate is a simple permutation whose action on a density matrix ρ is to rearrange the elements

in the matrix. Write out this action explicitly in the computational basis.

Solution

Concepts Involved: Linear Algebra, Quantum Gates, Controlled Operations, Density Operators

Let ρ be an arbitrary density matrix corresponding to a 2-qubit state. In the computational basis, we can

write ρ as:

∼













Studying the action of the CNOT gate on this density matrix, we calculate:

1,2

ρ CX

1,2







1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

























1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

























1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0



















100

Exercise 4.20: CNOT basis transformations

Unlike ideal classical gates, ideal quantum gates do not have (as electrical engineers say) ‘high-impedance’

inputs. In fact, the role of ‘control’ and ‘target’ are arbitrary – they depend on what basis you think of a

device as operating in. We have described how the CNOT behaves with respect to the computational basis,

and in this description the state of the control qubit is not changed. However, if we work in a diﬀerent

basis then the control qubit does change: we will show that its phase is ﬂipped depending on the state of

the ‘target’ qubit! Show that

H H

Introducing basis states |±⟩ ≡ (|0⟩ ± |1⟩)/

√

2, use this circuit identity to show that the eﬀect of a CNOT

with the ﬁrst qubit as control and the second qubit as target is as follows:

|+⟩|+⟩ 7→ |+⟩|+⟩

|−⟩|+⟩ 7→ |−⟩|+⟩

|+⟩|−⟩ 7→ |−⟩|−⟩

|−⟩|−⟩ 7→ |+⟩|−⟩.

Thus, with respect to this new basis, the state of the target qubit is not changed, while the state of the

control qubit is ﬂipped if the target starts as |−⟩, otherwise it is left alone. That is, in this basis, the

target and control have essentially interchanged roles!

Solution

Concepts Involved: Linear Algebra, Quantum Gates, Controlled Operations.

First, we have that:

⊗ H

1 1

1 −1

⊗

1 1

1 −1







1 1 1 1

1 −1 1 −1

1 1 −1 −1

1 −1 −1 1







101

Now conjugating CNOT

1,2

under H

⊗ H

, we have:

⊗ H

)CX

1,2

⊗ H

) =







1 1 1 1

1 −1 1 −1

1 1 −1 −1

1 −1 −1 1













1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0













1 1 1 1

1 −1 1 −1

1 1 −1 −1

1 −1 −1 1













4 0 0 0

0 0 0 4

0 0 4 0

0 4 0 0







= CX

2,1

which proves the circuit identity. We know already that:

2,1

|0⟩|0⟩ = |0⟩|0⟩

2,1

|1⟩|0⟩ = |1⟩|0⟩

2,1

|0⟩|1⟩ = |1⟩|1⟩

2,1

|1⟩|1⟩ = |0⟩|1⟩

so using the proven circuit identity and the fact that H|0⟩ = |+⟩, H|1⟩ = |−⟩, we obtain the map:

|+⟩|+⟩ 7→ |+⟩|+⟩

|−⟩|+⟩ 7→ |−⟩|+⟩

|+⟩|−⟩ 7→ |−⟩|−⟩

|−⟩|−⟩ 7→ |+⟩|−⟩

which is exactly what we wanted to prove.

Remark: Algebraically,

(H ⊗ H)CX

1,2

(H ⊗ H) = (H ⊗ H)(I ⊗ H)(CZ

1,2

)(I ⊗ H)(H ⊗ H)

= (H ⊗ I)(CZ

1,2

)(H ⊗ I)

= (H ⊗ I)(CZ

2,1

)(H ⊗ I)

= CX

2,1

102

Exercise 4.21

Verify that Figure 4.8 implements the C

(U) operation.

†

Exercise 4.22

Prove that a C

(U) gate (for any single qubit unitary U) can be constructed using at most eight one-qubit

gates, and six controlled-NOTs.

Exercise 4.23

Construct a C

(U) gate for U = R

(θ) and U = R

(θ), using only CNOT and single qubit gates. Can you

reduce the number of single qubit gates needed in the construction from three to two?

Exercise 4.24

Verify that Figure 4.9 implements the Toﬀoli gate.

103

Exercise 4.25: Fredkin gate construction

Recall that the Fredkin (controlled-swap) gate performs the transform







1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1







(1) Give a quantum circuit which uses three Toﬀoli gates to construct the Fredkin gate (Hint: think of

the swap gate construction – you can control each gate, one at a time).

(2) Show that the ﬁrst and last Toﬀoli gates can be replaced by CNOT gates.

(3) Now replace the middle Toﬀoli gate with the circuit in Figure 4.8 to obtain a Fredkin gate construc-

tion using only six two-qubit gates.

(4) Can you come up with an even simpler construction, with only ﬁve two-qubit gates?

Exercise 4.26

Show that the circuit:

diﬀers by a Toﬀoli gate only by relative phases. That is, the circuit that takes |c

, c

, t⟩ to

iθ(c

,t)

, c

, t ⊕ c

· c

⟩, where e

iθ(c

,t)

is some relative phase factor. Such gates can be some-

times be useful in experimental implementations, where it may be much easier to implement a gate that

is the same as the Toﬀoli gate up to relative phases than it is to do the Toﬀoli directly.

104

Exercise 4.27

Using just CNOTs and Toﬀoli gates, construct a quantum circuit to perform the transformation







1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0







This kind of partial cyclic permutation operation will be useful later, in Chapter 7.

Exercise 4.28

For U = V

with V unitary, construct a C

(U) gate analogous to that in Figure 4.10, but using no work

qubits. You may use controlled-V and controlled-V

†

gates.

Exercise 4.29

Find a circuit containing O(n

) Toﬀoli, CNOT and single qubit gates which implements a C

(X) gate (for

n > 3), using no work qubits.

Exercise 4.30

Suppose U is a single qubit unitary operation. Find a circuit containing O(n

) Toﬀoli, CNOT and single

qubit gates which implements a C

(U) gate (for n > 3), using no work qubits.

105

Exercise 4.31: More circuit identities

Let subscripts denote which qubit an operator acts on, and ket C be a CNOT with qubit 1 the control qubit

and qubit 2 the target qubit. Prove the following identities:

C = X

C = Y

C = Z

C = X

C = Z

z,1

(θ)C = CR

z,1

(θ)

x,2

(θ)C = CR

x,2

(θ).

Exercise 4.32

Let ρ be the density matric describing a two qubit system. Suppose we perform a projective measurement

in the computational basis of the second qubit. Let P

= |0⟩⟨0| and P

= |1⟩⟨1| be the projectors onto

the |0⟩ and the |1⟩ states of the second qubit, respectively. Let ρ

′

be the density matrix which would be

assigned to the system after the measurement by an observer who did not learn the measurement result.

Show that

′

= P

ρP

+ P

ρP

Also show that the reduced density matrix for the ﬁrst qubit is not aﬀected by the measurement, that is

(ρ) = tr

(ρ

′

Exercise 4.33: Measurement in the Bell basis

The measurement model we have speciﬁed for the quantum circuit model is that measurements are

performed only in the computational basis. However, often we want to perform a measurement in some

other basis, deﬁned by a complete set of orthonormal states. To perform this measurement, simply unitarily

transform from the basis we wish to perform the measurement in to the computational basis, then measure.

For example, show that the circuit

performs a measurement in the basis of the Bell states. More precisely, show that this circuit results in

a measurement being performed with corresponding POVM elements the four projectors onto the Bell

states. What are the corresponding measurement operators?

106

Exercise 4.34: Measuring an operator

Suppose we have a single qubit operator U with eigenvalues ±1, so that U is both Hermitian and unitary, so

it can be regarded as both an observable and a quantum gate. Suppose we wish to measure the observable

U. That is, we desire to obtain a measurement result indicating one of the two eigenvalues, and leaving

a post-measurement state which is the corresponding eigenvector. How can this be implemented by a

quantum circuit? Show that the following circuit implements a measurement of U :

|0⟩

H H

|ψ

⟩

|ψ

out

⟩

Exercise 4.35: Measurement commutes with controls

A consequence of the principle of deferred measurement is that measurements commute with quantum

gates when the qubit being measured is a control qubit, that is:

(Recall that the double lines represent classical bits in this diagram.) Prove the ﬁrst equality. The rightmost

circuit is simply a convenient notation to depict the use of a measurement result to classically control a

quantum gate.

Exercise 4.36

Construct a quantum circuit to add two two-bit numbers x and y modulo 4. That is, the circuit should

perform the transformation |x, y⟩ 7→ |x, x + y mod 4⟩.

Exercise 4.37

Provide a decomposition of the transform







1 1 1 1

1 i −1 −i

1 −1 1 1

1 −i −1 i







into a product of two-level unitaries. This is a special case of the quantum Fourier transform, which we

study in more detail in the next chapter.

Exercise 4.38

Prove that there exist a d × d unitary matrix U which cannot be decomposed as a product of fewer than

d − 1 two-level unitary matrices.

107

Exercise 4.39

Find a quantum circuit using single qubit operations and CNOTs to implement the transformation







1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0

0 0 a 0 0 0 0 c

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 b 0 0 0 0 d







where

U =

a c

b d

is an arbitrary 2 × 2 unitary matrix.

Exercise 4.40

For arbitrary α and β show that

E(R

ˆn

(α), R

ˆn

(θ)

) <

and use this to justify (4.76).

Exercise 4.41

This and the next two exercises develop a construction showing that the Hadamard, phase, controlled-NOT

and Toﬀoli gates are universal. Show that the circuit in Figure 4.17 applies the operation R

(θ) to the

third (target) qubit if the measurement outcomes are both 0, where cos θ = 3/5, and otherwise applies Z

to the target qubit. Show that the probability of both measurement outcomes being 0 is 5/8, and explain

how repeated use of this circuit and Z = S

gates may be used to apply a R

(θ) gate with probability

approaching 1.

108

Exercise 4.42: Irrationality of θ

Suppose cos θ = 3/5. We give a proof by contradiction that θ is an irrational multiple of 2π.

(1) Using the fact that e

iθ

= (3 + 4i)/5, show that if θ is rational, then there must exist a positive

integer m such that (3 + 4i)

= 5

(2) Show that (3+4i)

= 3+4i (mod 5) for all m > 0, and conclude that no m such that (3+4i)

can exist.

Exercise 4.43

Use the results of the previous two exercises to show that the Hadamard, phase, controlled-NOT and Toﬀoli

gates are universal for quantum computation.

Exercise 4.44

Show that the three qubit gate G deﬁned by the circuit:

(πα)

is universal for quantum computation whenever α is irrational.

Exercise 4.45

Suppose U is a unitary transform implemented by an n qubit quantum circuit constructed from H, S,

CNOT and Toﬀoli gates. Show that U is of the form 2

−k/2

M for some integer k, where M is a 2

× 2

matrix with only complex integer entries. Repeat this exercise with the TOﬀoli gate replaced by the π/8

gate.

Exercise 4.46: Exponential complexity growth of quantum systems

Let ρ be a density matrix describing the state of n qubits. Show that describing ρ requires 4

− 1

independent real numbers.

Exercise 4.47

For H =

, prove that e

−iHt

= e

−iH

. . . e

−iH

for all i if [H

, H

] = 0, for all j, k.

Exercise 4.48

Show that the restriction of H

to at most c particles implies that in the sum (4.97), L is upper bounded

by a polynomial in n.

109

Exercise 4.49: Baker–Campbell–Hausdorf formula

Prove that

(A+B)∆t

= e

A∆t

B∆t

−

[A,B]∆t

+ O(∆t

)

and also prove Equations (4.103) and (4.104).

Exercise 4.50

Let H =

, and deﬁne

∆t

−iH

∆t

−iH

∆t

. . . e

−iH

∆t

−iH

∆t

−iH

L−1

∆t

. . . e

−iH

∆t

(a) Prove that U

∆t

= e

−2iH∆t

+ O(∆t

)

(b) Use the results in Box 4.1 to prove that for a positive integer m,

E(U

∆t

, e

−2miH∆t

) ≤ mα∆t

for some constant α.

Exercise 4.51

Construct a quantum circuit to simulate the Hamiltonian

H = X

⊗ Y

⊗ Z

performing the unitary transform e

−i∆tH

for any ∆t.

Problem 4.1: Computable phase shifts

Let m and n be positive integers. Suppose f

{0, . . . , 2

− 1} 7→ {0, . . . , 2

− 1} is a classical function

from m to n bits which may be computed reversibly using T Toﬀoli gates, as described in Section 3.2.5.

That is, the function (x, y) 7→ (x, y ⊕ f(x)) may be implemented using T Toﬀoli gates. Give a quantum

circuit using 2T + n (or fewer) one, two and three qubit gates to implement the unitary operation deﬁned

|x⟩ 7→ exp



−2iπf(x)



|x⟩

Problem 4.2

Find a depth O(log n) construction for the C

(X) gate. (Comment: The depth of a circuit is the number

of distinct timesteps at which gates are applied; the point of this problem is that it is possible to parallelize

the C

(X) construction by applying many gates in parllel during the same timestep.)

110

Problem 4.3: Alternate universality construction

Suppose U is a unitary matrix on n qubits. Deﬁne H ≡ i ln(U). Show that

(1) H is Hermitian, with eigenvalues in the range 0 to 2π.

(2) H can be written

H =

where h

are real numbers and the sum is over all n-fold tensor products g of the Pauli matrices

{I, X, Y, Z}.

(3) Let ∆ = 1/k, for some positive integer k. Explain how the unitary operation exp



−ih

g∆



may be

implemented using O(n) one and two qubit operations.

(4) Show that

exp(−iH∆) =

exp



−ih

g∆



+ O(4

∆

)

where the product is taken with respect to any ﬁxed ordering of the n-fold tensor products of Pauli

matrices, g.

(5) Show that

U =





exp



−ih

h∆







+ O(4

∆)

(6) Explain how to approximate U to within a distance ϵ > 0 using O(n16

/ϵ) one and two qubit

unitary operations.

Problem 4.4: Minimal Toﬀoli construction (Research)

The following problems concern constructions of the Toﬀoli with some minimal number of other gates. ‘

(1) What is the smallest number of two qubit gates that can be used to implement the Toﬀoli gate?

(2) What is the smallest number of one qubit gates and CNOT gates that can be used to implement the

Toﬀoli gate?

(3) What is the smallest number of one qubit gates and controlled-Z gates that can be used to implement

the Toﬀoli gate?

Problem 4.5: (Research)

Construct a family of Hamiltonians, {H

} , on n qubits, such that simulating H

requires a number of

operations super-polynomial in n. (Comment: This problem seems to be quite diﬃcult.)

111

Problem 4.6: Universality with prior entanglement

Controlled-NOT gates and single qubit gates form a universal set of quantum logic gates. Show that

an alternative universal set of resources is comprised of single qubit unitaries, the ability to perform

measurements of pairs of qubits in the Bell basis, and the ability to prepare arbitrary four qubit entangled

states.

112

10 Quantum error-correction

Exercise 10.1

Verify that the encoding circuit in Figure 10.2 works as claimed.

|ψ⟩

|0⟩

that is, it encodes |ψ⟩ = a |0⟩ + b |1⟩ to a |000⟩ + b |111⟩.

Solution

Concepts Involved: Linear Algebra, Quantum Gates, Controlled Operations.

We calculate:

|ψ⟩ ⊗ |0⟩ ⊗ |0⟩ 7→ CX

1,3

1,2

|ψ⟩ ⊗ |0⟩ ⊗ |0⟩

= aCX

1,3

1,2

|000⟩ + bCX

1,3

1,2

|100⟩

= a |000⟩ + b |111⟩

where we use the deﬁnition of the controlled-X gate CX

1,2

|0⟩ ⊗ |φ⟩ = |0⟩ ⊗ |φ⟩ and CX

1,2

|1⟩ ⊗ |φ⟩ =

|1⟩ ⊗ X

|φ⟩ in the last line.

Exercise 10.2

The action of the bit ﬂip channel can be described by the quantum operation E(ρ) = (1 − p)ρ + pXρX.

Show that this may be given an alternative operator-sum representation, as E(ρ) = (1−2p)ρ+2pP

ρP

2pP

−

ρP

−

where P

and P

−

are projectors onto the +1 and −1 eigenstates of X, (|0⟩ + |1⟩)/

√

2 and

(|0⟩ − |1⟩)/

√

2, respectively. This latter representation can be understood as a model in which the qubit

is left alone with probability 1 − 2p, and is ‘measured’ by the environment in the |+⟩, |−⟩ basis with

probability 2p.

Solution

Concepts Involved: Linear Algebra, Projectors, Spectral Decomposition.

First, note that we may write:

= |+⟩⟨+| =

|+⟩⟨+| + |−⟩⟨−| + |+⟩⟨+| − |−⟩⟨−|

I + X

where we have used X = |+⟩⟨+| − |−⟩⟨−| as the spectral decomposition of X and I = |+⟩⟨+| + |−⟩⟨−|

the resolution of the identity. We can obtain the analogous relation for P

−

I − X

113

Therefore we can expand:

E(ρ) = (1 − 2p)ρ + 2pP

ρP

+ 2pP

−

ρP

−

= (1 − 2p)ρ + 2p

I + X

+ 2p

I − X

= (1 − 2p)ρ +

(ρ + Xρ + ρX + XρX) +

(ρ − Xρ − ρX + XρX)

= (1 − p)ρ + pXρX

which proves the claim.

Exercise 10.3

Show by explicit calculation that measuring Z

followed by Z

is equivalent, up to labeling of the

measurement outcomes, to measuring the four projectors deﬁned by (10.5)–(10.8), in the sense that both

procedures result in the same measurement statistics and post-measurement states.

Solution

Concepts Involved: Linear Algebra, Projectors, Spectral Decomposition.

The four projection operators corresponding to the four error syndromes of the three-qubit repetition code

are given by:

≡ |000⟩⟨000| + |111⟩⟨111|

≡ |100⟩⟨100| + |011⟩⟨011|

≡ |010⟩⟨010| + |101⟩⟨101|

≡ |001⟩⟨001| + |110⟩⟨110|

It suﬃces to show that the composition of projectors corresponding to measurements of Z

and Z

yield the same four projectors as the above. Z

has spectral decomposition:

= (|00⟩⟨00| + |11⟩⟨11|) ⊗ I − (|01⟩⟨01| + |10⟩⟨10|) ⊗ I

which corresponds to a projective measurement with projectors:

=+1

= (|00⟩⟨00| + |11⟩⟨11|) ⊗ I

=−1

= (|01⟩⟨01| + |10⟩⟨10|) ⊗ I

analogously, Z

has spectral decomposition:

= I ⊗ (|00⟩⟨00| + |11⟩⟨11|) − I ⊗ (|01⟩⟨01| + |10⟩⟨10|)

which corresponds to a projective measurement with projectors:

=+1

= I ⊗ (|00⟩⟨00| + |11⟩⟨11|)

=−1

= I ⊗ (|01⟩⟨01| + |10⟩⟨10|).

114

Now, we observe that:

=+1

= [(|00⟩⟨00| + |11⟩⟨11|) ⊗ I][I ⊗ (|00⟩⟨00| + |11⟩⟨11|)] = |000⟩⟨000| + |111⟩⟨111| = P

=−1

=+1

= [(|01⟩⟨01| + |10⟩⟨10|) ⊗ I][I ⊗ (|00⟩⟨00| + |11⟩⟨11|)] = |011⟩⟨011| + |100⟩⟨100| = P

=−1

= [(|01⟩⟨01| + |10⟩⟨10|) ⊗ I][I ⊗ (|01⟩⟨01| + |10⟩⟨10|)] = |010⟩⟨010| + |101⟩⟨101| = P

=+1

=−1

= [(|00⟩⟨00| + |11⟩⟨11|) ⊗ I][I ⊗ (|01⟩⟨01| + |10⟩⟨10|)] = |001⟩⟨001| + |110⟩⟨110| = P

so the claim is proven.

Exercise 10.4

Consider the three qubit bit ﬂip code. Suppose we had performed the error syndrome measurement by

measuring the eight orthogonal projectors corresponding to projections onto the eight computational basis

states.

(1) Write out the projectors corresponding to this measurement, and explain how the measurement

result can be used to diagnose the error syndrome: either no bits ﬂipped or bit number j ﬂipped,

where j is in the range one to three.

(2) Show that the recovery procedure works only for computational basis states.

(3) What is the minimum ﬁdelity for the error-correction procedure?

Solution

Concepts Involved: Linear Algebra, Projectors, Error Syndrome and Recovery, Fidelity

(1) The projectors are:

|000⟩⟨000|, |001⟩⟨001|, |010⟩⟨010|, |100⟩⟨100|, |011⟩⟨011|, |101⟩⟨101|, |110⟩⟨110|, |111⟩⟨111|.

Since the encoded state is |ψ⟩ = a |000⟩ + b |111⟩, if we measure one of |000⟩, |111⟩ we would

conclude no bits have been ﬂipped. If we measure |001⟩ or |110⟩, we would conclude that bit 1

was ﬂipped (and so the state had become a |001⟩ + b |110⟩. If we measure |010⟩ or |101⟩, then we

would conclude that bit 2 was ﬂipped (and so the state had become a |010⟩ + b |101⟩). Finally, if

we measure |100⟩ or |011⟩, we would conclude that bit 3 was ﬂipped (and so the state had become

a |100⟩ + b |011⟩).

(2) The recovery procedure involves doing nothing if the error syndrome tells us that no bits are ﬂipped,

or ﬂipping the jth bit if the jth bit was ﬂipped. In the no bit ﬂip case, after recovery we have

|000⟩ → |000⟩, |111⟩ → |111⟩. In the case we conclude the ﬁrst bit was ﬂipped, after recovery

we have |001⟩ → |000⟩, |110⟩ → |111⟩. In the case we conclude the second bit was ﬂipped, after

recovery we have |010⟩ → |000⟩, |101⟩ → |111⟩. Finally if we conclude that the third bit was ﬂipped,

115

after recovery we have |100⟩ → |000⟩, |011⟩ → |111⟩. In all cases, the post-recovery state is one

of the computational basis states |000⟩/ |111⟩, so the recovery only succeeds if the initial state was

one of the computational basis states.

(3) Supposing we use the three qubit error-correcting code to protect |ψ⟩ = a |0⟩ + b |1⟩. The encoded

state is |Ψ⟩ = a |000⟩+ b |111⟩. After applying the noise channel (i.e. each bit ﬂips with probability

p), the state we have is:

E(ρ

) =



|a|

(1 − p)

+ |b|



|000⟩⟨000|



|a|

p(1 − p)

+ |b|

(1 − p)





|001⟩⟨001| + |010⟩⟨010| + |100⟩⟨100|





|b|

p(1 − p)

+ |a|

(1 − p)





|110⟩⟨110| + |101⟩⟨101| + |011⟩⟨011|





|b|

(1 − p)

+ |a|



|111⟩⟨111|

The recovery procedure maps any state with ≥ 2 zeros to |000⟩⟨000| (and hence back to |0⟩⟨0| after

decoding) and any state with ≥ 2 ones to |111⟩⟨111| (and hence back to |1⟩⟨1| after decoding), so

the ﬁnal state is:

= R(E(ρ

)) =



|a|

(1 − p)

+ 3p(1 − p)

+ |b|

+ 3p

(1 − p)



|0⟩⟨0|



|b|

(1 − p)

+ 3p(1 − p)

+ |a|

+ 3p

(1 − p)



|1⟩⟨1|

To ﬁnd the minimum ﬁdelity, it suﬃces to minimize ⟨ψ|ρ |ψ⟩, which we compute to be:

⟨ψ|ρ |ψ⟩ = |a|



|a|

(1 − p)

+ 3p(1 − p)

+ |b|

+ 3p

(1 − p)



+ |b|



|b|

(1 − p)

+ 3p(1 − p)

+ |a|

+ 3p

(1 − p)



With the normalization constraint on the initial state of |a|

+ |b|

= 1, we can rewrite the above in

terms of of |a|

alone:

⟨ψ|ρ |ψ⟩ =



2(|a|

)

− 2|a|

+ 1

h

(1 − p)

+ 3p(1 − p)



2|a|

− 2(|a|

)

h

+ 3p

(1 − p)

We take the derivative of the above w.r.t. |a|

and set it to zero to ﬁnd the minimzing value of |a|

∂

∂|a|

⟨ψ|ρ |ψ⟩ = (4|a|

− 2)

(1 − p)

+ 3p(1 − p)

− p

+ 3p

(1 − p)

= 0

Which for any value of p is satisﬁed when |a|

, i.e. |a| =

√

(and so |b| =

√

as well). So,

the ﬁdelity is minimized for |ψ⟩ =

√

iφ

|0⟩ + e

iφ

|1⟩) (which is what we might have expected -

given that the error correction succeeds only for the computational basis states, we should have the

worst ﬁdelity for states which are the furthest from both). For these states, the ﬁdelity is (plugging

116

into our former general expression):

min

|ψ|ρ |ψ⟩ =

(1 − p)

+ 3p(1 − p)

+ 3p

(1 − p) + p

√

Exercise 10.5

Show that the syndrome measurement for detecting phase ﬂip errors in the Shor code corresponds to

measuring the observables X

and X

Solution

Concepts Involved: Linear Algebra, Eigenvalues, Eigenvectors, Error Syndrome

We have the codewords:

⟩ =

(|000⟩ + |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

⟩ =

(|000⟩ − |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√

A phase ﬂip error on a given block amounts to ﬂipping the phase of the block:

(|000⟩ ± |111⟩) = |000⟩ ∓ |111⟩

Measuring X

1−2

= X

compares the phase of the ﬁrst and second blocks (with +1 if they

are the same, -1 if they are diﬀerent) - we can see this from the eigenvalue relations:

(|000⟩ + |111⟩)(|000⟩ + |111⟩) = +1(|000⟩ + |111⟩)(|000⟩ + |111⟩)

(|000⟩ − |111⟩)(|000⟩ + |111⟩) = +1(|111⟩ − |000⟩)(|000⟩ + |111⟩)

= −1(|000⟩ + |111⟩)(|000⟩ + |111⟩)

(|000⟩ + |111⟩)(|000⟩ − |111⟩) = +1(|000⟩ + |111⟩)(|111⟩ − |000⟩)

= −1(|000⟩ + |111⟩)(|000⟩ + |111⟩)

(|000⟩ − |111⟩)(|000⟩ − |111⟩) = +1(|111⟩ − |000⟩)(|111⟩ − |000⟩)

= +1(|000⟩ + |111⟩)(|000⟩ + |111⟩)

analogously, measuring X

2−3

= X

compares the phase of the second and third blocks.

The codewords have all three blocks with the same phase, so if we measure X

1−2

= X

2−3

= +1 then we

conclude no phase ﬂip error occured. If we measure X

1−2

= +1 and X

2−3

= −1 then we conclude that

a phase ﬂip must have occured in the third block (one of qubits 7/8/9). If we measure X

1−2

= −1 and

2−3

= +1 then we conclude that a phase ﬂip occured on the ﬁrst block (one of qubits 1/2/3). If we

measure X

1−2

= X

2−3

= −1 then we conclude that a phase ﬂip error occured on the second block (one

of qubits 4/5/6). We thus conclude that measuring these two operators yields the syndrome for detecting

phase ﬂip errors.

117

Exercise 10.6

Show that recovery from a phase ﬂip on any of the ﬁrst three qubits may be accomplished by applying

the operator Z

Solution

Concepts Involved: Linear Algebra, Error Recovery

We have the encoded state:

|ψ

⟩ = α |0

⟩ + β |1

⟩

= α

(|000⟩ + |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

+ β

(|000⟩ − |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√

We saw that Z

(|000⟩±|111⟩) = |000⟩∓|111⟩ for i ∈ {1, 2, 3}, so if a phase ﬂip error occurs on the ﬁrst

qubit, we have:

|ψ

⟩

−→ α

(|000⟩ − |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

+ β

(|000⟩ + |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√

Now since Z

(|000⟩ ± |111⟩) = |000⟩ ± (−1)

|111⟩ = |000⟩ ∓ |111⟩, we have:



(|000⟩ − |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

+ β

(|000⟩ + |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√



= α

(|000⟩ + |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

+ β

(|000⟩ − |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√

= |ψ

⟩

so the error correction is accomplished.

Exercise 10.7

Consider the three qubit bit ﬂip code of Section 10.1.1, with corresponding projector P =

|000⟩⟨000| + |111⟩⟨111|. The noise process this code protects against has operation elements

(1 − p)

p(1 − p)

where p is the probability that the bit ﬂips.

Note that this quantum operation is not trace-preserving, since we have omitted operation elements cor-

responding to bit ﬂips on two and three qubits. Verify the quantum error-correction conditions for this

code and noise process.

Solution

Concepts Involved: Linear Algebra, Projectors, Error Correction Conditions.

We calculate P E

†

P for each of the errors E

. Note that in this case the errors are all Hermitian,

so this reduces to calculation of P E

P for all combinations of errors. Furthermore, note that the

set of errors

(1 − p)

p(1 − p)

is mutually commuting, so

118

P E

P = P E

P so we only need to check all combinations (and the order does not eﬀect the result).

(1 − p)

IP = (1 − p)

= (1 − p)

p(1 − p)

P = p(1 − p)

P IP = p(1 − p)

= p(1 − p)

p(1 − p)

P = p(1 − p)

P IP = p(1 − p)

= p(1 − p)

p(1 − p)

P = p(1 − p)

P IP = p(1 − p)

= p(1 − p)

where we have used that Paulis square to the identity and projectors are idempotent. For the other

combinations we ﬁnd:

(1 − p)

p(1 − p)

P =

p(1 − p)

(|000⟩⟨000| + |111⟩⟨111|)(|100⟩⟨000| + |011⟩⟨111|) = 0 = 0P

(1 − p)

p(1 − p)

P =

p(1 − p)

(|000⟩⟨000| + |111⟩⟨111|)(|010⟩⟨000| + |101⟩⟨111|) = 0 = 0P

(1 − p)

p(1 − p)

P =

p(1 − p)

(|000⟩⟨000| + |111⟩⟨111|)(|001⟩⟨000| + |110⟩⟨111|) = 0 = 0P

p(1 − p)

P = p(1 − p)

(|000⟩⟨100| + |111⟩⟨011|)(|010⟩⟨000| + |101⟩⟨111|) = 0 = 0P

p(1 − p)

P = p(1 − p)

(|000⟩⟨100| + |111⟩⟨011|)(|001⟩⟨000| + |110⟩⟨111|) = 0 = 0P

p(1 − p)

P = p(1 − p)

(|000⟩⟨010| + |111⟩⟨101|)(|001⟩⟨000| + |110⟩⟨111|) = 0 = 0P

So we therefore ﬁnd:

P E

†

P = α

where:

α =







(1 − p)

0 0 0

0 p(1 − p)

0 0

0 0 p(1 − p)

0 0 0 p(1 − p)







is Hermitian. The error-correction conditions are therefore veriﬁed.

119

Exercise 10.8

Verify that the three qubit phase ﬂip code |0

⟩ = |+ + +⟩, |1

⟩ = |−− −⟩ satisﬁes the quantum

error-correction conditions for the set of error operators {I, Z

, Z

Solution

Concepts Involved: Linear Algebra, Projectors, Error Correction Conditions.

First, note the projector onto the code C in this case is:

P = |+ + +⟩⟨+ + +| + |− − −⟩⟨− − −|

We calculate P E

†

P for each of the errors E

∈ {I, Z

, Z

}. The calculation is completely analogous

to that in Ex. 10.7, simply replacing X → Z, |0⟩ → |+⟩, |1⟩ → |−⟩, and setting all of the pre-factors

(1 − p)

and

p(1 − p)

to one. The result we ﬁnd is:

P E

†

P = α

where:

α =







1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1







which is of course Hermitian, and the QEC conditions are thus satisﬁed.

Exercise 10.9

Again, consider the three qubit phase ﬂip code. Let P

and Q

be the projectors into the |0⟩ and |1⟩

states, respectively, of the ith qubit. Prove that the three qubit phase ﬂip code protects against the error

set {I, P

, Q

, P

, Q

, P

, Q

Solution

Concepts Involved: Linear Algebra, Error Correction Conditions, Discretization of Errors.

By Theorem 10.2 in the text, we know that if C is a quantum code and R is the error-correction procedure

constructed via the error correction conditions that corrects for a noise process E with operation elements

}, then R also corrects for arbitrary complex linear combinations of the E

. We then note that all

errors in {I, P

, Q

, P

, Q

, P

, Q

} can be written as linear combinations of errors in {I, Z

, Z

I = I, P

I + Z

, Q

I − Z

therefore by Theorem 10.2 and the result of Ex. 10.8, the phase ﬂip code can protect against

{IP

, Q

, P

, Q

, P

, Q

120

Exercise 10.10

Explicitly verify the quantum error-correction conditions for the Shor code, for the error set containing I

and the error operators X

, Y

, Z

for j = 1 through 9.

Solution

Concepts Involved: Linear Algebra, Projectors, Error Correction Conditions.

We have:

P = |0

⟩⟨0

| + |1

⟩⟨1

where:

⟩ =

(|000⟩ + |111⟩)(|000⟩ + |111⟩)(|000⟩ + |111⟩)

√

⟩ =

(|000⟩ − |111⟩)(|000⟩ − |111⟩)(|000⟩ − |111⟩)

√

All E

we consider in the set of errors are Hermitian, so E

†

= E

. Firstly, since all Pauli operators square

to the identity, we ﬁnd for all E

that:

P E

†

P = P E

P = P IP = P

= P

Next, we observe:

P IX

P = P IY

P = P IZ

P = P X

P = P Z

P = P X

P = P Y

P = P Z

= 0 = 0P

as all possible bit/phase ﬂips on a single qubit map the codewords to states orthogonal to both codewords.

Next, we ﬁnd that for k ̸= l that:

P X

P = P Y

P = P X

P = P Y

P = P X

P = P Z

P = P Y

P = P Z

= 0 = 0P

as in each case we have a bit ﬂip on one or two qubits which maps the codewords to state orthogonal to

both codwords.

Finally, we ﬁnd that:

P Z

P =







P if k, l are in the same block

0 if k, l are in diﬀerent blocks

as in the former case the two phase ﬂips cancel out (and thus P is preserved), and in the latter case

we have phase ﬂips on two diﬀerent blocks and the codewords are mapped to states orthogonal to both

codewords.

121

We thus conclude that:

P E

†

P = α

where α

is Hermitian (as it has 1s on the diagonal, 1s on entries for Z

with i, j in the same block

(thus symmetric across the diagonal), and zero elsewhere). We have thus veriﬁed the quantum error

correction conditions.

Exercise 10.11

Construct operation elements for a single qubit quantum operation E that upon input of any state ρ

replaces it with the completely randomized state I/2. It is amazing that even such noise models as this

may be corrected by codes such as the Shor code!

Solution

Concepts Involved: Linear Algebra, Density Operators, Quantum Operations.

We wish to ﬁnd operation elements {E

} such that:

E(ρ) =

ρE

†

for any input single-qubit state ρ. We claim that





are the operation elements with this

desired property. First, we verify that they satisfy the completeness relation:

†

+ X

+ Y

+ Z

) =

(4I) = I

Next, we verify that they have the claimed property of sending every initial qubit state to the maximally

mixed state. From Ex. 2.72, we can write a single-qubit density operator as:

ρ =

I + r

X + r

Y + r

122

where r = (r

, r

) ∈ R

and ∥r∥ = 1. Now calculating E(ρ), we have:

E(ρ) =

(ρ + XρX + Y ρY + ZρZ)



(I + X

+ Y

+ Z

) + r

(X + X

+ Y XY + ZXZ)

+ r

(Y + XY X + Y

+ ZY Z) + r

(Z + XZX + Y ZY + Z

)





4I + r

(2X + 2iY Z) + r

(2Y + 2iZX) + r

(2Z + 2iXY )





4I + r

(2X + 2i(iX) + r

(2Y + 2i(iY )) + r

(2Z + 2i(iZ))



(4I)

where we use that XY = iZ, Y Z = iX, and XZ = iY . The claim is thus proven.

Remark:

The described channel is of course the single-qubit depolarizing channel of full strength.

Exercise 10.12

Show that the ﬁdelity between the state |0⟩ and E(|0⟩⟨0|) is

1 − 2p/3, and use this to argue that the

minimum ﬁdelity for the depolarizing channel is

1 − 2p/3.

Solution

Concepts Involved: Linear Algebra, Density Operators, Quantum Operations, Fidelity.

The density operator corresponding to |0⟩ is |0⟩⟨0|, and sending this through the depolarizing channel we

have:

E(|0⟩⟨0|) = (1 − p) |0⟩⟨0| +

(X |0⟩⟨0|X + Y |0⟩⟨0|Y + Z |0⟩⟨0|Z)

= (1 − p) |0⟩⟨0| +

(|1⟩⟨1| + |1⟩⟨1| + |0⟩⟨0|)

= (1 −

) |0⟩⟨0| +

|1⟩⟨1|

and so:

F (|0⟩, E(|0⟩⟨0|)) =

⟨0|



(1 −

) |0⟩⟨0| +

|1⟩⟨1|



|0⟩ =

1 −

(4)

as claimed. Because the depolarizing channel is symmetric in X/Y /Z, it is therefore symmetric in possible

input states and so for any input state |ψ⟩ we would ﬁnd that F (|0⟩, E(|0⟩⟨0|)) =

1 − 2p/3. As such,

this is the minimum ﬁdelity.

123

For a more rigorous argument; by from Ex. 2.72, we can write a single-qubit density operator as:

ρ =

I + r

X + r

Y + r

where r = (r

, r

) ∈ R

and ∥r∥ = 1 when ρ = |ψ⟩⟨ψ| a pure state. We then have that:

⟨ψ|X |ψ⟩ = Tr





= Tr



X + r

I + r

Y X + r



= r

and analogously for Y /Z. We then have:

F (|ψ⟩, E(|ψ⟩⟨ψ|)) =

⟨ψ|



(1 − p) |ψ⟩⟨ψ| +

(X |ψ⟩⟨ψ|X + Y |ψ⟩⟨ψ|Y + Z |ψ⟩⟨ψ|Z)



(1 − p) |ψ⟩⟨ψ|

(⟨ψ|X |ψ⟩

+ ⟨ψ|Y |ψ⟩

+ ⟨ψ|Z |ψ⟩

(1 − p) +

+ r

)

(1 − p) +

1 −

where we use that ∥r∥ = 1 in the fourth equality. Since this is true for all pure states, it must be the

minimum ﬁdelity.

Exercise 10.13

Show that the minimum ﬁdelity F (|ψ⟩, E(|ψ⟩⟨ψ|)) when E is the amplitude damping channel when E is

the amplitude damping channel with parameter γ is

√

1 − γ.

Solution

Concepts Involved: Linear Algebra, Fidelity.

Let |ψ⟩ = a |0⟩ + b |1⟩ with |a|

+ |b|

= 1. Then we have:

|ψ⟩⟨ψ| =

|a|

∗

b |b|

and after applying the amplitude damping channel we have (from Ex. ??):

E(|ψ⟩⟨ψ|) =

1 − (1 − γ)(1 − |a|

) ab

∗

√

1 − γ

∗

√

1 − γ |b|

(1 − γ)

124

Calculating the ﬁdelity, we then have:

F (|ψ⟩, E(|ψ⟩⟨ψ|)) =

⟨ψ|E(|ψ⟩⟨ψ|) |ψ⟩

∗

1 − (1 − γ)(1 − |a|

) ab

∗

√

1 − γ

∗

√

1 − γ |b|

(1 − γ)

|a|

(1 − (1 − γ)(1 − |a|

)) + 2|a|

|b|

1 − γ + |b|

(1 − γ)

Using the normalization condition, |b|

= 1 − |a|

so we can write the above in terms of |a|

alone:

F (|ψ⟩, E(|ψ⟩⟨ψ|)) =

|a|

(1 − (1 − γ)(1 − |a|

)) + 2|a|

(1 − |a|

)

1 − γ + (1 − |a|

)

(1 − γ)

2(1 −

1 − γ − γ)(|a|

)

+ (−2 + 2

1 − γ + 3γ)|a|

+ 1 − γ

This is minimized when the expression under the square root is minimized. Taking the derivative w.r.t

|a|

, we ﬁnd:

∂

∂|a|

(F (|ψ⟩, E(|ψ⟩⟨ψ|)))

= 4(1 −

1 − γ − γ)|a|

− 2 + 2

1 − γ + 3γ

which is non-negative for |a|

∈ [0, 1] (which is the domain over which it is deﬁned). Therefore

F (|ψ⟩, E(|ψ⟩⟨ψ|)) is an increasing function of |a|

over [0, 1], and hence F (|ψ⟩, E(|ψ⟩⟨ψ|)) is minimized

when a = 0 and therefore |ψ⟩ = |1⟩. In this case, the ﬁdelity is:

F (|ψ⟩, E(|ψ⟩⟨ψ|))

min

= F (|1⟩, E(|1⟩⟨1|)) =

1 − γ

as claimed.

Exercise 10.14

Write an expression for a generator matrix encoding k bits using r repetitions for each bit. This is an

[rk, k] linear code, and should have an rk × k generator matrix.

Solution

Concepts Involved: Linear Algebra, Generator Matrices.

The claimed generator matrix G is an rk × k matrix such that:







1 r(j − 1) < i ≤ rj

0 otherwise.

By matrix multiplication, we can see that:

G(x

, x

, . . . , x

) = (

r times

z }| {

, . . . , x

r times

z }| {

, . . . , x

, . . . ,

r times

z }| {

, . . . , x

)

125

Exercise 10.15

Show that adding one column of G to another results in a generator matrix generating the same code.

Solution

Concepts Involved: Linear Algebra, Generator Matrices.

The set of possible codewords of a code corresponds to the vector space spanned by the columns of G.

So if G = [v

, v

, . . . v

] then the possible codewords are:

v = c

+ c

+ . . . + c

where c

∈ Z

and addition is done modulo 2. WLOG suppose we add column 2 to colummn 1 (permuting

the columns of G clearly preserves the codespace, as it just amounts to permuting labels in the equation

above), so we have G

′

= [v

+ v

, v

, . . . , v

], so the possible codewords are:

′

= c

′

+ v

) + c

′

+ . . . + c

′

where c

′

∈ Z

. By deﬁning c

′

= c

, c

′

= c

+ c

, and c

′

= c

for j ≥ 2 we can see that the codewords

′

are the same as the codewords v, and thus G and G

′

generate the same code.

Exercise 10.16

Show that adding one row of the parity check matrix to another does not change the code. Using Gaussian

elimination and swapping of bits it is therefore possible to assume that the parity check matrix has the

standard form [A|I

n−k

] where A is an (n − k) × k matrix.

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices.

In the parity check matrix formulation, an [n, k] code is all x ∈ Z

such that Hx = 0 where H ∈ Z

(n−k)×n

is the parity check matrix. We can write:

H =













with v

the rows of H. By the deﬁnition of matrix multiplication, it follows from Hx = 0 that:

· x = 0

for each i and for all codewords x. WLOG suppose we add row 2 to row 1 (permuting the rows of H

126

clearly preserves the codespace, as the above condition is unchanged). We then have:

′







+ v







It then follows that if Hx = 0, then H

′

x = 0 as:

+ v

) · x = v

· x + v

· x = 0 + 0 = 0

and v

· x = 0 for i ≥ 2. Furthermore, if H

′

x = 0 then Hx = 0 as:

· x = (v

+ v

) · x = (v

· v

) · x + v

· x = 0 + 0 = 0

and v

· x = 0 for i ≥ 2. Therefore, H, H

′

correspond to the same code.

Since Gaussian elimination only involves swapping rows (does nothing to H), swapping columns (changes

the labels of the qubits) and adding rows to each other (does nothing as shown above), we can thus always

assume that the parity check matrix can be brought to standard form.

Exercise 10.17

Find a parity check matrix for the [6, 2] repetition code deﬁned by the generator matrix in (10.54).

Solution

Concepts Involved: Linear Algebra, Generator Matrices, Parity Check Matrices.

The [6, 2] repetition code has generator matrix:

G =







1 0

0 1







To construct H, we pick out 6 −2 = 4 linearly independent vectors orthogonal to the columns of G. Four

such vectors are:

















































127

Therefore one such parity check matrix is:







1 1 0 0 0 0

0 1 1 0 0 0

0 0 0 1 1 0

0 0 0 0 1 1







Exercise 10.18

Show that the parity check matrix H and generator matrix G for the same linear code satisfy HG = 0

Solution

Concepts Involved: Linear Algebra, Genrator Matrices, Parity Check Matrices.

For a given [n, k] code with parity check matrix H and generator matrix G, we can write:

H =







n−k







, G =

··· y

where v

, y

are each n-dimensional vectors which are orthogonal to one another. By the deﬁnition of

matrix multiplication, HG is a n − k × k matrix with entries:

(HG)

= v

· y

= 0

where the last equality follows by orthogonality, thus proving the claim.

Exercise 10.19

Suppose an [n, k] linear code C has a parity check matrix of the form H = [A|I

n−k

], for some (n −k) ×k

matrix A. Show that the corresponding generator matrix is

G =



−A



Solution

Concepts Involved: Linear Algebra, Genrator Matrices, Parity Check Matrices.

To get a generator matrix from a parity check matrix, we pick k linearly independent vectors y

, . . . y

spanning the kernel of H, and set G to have columns y

through yy

. In this case, H has standard form

128

H = [A|I

n−k

] and so we may write:

H =







1,n−k

2,n−k

n−k

n−k,n−k







where v

are the rows of A and e

i,n−k

is a n−k length vector with 1 in the ith position and 0s elsewhere.

We want to ﬁnd vectors in the kernel of H, i.e. vectors y that satisfy:

· y

1,...k

+ e

i,n−k

· y

k+1,...n

for every i ∈ {1, . . . , n − k}. A clear choice that satisﬁes this relation is y

1,...,n−k

= e

n,k

and y

k+1,...,n

−w

where w

is the nth column of A; this choice satisﬁes the above as:

· e

n,k

+ e

i,n−k

· (−w

) = a

− a

= 0

This yields y

, . . . y

, one for each column of A. We therefore construct G as:

G =

1,k

2,k

. . . e

k,k

−w

··· −w

−A

which was what we wished to show.

Exercise 10.20

Let H be a parity check matrix such that any d − 1 columns are linearly independent, but there exists a

set of d linearly dependent columns. Show that the code deﬁned by H has distance d.

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices, Code Distance.

Given a parity check matrix H, a codeword x = (x

, x

, . . . x

) satisﬁes Hx = 0, which implies:

+ x

+ . . . + x

= 0

where h

are the columns of H. Since any d −1 columns are linearly independent, it follows that any sum

of d −1 (or less) columns of H is nonzero, and therefore there are no codewords of weight d −1 or lower.

However, there exists a set of d linearly dependent columns, and therefore there exists a codeword that

is 1 for each of those columns and 0 elsewhere, and is therefore of weight d. There are no codewords of

smaller weight, and therefore we conclude that the code has distance d.

Exercise 10.21: Singleton bound

Show than an [n, k, d] code must satisfy n − k ≥ d − 1.

129

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices, Code Distance.

An [n, k, d] code has an n−k×n parity check matrix H. It therefore has at most n−k linearly independent

columns. From the solution to the previous exercise, if a code has distance d then the parity check matrix

must have all sets of d − 1 columns be linearly independent (else there would exist a codeword of weight

d−1 and hence the code would have distance < d, a contradiction). Combining these two facts, it follows

that:

n − k ≥ d − 1

as claimed.

Exercise 10.22

Show that all Hamming codes have distance 3, and thus can correct an error on a single bit. The Hamming

codes are therefore [2

− 1, 2

− r − 1, 3] codes.

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices, Code Distance.

Recall that the [2

−1, 2

−r −1] Hamming code (for r ≥ 2) is a linear code having parity check matrix

whose columns are all 2

− 1 bit strings of length r which are not zero.

Any two columns of H are diﬀerent and therefore linearly independent. Furthermore, H has the 3 columns:





































which are linearly dependent as they add together to make zero. By Ex. 10.20, any Hamming code has

distance 3. Since a distance d ≥ 2t + 1 code can correct errors on t bits, all Hamming codes can correct

errors on one bit.

Exercise 10.23

(∗) Prove the Gilbert-Varshamov bound.

Exercise 10.24

Show that a code with generator matrix G is weakly self-dual if and only if G

G = 0.

130

Solution

Concepts Involved: Linear Algebra, Generator Matrices, Dual codes.

Recall that if we have a [n, k] code C with generator matrix G and parity check matrix H, then the

dual code C

⊥

is the code consisting of all codewords y such that y is orthogonal to all codewords in C.

Furthermore, recall that a code is weakly self-dual if C ⊆ C

⊥

=⇒

Suppose that G is weakly self dual. Then, it follows that every codeword y = Gx ∈ C is

contained in C

⊥

. Since the parity check matrix applied to a codeword of a code gives zero, for C

⊥

have that G

y = 0 and thus G

y = G

Gx = 0 for all length k binary vectors x, but this is only possible

if G

G = 0.

⇐=

Suppose that G

G = 0. Suppose that y = Gx, y

′

= Gx

′

are codewords of C. We then see that

′

· y = x

′T

Gx = x

′T

0x = 0. Thus, all codewords of C are orthogonal to each other, and thus all

codewords y of C are codewords of C

⊥

by deﬁnition. Thus C ⊆ C

⊥

Exercise 10.25

Let C be a linear code. Show that if x ∈ C

⊥

then

y∈C

(−1)

x·y

= |C|, while if x /∈ C

⊥

then

y∈C

(−1)

x·y

= 0.

Solution

Concepts Involved: Linear Algebra, Dual Codes

Suppose x ∈ C

⊥

. Then it follows that y · x = 0 for every codeword y ∈ C. Thus,

y∈C

(−1)

x·y

y∈C

(−1)

y∈C

1 = |C|. Suppose instead that x /∈ C

⊥

. Then we claim that half the codewords of

C are orthogonal to x with x · y = 0, and the other half are not orthogonal with x · y = 1. As proof of

this fact, suppose there are n basis codewords y

, . . . , y

of C; since x /∈ C

⊥

, it follows that at least one

of these basis codewords is not orthogonal to x. Let y

, . . . , y

be the non-orthogonal basis codewords

and y

k+1

, . . . , y

be the orthogonal codewords. To form an arbitrary codeword of C, we take a linear

combination of the basis codewords. If an even number fo y

, . . . , y

are included in the sum then the

codeword is orthogonal to x and otherwise the codeword is not orthogonal to x. There are 2

k−1

to choose

an even number of elements out of a set of k elements and 2

k−1

ways to choose an odd number, and

therefore there are the same number of codewords in C that are orthogonal to x as there are those that

are not orthogonal. Hence, the contributions of these two evenly weighted parts cancel in the sum to yield

y∈C

(−1)

x·y

= 0.

Exercise 10.26

Suppose H is a parity check matrix. Explain how to compute the transformation |x⟩|0⟩ 7→ |x⟩|Hx⟩ using

a circuit composed entirely of controlled-NOTs.

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices, Controlled Operations

131

By the deﬁnition of matrix multiplication:

(Hx)

(5)

So, if we want the ith bit in the second register to become



(Hx)



, this can be realized by applying a

CNOT gate with control on the jth qubit of the ﬁrst register (in |x⟩) and acting on the ith qubit of the

second register if H

= 1 (and doing nothing if H

= 0); each gate (or identity) realizing one term in

the above sum.

Exercise 10.27

Show that the codes deﬁned by

|x + C

⟩ ≡

y∈C

(−1)

u·y

|x + y + v⟩

as parameterized by u and v are equivalent to CSS(C

, C

) in the sense that they have the same error-

correcting properties. These codes, which we’ll refer to as CSS

u,v

, C

) will be useful later in our study

of quantum key distribution, in Section 12.6.5.

Exercise 10.28

Verify that the transpose of the matrix in (10.77) is the generator of the [7, 4, 3] Hamming code.

Solution

Concepts Involved: Linear Algebra, Parity Check Matrices, Generator Matrices

The matrix in (10.77) is:

H[C

] =







1 0 0 0 0 1 1

0 1 0 0 1 0 1

0 0 1 0 1 1 0

0 0 0 1 1 1 1







Taking the transpose, we have:

H[C

]







1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 1 1 1

1 0 1 1

1 1 0 1







132

Looking at the parity check matrix for the [7, 4, 3] Hamming code, we have:

H[C

] =







0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1







In order to conﬁrm H[C

]

as the generator matrix of the code, we require that the columns are linearly

independent and lie in the kernel of H[C

]. The linearly independence is immediately clear by inspection

(as columns i = 1, 2, 3, 4 uniquely have a non-zero ith entry). Let us then just verify that they lie in the

kernel of H, which can equivalently be done by checking that H[C

]H[C

]

= 0:

H[C

]H[C

]







0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1













1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 1 1 1

1 0 1 1

1 1 0 1













1 + 1 1 + 1 1 + 1 1 + 1 + 1 + 1

1 + 1 1 + 1 1 + 1 1 + 1













0 0 0 0







Exercise 10.29

Show that an arbitrary linear combination of any two elements of V

is also in V

. Therefore, V

is a

subspace of the n qubit state space. Show that V

is the intersection of the subspaces ﬁxed by each

operator in S (that is, the eigenvalue one eigenspaces of elements of S).

Exercise 10.30

Show that −I /∈ S implies ±iI /∈ S.

Solution

Concepts Involved: Group Theory, Pauli Group

Subgroups are groups and therefore closed under multiplication. If iI ∈ S, then (iI)

= (i)

I = −I ∈ S.

The claim is thus shown via the contrapositive.

133

Exercise 10.31

Suppose that S is a subgroup of G

generated by elements g

, . . . , g

. Show that all the elements of S

commute if and only if g

and g

commute for each pair i, j.

Solution

Concepts Involved: Group Theory, Pauli Group

=⇒

Suppose all elements of S commute. Since each generator is itself an element of S, any pair of

generators will commute.

⇐=

Suppose any pair of generators g

, g

of S commute. Any two elements s

, s

∈ S can be written

as a product of generators:

= g

. . . g

, s

= g

. . . g

Using the pairwise commutation of the generators, we can move the g

s together to ﬁnd that s

= g

. . . g

and so all elements of S commute.

Remark: The above argument holds for any group, not just subgroups of G

Exercise 10.32

Verify that the generators in Figure 10.6 stabilize the codewords for the Steane code, as described in

Section 10.4.2.

Exercise 10.33

Show that g and g

′

commute if and only if r(g)Λr(g

′

)

= 0. (In the check matrix representation,

arithmetic is done modulo two.)

Exercise 10.34

Let S = ⟨g

, . . . , g

⟩. Show that −I is not an element of S if and only if g

= I for all j, and g

̸= −I

for all j.

Exercise 10.35

Let S be a subgroup of G

such that −I is not an element of S. Show that g

= I for all g ∈ S, and

thus g

†

= g.

Exercise 10.36

Explicitly verify that UX

†

= X

, U X

†

= X

, U Z

†

= Z

, and UZ

†

= Z

. These and

other useful conjugation relations for the Hadamard, phase, and Pauli gates are summarized in Figure

10.7.

134

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Controlled Operations

First note our ability to write the controlled-NOT operation in block diagonal form:

U = U

†

I 0

0 X

By explicit (block) matrix multiplication we then have:

†

I 0

0 X

0 I

I 0

0 X

0 I

X 0

I 0

0 X

X 0

= X

†

I 0

0 X

X 0

0 X

I 0

0 X

X 0

0 X

I 0

0 X

X 0

0 I

I 0

0 X

X 0

0 X

= X

†

I 0

0 X

I 0

0 −I

I 0

0 X

I 0

0 −X

I 0

0 X

I 0

0 −X

I 0

0 −I

= Z

†

I 0

0 X

Z 0

0 Z

I 0

0 X

Z 0

0 XZ

I 0

0 X

Z 0

0 XZX

Z 0

0 −Z

= Z

Exercise 10.37

What is UY

†

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Controlled Operations

Note from the previous Exercise that UX

†

= X

and UZ

†

= Z

. Hence writing Y = iZX and

using that U

†

U = I:

†

= iUZXU

†

= iUZU

†

UXU

†

= iZ

= iY

Exercise 10.38

Suppose U and V are unitary operators on two qubits which transform Z

, Z

, X

and X

by conjugation

in the same way. Show this implies that U = V .

135

Solution

Concepts Involved: Linear Algebra, Unitary Operators, Pauli Group

We observe that UAU

†

= V AV

†

for A ∈ {Z

, Z

, X

} implies that UAU

†

= V AV

†

for any two

qubit Pauli as UAU

†

UBU

†

= V AV

†

V BV

†

=⇒ UABU

†

= V ABV

†

for any two operators A, B,

and {Z

, Z

, X

} generates all two qubit Paulis via multiplication (which is seen from Z

= I and

ZX = iY ). Then, observing that the two-qubit Pauli operators form a basis for operators acting on

the Hilbert space C

(formally - they are 16 linearly independent vectors in C

4×4

over ﬁeld C, and since

dim C

4×4

= 16 they form a basis) we can write any operator O ∈ C

4×4

as a linear combination of the

two qubit Paulis, O =

. We then have:

UOU

†

= U









†

V A

†

= V









†

= V OV

†

So UOU

†

= V OV

†

for all O ∈ C

4×4

, which is only possible if U = V .

Exercise 10.39

Verify (10.91).

Solution

Concepts Involved: Linear Algebra, Unitary Operators

We verify by matrix multiplication:

SXS

†

1 0

0 i

0 1

1 0

0 −i

0 1

i 0

1 0

0 −i

i 0

= Y

SZS

†

1 0

0 i

1 0

0 −1

1 0

0 −i

1 0

0 −i

1 0

0 −i

1 0

0 (−i)

1 0

0 −1

= Z

136

Exercise 10.40

Provide an inductive proof of Theorem 10.6 as follows.

(1) Prove that the Hadamard and phase gates can be used to perform any normalizer operation on a

single qubit.

(2) Suppose U is an n + 1 qubit gate in N(G

n+1

) such that UZ

†

= X

⊗g and UX

†

= Z

⊗g

′

for some g, g

′

∈ G

. Deﬁne U

′

on n qubits by U

′

|ψ⟩ ≡

√

2⟨0|U(|0⟩ ⊗ |ψ⟩). Use the inductive

hypothesis to show that the construction for U in Figure 10.9 may be implemented using O(n

)

Hadamard, phase, and controlled-NOT gates.

(3) Show that any gate U ∈ N (G

n+1

) may be implemented using O(n

) Hadamard, pahse, and

controlled-NOT gates.

Exercise 10.41

Verify Equations (10.92) through (10.95).

Exercise 10.42

Use the stabilizer formalism to verify that the circuit of Figure 1.13 on page 27 teleports qubits, as claimed.

Note that the stabilizer formalism restricts the class of states being teleported, so in some sense this is

not a complete description of teleportation, nevertheless it does allow an understanding of the dynamics

of teleportation.

Exercise 10.43

Show that S ⊆ N (S) for any subgroup S of G

Exercise 10.44

Show that N (S) = Z(S) for any subgroup S of G

not containing −I.

Exercise 10.45: Correcting located errors

Suppose C(S) is an [n, k, d] stabilizer code. Suppose k qubits are encoded in n qubits using this code,

which is then subjected to noise. Fortunately, however, we are told that only d − 1 of the qubits are

aﬀected by the noise, and moreover, we are told precisely which d − 1 qubits have been aﬀected. Show

that it is possible to correct the eﬀects of such located errors.

137

Exercise 10.46

Show that the stabilizer for the three qubit pahse ﬂip code is generated by X

and X

Exercise 10.47

Verify that the generators of Figure 10.11 generate the two codewords of Equation (10.13).

Exercise 10.48

Show that the operations

Z = X

and

X = Z

act as

logical Z and X operations on a Shor-code encoded qubit. That is, show that this

Z is independent of

and commutes with the generators of the Shor code, and that

X is independent of and commutes with

the generators of the Shor code, and anti-commutes with

Exercise 10.49

Use Theorem 10.8 to veirfy that the ﬁve qubit code can protect against an arbitrary single qubit error.

Exercise 10.50

Show that the ﬁve qubit code saturates the quantum Hamming bound, that is, it satisﬁes the inequality

of (10.51) with equality.

Exercise 10.51

Verify that the check matrix deﬁned in (10.106) corresponds to the stabilizer of the CSS code

CSS(C

, C

), and use Theorem 10.8 to show that arbitrary errors on up to t qubits may be corrected by

this code.

Exercise 10.52

Verify by direct operation on the codewords that the operators of (10.107) act appropriately, as logical Z

and X.

138

Exercise 10.53

Prove that the encoded Z operators are independent of one another.

Exercise 10.54

Prove that with the check matrix for the encoded X operators deﬁned as above, the encoded X operators

are idnependent of one another and of the gnerators, commute with the gnerators of the stabilizer, with

each other, and

commutes with all the

except with

, with which it anti-commutes.

Exercise 10.55

Find the

X operator for the standard form of the Steane code.

Exercise 10.56

Show that replacing an encoded X or Z operator by g times that operator, where g is an element of the

stabilizer, does not change the action of the operator on the code.

Exercise 10.57

Give the check matrices for the ﬁve and nine qubit codes in standard form.

Exercise 10.58

Verify that the circuits in Figures 10.13–10.15 work as described, and check the claimed circuit equiva-

lences.

139

Exercise 10.59

Show that by using the identities of Figures 10.14 and 10.15, the syndrome circuit of Figure 10.16 can be

replaced with the circuit of Figure 10.17.

Exercise 10.60

Construct a syndrome measuring circuit analogous to that in Figure 10.16, but for the nine and ﬁve qubit

codes.

Exercise 10.61

Describe explicit recovery operations E

†

corresponding to the diﬀerent possible error syndromes that may

be measured using the circuit in Figure 10.16.

Exercise 10.62

Show by explicit construction of generators for the stabilizer that concatenating an [n

, 1] stabilizer code

with an [n

, 1] stabilizer code gives an [n

, 1] stabilizer code.

Exercise 10.63

Suppose U is any unitary operation mapping the Steane code into itself, and such that U

†

X and

†

Z. Prove that up to a global phase the action of U on the encoded states |0

⟩ and |1

⟩ is

⟩ 7→ (|0

⟩ + |1

⟩)/

√

2 and |1

⟩ 7→ (|0

⟩ − |1

⟩)/

√

Exercise 10.64: Back propogation of errors

It is clear that an X error on the control qubit of a CNOT gate propagates to the target qubit. In addition,

it turns out that a Z error on the target propagates back to the control! Show this using the stabilizer

formalism, and also directly using quantum circuit identities. You may ﬁnd Exercise 4.20 on page 179

useful.

140

Exercise 10.65

An unknown qubit in the state |ψ⟩ can be swapped with a second qubit which is prepared in the state |0⟩

using only two controlled-NOT gates, with the circuit

Show that the two circuits below, which use only a single CNOT gate, with measurement and a classically

controlled single qubit operation, also accomplish the same task:

Exercise 10.66

One way to implement a π/8 gate is to ﬁrst swap the qubit state |ψ⟩ you wish to transform with some

unknown state |0⟩, then to apply a π/8 gate to the resulting qubit. Here is a quantum circuit which does

that:

Doing this does not seem particularly useful, but actually it leads to something which is! Show that by

using the relations T X = exp



−iπ/4



SX and T U = UT (U is the controlled-NOT gate, and T acts on

the control qubit) we may obtain the circuit of Figure 10.25.

Exercise 10.67

Show that the following circuit identities hold:

141

Exercise 10.68: Fault-tolerant Toﬀoli gate construction

A procedure similar to the above sequence of exercises for the π/8 gate gives a fault-tolerant Toﬀoli gate.

(1) First, swap the three qubit state |xyz⟩ you wish to transform with some known state |000⟩, then

apply a Toﬀoli gate to the resulting qubits¿ Show that the following circuit accomplishes this task:

(2) Using the commutation rules from Exercise 10.67, show that moving the ﬁnal Toﬀoli gate all the

way back to the left side gives the circuit

(3) Assuming the ancilla preparation shown in the leftmost dotted box can be done fault-tolerantly,

show that this circuit can be used to give a fault-tolerant implementation of the Toﬀoli gate using

the Steane code.

Exercise 10.69

Show that a single failure anywhere in the ancilla preparation and veriﬁcation can lead to at most one X

or Y error in the ancilla output.

Exercise 10.70

Show that Z errors in the ancilla do not propagate to aﬀect the encoded data, but result in an incorrect

measurement result being observed.

142

Exercise 10.71

Verify that when M = e

−iπ/4

SX the procedure we have described gives a fault-tolerant method for

measuring M.

Exercise 10.72: Fault-tolerant Toﬀoli ancilla state construction

Show how to fault-tolerantly prepare the state created by the circuit in the dotted box of exercise 10.68,

that is,

|000⟩ + |010⟩ + |100⟩ + |111⟩

You may ﬁnd it helpful to ﬁrst give the stabilizer generators for this state.

Exercise 10.73: Fault-tolerant encoded state construction

Show that the Steane code encoded |0⟩ state can be constructed fault-tolerantly in the following manner.

(1) Begin with the circuit of Figure 10.16, and replace the measurement of each generator, as shown in

Figure 10.30, with each ancilla qubit becoming a cat state |00 . . . 0⟩ + |11 . . . 1⟩, and the operations

rearranged to have their controls on diﬀerent qubits, so that errors do not propagate within the code

block.

(2) Add a stage to fault-tolerantly measure Z.

(3) Calculate the error probability of this circuit, and of the circuit when the generator measurements

are repeated three times and majority voting is done.

(4) Enumerate the operations which should be performed conditioned on the measurement results and

show that they can be done fault-tolerantly.

Exercise 10.74

Construct a quantum circuit to fault-tolerantly generate the encoded |0⟩ state for the ﬁve qubit code

(Section 10.5.6).

Problem 10.1

Channels E

and E

are said to be equivalent if there exist unitary channels U and V such that E

U ◦ E

◦ V.

(1) Show that the relation of channel equivalence is an equivalence relation.

(2) Show how to turn an error-correcting code for E

into an error-correcting code for E

. Assume

that the error-correction procedure for E

is performed as a projective measurement followed by a

conditional unitary operation, and explain how the error-correction procedure for E

can be performed

in the same fashion.

143

Solution

Concepts Involved: Unitary operators, Quantum Channels, Quantum Measurement.

Recall that a unitary channel is a quantum channel such that U(ρ) = UρU

†

for a unitary operator U.

(1) Reﬂexivity. Take U = V = I (the identity channel, which is unitary). Then E = I ◦E ◦I so E ∼ E

as desired.

Symmetry. Suppose E

∼ E

. Then there exists U, V such that E

= U ◦E

◦V. It then follows that

= U

†

◦E

◦V

†

, where † denotes the dual channel, i.e. if U(ρ) = UρU

†

then U

†

(ρ) = U

†

ρU. The

dual channel of a unitary channel is also a unitary channel as U

†

is unitary for unitary U. Hence

∼ E

as desired.

Transitivity. Suppose E

∼ E

and E

∼ E

. Then there exist U, V, U

′

, V

′

such that E

= U ◦E

◦V

and E

= U

′

◦ E

◦ V

′

. It then follows that E

= U

′

◦ U ◦ E

◦ V ◦ V

′

and since the composition

of two unitary channels is another unitary channel (as the composition of two unitary operators is

again unitary), it follows that E

∼ E

as desired.

We have therefore shown that channel equivalence is an equivalence relation.

(2) Suppose that E

= U ◦ E

◦ V. If the error correcting code for E

consists of a projective measure-

ment P

followed by a conditional unitary C

(where the subscript denotes a conditioning on the

measurement outcome m), this means that for a given state ρ which lies in the support of the code

that C

(ρ)P

†

∝ ρ.

If we instead have E

as our noise channel, let us rotate the measurement basis and carry out the

measurement P

′

= UP

†

(note that a unitary conjugation of a projector remains a projector, as

′2

= (UP

†

)

= UP

†

= UP

†

= P

′

). Let us also modify the conditional unitary

to be C

′

= V

†

. We then have:

′

(ρ)P

′

′†

= (V

†

)(UP

†

)UE

(V ρV

†

(UP

†

)(V

†

)

†

= V

†

(V ρV

†

= V

†

(V ρV

†

∝ V

†

V ρV

†

= ρ

which shows that the error-correction procedure for E

can be performed in the same fashion (with

the unitary-modiﬁed measurements/unitaries).

Problem 10.2: Gilbert–Varshamov bound

Prove the Gilbert-Varshamov bound for CSS codes, namely, that an [n, k] CSS code correcting t errors

exists for some k such that

≥ 1 − 2H





As a challenge, you may like to try proving the Gilbert–Varshamov bound for a general stabilizer code,

144

namely, that there exists an [n, k] stabilizer code correcting errors on t qubits, with

≥ 1 −

2 log(3)t

− H





Problem 10.3: Encoding stabilizer codes

Suppose we assume that the generators for the code are in standard form, and that the encoded Z and

X operators have been constructed in standard form. Find a circuit taking the n × 2n check matrix

corresponding to a listing of all the generators for the code together with the encoded Z operations from

G =







0 0 0 I 0 0

0 0 0 0 I 0

0 0 0 0 0 0







to the standard form







I A

B 0 C

0 0 0 D I E

0 0 0 A

0 I







Problem 10.4: Encoding by teleportation

Suppsoe you are given a qubit |ψ⟩ to encode in a stabilizer code, but you are not told anything about how

|ψ⟩ was constructed: it is an unknown state¿ Construct a circuit to perform the encoding in the following

manner:

(1) Explain how to fault-tolerantly construct the partially encoded state

|0⟩|0

⟩ + |1⟩|1

⟩

√

by writing this as a stabilizer state, so it can be prepared by measuring stabilizer generators.

(2) Show how to fault-tolerantly perform a Bell basis measurement with |ψ⟩ and the unencoded qubit

from this state.

(3) Give the Pauli operations which you need to ﬁx up the remaining encoded qubit after this measure-

ment, so that it becomes |ψ⟩, as in the usual quantum teleportation scheme.

Compute the probability of error of this circuit. Also show how to modify the circuit to perform fault-

tolerant decoding.

Problem 10.5

Suppose C(S) is an [n, 1] stabilizer code capable of correcting errors on a single qubit. Explain how a

fault-tolerant implementation of the controlled-NOT gate may be implemented between two logical qubits

encoded using this code, using only fault-tolerant stabilizer state preparation, fault-tolerant measurement

of elements of the stabilizer, and normalizer gates applied transversally.

145

A1 Notes on basic probability theory

Exercise A1.1

Prove Bayes’ rule.

Solution

Concepts Involved: Probability, Conditional Probability.

Recall that conditional probabilities were deﬁned as:

P (Y = y|X = x) =

P (X = x, Y = y)

P (X = x)

and also recall that Bayes’ rule is given by:

p(x|y) = p(y|x)

p(x)

p(y)

By the deﬁnition of conditional probability:

p(y|x)

p(x)

p(y)

p(X = x, Y = y)

p(x)

p(y)

P (X = x, Y = y)

p(y)

= p(x|y)

Exercise A1.2

Prove the law of total probability.

Solution

Concepts Involved: Probability, Conditional Probability.

Recall that the law of total probability is given by:

p(y) =

p(y|x)p(x)

Using the identity p(Y = y) =

p(X = x, Y = y) and Bayes’ rule, we have

p(y) =

p(x, y) =

p(y|x)p(x)

Exercise A1.3

Prove that there exists a value of x ≥ E(X) such that p(x) > 0.

146

Solution

Concepts Involved: Probability, Expectation.

Recall that the expectation of a random variable X is deﬁned by:

E(X) =

p(x)x

Let ˜x = max {x

x is a possible value of X}. This maximum exists as we assume X can only take on a

ﬁnite set of values. We therefore have that:

E(X) =

p(x)x ≤

p(x)˜x = ˜x

p(x) = ˜x

Where in the last equality we use that the sum over all probabilities must be 1.

Exercise A1.4

Prove that E(X) is linear in X

Solution

Concepts Involved: Probability, Expectation.

Let a, b ∈ R and X, Y be random variables. We then have that:

E(aX + bY ) =

p(x, y)(ax + by)

p(x, y)ax +

p(x, y)by

= a





p(x, y)





x + b

p(x, y)

= a

p(x)x + b

p(y)y

= aE(X) + bE(y)

which shows that expectation is linear.

Exercise A1.5

Prove that for independent random variables X and Y , E(XY ) = E(X)E(Y ).

Solution

Concepts Involved: Probability, Expectation, Independent Random Variables.

147

Recall two random variables X, Y are independent if

p(X = x, Y = y) = p(X = x)p(Y = y)

We have that:

E(XY ) =

xyp(x, y) =

xyp(x)p(y) =

p(x)x





p(y)y





= E(x)E(y)

Exercise A1.6

(∗) Prove Chebyshev’s inequality.

Solution

Concepts Involved: Probability, Expectation, Variance.

Recall the deﬁnition of the variance and standard deviaiton of a random variable X:

Var(X) = E[(X − E(X))

], ∆(X) =

Var(X)

Also, recall that Chebyshev’s inequality reads:



X − E(X)



≥ λ∆(X)) ≤

where λ > 0.

We ﬁrst establish Markov’s inequality for the expectation value E(X). Let a > 0, and then we have that:

E(X) =

xp(x) =

x≥a

xp(x) +

x<a

xp(x) ≥

x≥a

ap(x) + 0 = ap(X ≥ a)

Therefore, we obtain that:

p(X ≥ a) ≤

E(X)

for any random variable X and a > 0. Next, substitute X with (X − E(X))

and let a = λ

Var(X) for

λ > 0. Markov’s inequality then states that:

p((X − E(X))

≥ λ

Var(X)) ≤

E(X − E(X))

Var(X)

Since E(X − E(X))

= Var(X), we have that:

p((X − E(X))

≥ λ

Var(X)) ≤

148

If λ > 0, then p((X − E(X))

≥ λ

Var(X)) = p(



X − E(X)



≥ λ∆(X)) by taking square roots, so we

obtain:



X − E(X)



≥ λ∆(X)) ≤

as desired.

149

A2 Group theory

Exercise A2.1

Prove that for any element of g of a ﬁnite group, there always exists a positive integer r such that g

= e.

That is, every element of such a group has an order.

Solution

Concepts Involved: Group Axioms, Order.

Suppose G is a ﬁnite group, and g ∈ G. Then, there exists some r

, r

∈ N such that r

̸= r

and

= g

. If this was not the case, then g

would be unique for each n ∈ N, contradicting the ﬁniteness

of G. WLOG take r

< r

, and let r = r

− r

∈ N. Using associativity, we then have that:

= g

from which we conclude that g

= e.

Exercise A2.2

Prove Lagrange’s Theorem.

Solution

Concepts Involved: Group Axioms, Subgroups, Order, Equivalence Relations.

Let H be a subgroup of a group G and deﬁne the relation ∼ by a ∼ b iﬀ a = bh for some h ∈ H. ∼

is reﬂexive as a = ae (so a ∼ a) where e ∈ H is the identity element. ∼ is symmetric as if a ∼ b, then

a = bh for some h ∈ H so b = ah

−1

(so b ∼ a) where h

−1

∈ H as H is closed under inverses. Finally ∼

is transitive as if a ∼ b and b ∼ c, there exist h

, h

∈ H such that a = bh

and b = ch

so a = ch

As h

∈ H (H is closed under multiplication) it follows that a ∼ c. Having shown ∼ to have these

three properties, we conclude it is an equivalence relation. Then, the equivalence classes of ∼ partition

G, where the equivalence class of g ∈ G is [g] =



gh|h ∈ H



Now, let g ∈ G and deﬁne the map φ

H → [g] as φ

(h) = gh. φ

is injective as if φ

) = φ

)

then gh

= gh

and multiplying by g

−1

on both sides h

= h

. φ

is surjective as if k ∈ [g], then there

exists some h ∈ H such that k = gh by the deﬁnition of ∼. Hence φ

is bijective.

As per our prior observation, the equivalence classes of ∼ partition G, so G =

i=1

] and |G| =



i=1

]



i=1



]



. Further, there is a bijection φ

from each equivalence class to H, so



]



= |H|

for all i. Thus |G| =

i=1

|H| = nH and hence |H| divides |G|, as desired.

Exercise A2.3

Show that the order of an element g ∈ G divides |G|.

150

Solution

Concepts Involved: Group Axioms, Subgroups, Order, Lagrange’s Theorem.

Let g ∈ G with order r. Then, deﬁne H =



|n ∈ N



. We claim that H is a subgroup of G. First, g

∈ G

for any n as G is closed under multiplicaton, so H ⊂ G. Next, if g

, g

∈ H then g

·g

= g

∈ H.

Associativity is inherited from the associativity of multiplication in G. Since g

= e ∈ H, H contains the

identity. Finally, for g

∈ H we have g

r−k

∈ H such that g

r−k

= g

r−k

= g

= e so H is closed

under inverses. Hence the claim is proven.

Next, we observe that |H| = r as H contains the r elements e, g, g

, . . . g

r−1

. Hence by Lagrange’s

Theorem r divides |G|.

Exercise A2.4

Show that if y ∈ G

then G

= G

Solution

Concepts Involved: Group Axioms, Conjugacy Classes

Suppose y ∈ G

. Then there exists some g ∈ G such that g

−1

xg = y. Multiplying both sides on the left

by g and on the right by g

−1

we ﬁnd that x = gyg

−1

. We now show the two inclusions.

⊆

Suppose that k ∈ G

. Then there exists some g

′

∈ G such that k = g

′−1

′

. Then using x =

gyg

−1

we ﬁnd k = g

′−1

gyg

−1

′

. Now, g

−1

′

∈ G (by closure) and it has inverse g

′−1

g, and hence

k = g

′−1

gyg

−1

′

∈ G

. So, G

⊆ G

⊇ Suppose that l ∈ G

. Then there exists some g

′′

∈ G such that l = g

′′−1

′′

. Then with g

−1

xg = y

we ﬁnd l = g

′′−1

−1

xgg

′′

. Much like before, gg

′′

∈ G (by closure) with inverse g

′′−1

−1

so l ∈ G

. So,

⊆ G

We conclude that G

= G

Exercise A2.5

Show that if x is an element of an Abelian group G, then G

= {x}.

Solution

Concepts Involved: Abelian Groups, Conjugacy Classes.

Evidently x = e

−1

xe ∈ G

so {x} ⊆ G

. Next, if k ∈ G

then k = g

−1

xg for some g ∈ G, but since G

is abelian, g

−1

x = xg

−1

so k = xg

−1

g = xe = x so k ∈ {x} and hence G

⊆ {x}. We conclude that

= {x}.

Exercise A2.6

Show that any group of prime order is cyclic.

151

Solution

Concepts Involved: Order, Cyclic Groups.

Suppose |G| = p where p is prime. Since G is ﬁnite, every element of G has an order by Exercise A2.1.

Since the order of any element g ∈ G divides |G| = p by Exercise A2.3, and since p is prime, the order of

g is either 1 or p. Since |G| > 1, there exists at least one g ∈ G with order p, and this g is a generator

of G (with g

= g, g

, g

, . . . , g

= e distinct and comprising all the elements of G. In fact this is true of

any non-identity g). Hence G is cyclic.

Exercise A2.7

Show that every subgroup of a cyclic group is cyclic.

Solution

Concepts Involved: Group Axioms, Subgroups, Cyclic Groups, Euclid’s Division Algorithm.

First we prove a necessary Lemma, namely that any nonempty subset of the natural numbers contains a

least element. We show this by proving the contrapositive. Suppose that A ⊆ N has no least element.

Then 1 /∈ A as then 1 would be the least element. Suppose then that 1, . . . k − 1 /∈ A; then k /∈ A as

then k would be the least element. By strong induction, there exists no k ∈ N such that k ∈ A, i.e. A is

empty. This concludes the proof of the lemma.

Let G = ⟨a⟩ be a cyclic group and H a subgroup of G. If H = {e}, it is trivially cyclic and we are

done. If H ̸= {e}, then there exists some a

∈ H with n ̸= 0. Since H is closed under inverses,

)

−1

= a

−n

∈ H as well which ensures that H contains some positive power of a. Then consider

the set A =



k ∈ N|a

∈ H



. Any nonempty subset of the naturals has a minimum element; therefore

let d = min A. It is immediate that





is a subgroup of H as a

∈ H and H is a group. To show

the reverse containment, suppose that g ∈ H. Since H is a subgroup of the cyclic G, it follows that

g = a

for some p ∈ Z. We can then write p = qd + r for 0 ≤ r < d by Euclid’s Division algorithm

(see Appendix 4). We then have that a

= a

p−qd

= a

)

−q

∈ H by closure. Now, since d is the least

positive integer for which a

∈ H and 0 ≤ r < d, it must follow that r = 0. Therefore, p = qd and hence

= (a

)

∈





. So, H is a subgroup of





. We conclude that H =





and hence H is cyclic.

Exercise A2.8

Show that if g ∈ G has ﬁnite order r, then g

= g

if and only if m = n (mod r).

Solution

Concepts Involved: Order, Modular Arithmetic, Euclid’s Division Algorithm

Suppose g ∈ G has ﬁnite order r.

⇐= First suppose that m = n (mod r). Then m − n = kr for some k ∈ N. Therefore g

m−n

= g

But g

= (g

)

= e

= e, so g

m−n

= g

−n

= e, and multiplying both sides by g

we ﬁnd g

= g

=⇒ Suppose g

= g

. Then multiplying both sides by g

−n

we ﬁnd g

m−n

= e. By Euclid’s Division

algorithm there exist integers q, p such that m − n = qr + p with 0 ≤ p < r. We then have that

152

m−n

= g

qr+p

= g

= e. Furthermore, g

= (g

)

= e

= e so g

= e. But since g has order r and

0 ≤ p < r, it follows that p = 0. Hence m − n = qr and so m ≡ n (mod r).

Exercise A2.9

Cosets deﬁne an equivalence relation between elements. Show that g

, g

∈ G are in the same coset of

H in G if and only if there exists some h ∈ H such that g

= g

Solution

Concepts Involved: Equivalence Relations, Cosets

In Exercise A2.2 we showed that the relation ∼ on a group G deﬁned by g

∼ g

iﬀ g

= g

h for some

h ∈ H was an equivalence relation. The equivalence classes of this equivalence relation were



gh|h ∈ H



i.e. precisely the left cosets of H in G. So, g

, g

are in the same coset of H in G if and only if g

= g

for some h ∈ H, which is exactly what we wished to show.

Exercise A2.10

How many cosets of H are there in G?

Solution

Concepts Involved: Equivalence Relations, Cosets

We observe that the map φ

H → [g] deﬁned in the solution of Exercise A2.2 is a map from H to a right

coset of H in G deﬁned by g. Since we showed that this map was bijective, this shows that |H| = |Hg|

for any g ∈ G. Furthermore, since the cosets deﬁne an equivalence relation between elements of G, the

cosets of H in G partition G. So, we conclude that there are |G|/|H| cosets of H in G, each of cardinality

|H|.

Exercise A2.11: Characters

Prove the properties of characters given above.

Solution

Concepts Involved: Matrix Groups, Character (Trace)

Recall that the character of a matrix group G ⊂ M

is a function on the group deﬁned by χ(g) = tr(g)

where tr is the trace function. It has the properties that (1) χ(I) = n, (2)



χ(g)



≤ n, (3)



χ(g)



= n

implies g = e

iθ

I, (4) χ is constant on any given conjugacy class of G, (5) χ(g

−1

) = χ

∗

(g) and (6) χ(g)

is an algebraic number for all g.

The six properties are proven below.

(1) χ(I) = tr(I) =

k=1

1 = n.

(2) Let g ∈ G. Since G is ﬁnite, by Exercise A2.1 it follows that g has order r such that g

= I. So,

g may be diagonalized with roots of unity e

2πij/r

, j ∈ {0, 1, . . . , r − 1} on the diagonal. We then

153

ﬁnd using the triangle inequality that:



χ(g)



tr(g)



k=1

2πij



≤

k=1



2πij



1 = n

which proves the claim.

(3) The (complex) triangle inequality |z

+ z

| ≤ |z

|+ |z

| is saturated when z

= kz

for some k ≥ 0.

This can only occur in the above equation when every λ

in the sum is identical (as distinct roots

of unity are not related by a non-negative constant). If the λ

s are identical, then g is diagonal with

diagonal entries of unit modulus, so g = e

iθ

I as claimed.

(4) Let G



−1

xg|g ∈ G



be the conjugacy class of x in G. We then have for any h ∈ G

that

χ(h) = χ(g

−1

xg) = tr



−1



= tr



xgg

−1



= tr(xI) = tr(x), using the cyclicity of the trace. We

conclude that χ is constant on the conjugacy class.

(5) By the same argument as (2), g ∈ G can be diagonalized with roots of unity e

2πij/r

on the diagonal:

g =







2πij







It then follows that g

−1

is:

−1







−2πij







So we have that:

χ(g

−1

) = tr



−1



j=1

−2πij

j=1

2πij

)

∗





j=1

2πij





∗

= (tr(g))

∗

= χ

∗

(g).

which proves the claim.

(6) χ(g) is the sum of r-th roots of unity, which are algebraic; hence χ(g) is algebraic as the sum of

algebraic numbers.

Exercise A2.12: Unitary matrix groups

(∗) A unitary matrix group is comprised solely of unitary matrices (those who which satisfy U

†

U = I).

Show that every matrix group is equivalent to a unitary matrix group. If a representation of a group

consists entirely of unitary matrices, we may refer to it as being a unitary representation.

154

Solution

Concepts Involved: Matrix Groups, Character (Trace), Equivalence, Unitary Operators.

Recall that two groups are equivalent if they are isomorphic (i.e. there is a bijection between the groups

that respects the group multiplication) and the isomorphic element have the same character.

Let G = {A

, . . . A

} be a ﬁnite matrix group. Then deﬁne

A =

i=1

†

By Ex. 2.25 each term of the above sum is positive, and by Ex. 2.24 each term is Hermitian. The sum

of Hermitian operators is Hermitian, so A is Hermitian. By Ex. 2.21, A is diagonalizable. Let U be the

unitary matrix that diagonalizes A. We then have that D is a diagonal matrix, with:

D = UAU

†

Let D

1/2

be the matrix obtained by taking the square root of the diagonal entries of D. Then deﬁne

T = D

1/2

U. We then claim that G

= {V

, . . . V

} is a unitary matrix group equivalent to G, where:

= T A

−1

We have three points to verify; (i) That the V

s are unitary, (ii) That φ

G → G

deﬁned by φ(A

) =

T A

−1

= V

is an isomorphism, and (iii) that the characters of A

and V

are equivalent.

(i) For any V

, we have:

†

= (T A

−1

)

†

(T A

−1

)

= (D

1/2

†

−1/2

)

†

1/2

†

−1/2

)

= (D

−1/2

†

1/2

)(D

1/2

†

−1/2

)

= (D

−1/2

†

)D(UA

†

−1/2

)

= (D

−1/2

†

)(UAU

†

)(UA

†

−1/2

)

= (D

−1/2

†

)A(A

†

−1/2

)

= (D

−1/2

†

)





j=1

†





†

−1/2

)

= D

−1/2





j=1

)

†

)





†

−1/2

= D

−1/2





k=1

†





†

−1/2

= D

−1/2

UAU

†

−1/2

= D

−1/2

= I

155

Where in the sixth equality we use the unitarity of U, and in the ninth equality we use that A

= A

iterates over all the group elements as A

iterates over all the group elements. To see that this

is the case, it suﬃces to show that the map ψ

→ M

deﬁned by ψ

) = A

a bijection. To see that it is injective, suppose that ψ

) = ψ

). Then it follows that

= A

, and multiplying on the left by A

−1

(which exists) we ﬁnd that A

= A

. To

see that it is surjective, suppose that A

′

∈ M

. Then, there exists A

′

−1

∈ M

such that

′

−1

) = A

′

−1

= A

′

. We conclude that ψ

is bijective.

(ii) Firstly, φ is a homomorphism as for any A

, A

we have:

φ(A

)φ(A

) = V

= T A

−1

T A

−1

= T A

−1

= φ(A

Next, φ is surjective by construction. Finally, it is injective; suppose that V

= V

. Then we have

that:

T A

−1

= T A

−1

And multiplying both sides on the left by T

−1

on the left and T on the right we ﬁnd that A

= A

Hence we conclude that φ is a bijective homomorphism and hence an isomorphism.

(iii) This is immediate from the cyclicity of the trace:

χ(V

) = tr



T A

−1



= tr



−1

T A



= tr(A

) = χ(A

The claim is therefore proven.

Exercise A2.13

Show that every irreducible Abelian matrix group is one dimensional.

Exercise A2.14

Show that if ρ is an irreducible representation of G, then |G|/d

is an integer.

Exercise A2.15

Using the Fundamental Theorem, prove that characters are orthogonal, that is:

i=1

(χ

)

∗

= |G|δ

and

p=1

(χ

)

∗

|G|

where p, q, and δ

have the same meaning as in the theorem and χ

is the value the character of the

pth irreducible representation takes on the ith conjugacy class of G and r

is the size of the ith conjugacy

class of G and r

is the size of the ith conjugacy class.

156

Exercise A2.16

is the group of permutations of three elements. Suppose we order these as mapping 123 to:

123;231;312;213;132, and 321, respectively. Show that there exist two one-dimensional irreducible repre-

sentations of S

, one of which is trivial, and the other of which is 1,1,1,-1,-1,-1, corresponding in order to

the six permutations given earlier. Also show that there exists a two dimensional irreducible representation,

with the matrices

1 0

0 1

−1 −

√

3 −1

−1

√

−

√

3 1

−1 0

0 1

√

3 −1

1 −

√

−

√

3 1

Verify that the representations are orthogonal.

Exercise A2.17

Prove that the regular representation is faithful.

Exercise A2.18

Show that the character of the regular representation is zero except on the representation of the identity

element, for which χ(I) = |G|.

Exercise A2.19

Use Theorem A2.5 to show that the regular representation contains d

instances of each irreducible

representation ρ

. Thus, if R denotes the regular representation, and

G denotes the set of all inequivalent

irreducible representations, then:

ρ∈G

Exercise A2.20

The character of the regular representation is zero except for the conjugacy class i containing e, the

identity element in G. Show, therefore, that

ρ∈G

(g) = Nδ

Exercise A2.21

Show that

ρ∈

= |G|.

Exercise A2.22

Substitute (A2.10) into (A2.9) and prove that

f(ρ) is obtained.

157

Exercise A2.23

Let us represent an Abelian group G by g ∈ [0, N − 1], with addition as the group operation, and deﬁne

(g) = exp



−2πigh/N



at the h representation of g. This representation is one-dimensional, so d

= 1.

Show that the Fourier transform relations for G are

f(h) =

√

N−1

g=0

f(g)e

−2πigh/N

and f(h) =

√

N−1

g=0

f(g)e

2πigh/N

Exercise A2.24

Using the results of Exercise A2.16, construct the Fourier transform over S

and express it as a 6x6 unitary

matrix.

158