Week 1
We covered the Quick Reference Note up to and including sec. 4.1
Exercises: 1-3 of the "QIP exercise" set.
Week 2
We have covered the Deutch and Deutch-Josza problems, N&C 1.4
also the very beginning of Chapter 4, which we continue on next week.
Exercises:
nr. 4 and 5 from the "QIP exercises" set.
4.16 from N&C
To hand in: 4.20 (only the first part, showing the two circuits are equal)
Week 3
We will cover N&C Chapter 4.1-4.4 (though some details are left out), and a quick overview of 4.5, as well as the quick reference note section 7.
Exercises
4.17,
4.18,
4.24 (if we have time)
To hand in: 4.35 (Section 4.2 of the Quick Ref. note will be useful)
and those who want to impress the teacher can solve and hand in this one as well:
We showed in the lectures that a circuit that needs a classical random bit as input
can be simulated without external randomness, we just apply an H gate to a bit
in classical state |0> and do a measurement. The resulting circuit is not quite in
standard form because a measurement occurs in the middle, where standard form
requires that all measurements are done at the end. Use an additional qubit and a
C-NOT gate to modify the construction so we get an equivalent circuit in standard
form. Exercise 4.35 will probably be useful here.
Week 4
We will start on quantum search algorithms, and will cover N&C 6-6.1, also a little
bit of material from Brassard et al.: Quantum Amplitude Amplification, a paper
you find on the course web page. We may have time to talk also about section 6.6
N&C.
Exercises
6.1
To hand in: 6.2, plus this extra question: assume you search for x, such that f(x)=1, and there
is exactly one such x. Based on the result of 6.2, argue that if you start with an equally weighted
superposition of all x, and apply one Grover iteration, then the amplitude (weight) on the
correct solution is almost 3 times larger than it was before (for large N).
and this one:
prove the claim made on p.251 that Step 3 of Grover's algorithm can be implemented using
O(n) elementary gates. As usual, you can use auxiliary qubits as long as they are returned
to their original state after use.
Week 5
We will cover more lower bound techniques for black-box algorithms, sec. 6.7 of N&C.
If there is additional time, we start on Quantum Fourier Transform, using the note from
the webpage. Next week, we continue with this.
Exercises
6.20 (where I could only prove a bound of N/2)
Exercises 6 from "QIP Exercises" on the web page (document has been expanded)
To hand in, this one:
You are given a function f that maps n bit strings to n bit strings. f is 2-to-1, that is every
image under f has exactly 2 preimages. The problem is to find a collision, i.e.
distinct x,y such that f(x)= f(y). We consider the black-box version of the problem, i.e.
no side information on f is given. Let N= 2^n as usual.
Classically, one can solve the problem by constructing a sorted table L, consisting of
k pairs (x,f(x)) where the x's are random, and check if L contains a collision. By the standard "birthday" argument, this will yield a solution with constant probability if the size of L is a
constant times the square root of N.
Quantumly, we can pick some x and define a function h by: h(y)=1 if y is different from
x and f(y)=f(x), and h(y)=0 otherwise. Then we can use Grover's algorithm to find a y
for which h(y)=1. There is exactly one such y and N candidates, so we need to evaluate
f about square root of N times to find the solution. This needs less memory than the classical
solution, but is not better in terms of running time.
Using a time/space tradeoff, construct a quantum algorithm for finding collisions by combining
the above two approaches, such that you use both time and space a constant times the
third root of N. Note that you will need to change the function h from above, and also that
you may ignore the time needed to sort tables, the only thing that counts for time complexity
is the number of times you call the oracle for f.
Week 6
This week, we go on with the quantum Fourier Transform using the note on the web page.
Exercises
Are all from the note on the Quantum Fourier Transform.
Exercise 1
Exercise 2
To hand in: Exercise 3
Hints about Exercise 3: do not expect to find a "nice" expression as the answer to question 1,
it probably looks ugly to you, but that's fine. Also, you will find it useful to show
that omega_M raised to power M/N equals omega_N.
Week 7
This week, we finish the part on the quantum Fourier Transform. After the autumn break,
we start with general measurements and density matrices, using the quick reference note.
For this week, only a hand-in exercise:
Let G_N be the inverse of the Quantum Fourier transform F_N.
Using the fact that the complex conjugate of omega_N^i is omega_N^(-i), derive
a concrete expression for G_N applied to a basis vector |i>.
Use this result to compare what happens if you apply F_N or G_N to an arbitrary
input state |u> and measure the result. More precisely, measuring F_N |u>
produces a probability distribution Df over the possible classical outcomes in Z_N,
while measuring G_N |u> produces a different distribution Dg.
Show that the probability Dg assigns to j equals the probability Df assigns to -j.
Week 8
This week, we have covered general measurement and some basic facts about
Normal, Hermitian and Positive operators. We have seen an example of a general
measurement that - in a certain sense - does better than any projective measurement.
Thursday, we will look at the density matrix concept and so called quantum
teleportation as an example.
The material is covered in the quick reference note, section 4.3 and 5,
and 1.3.7 (Teleportation).
The quick reference note has been to include a summary on
normal operators and reference to proofs in N&C that the facts on measurements
and density matrices claimed actually follow from the postulates. These proofs
are not part of the curriculum, however.
Exercises - from the revised version of the QIP exercises document
Exercise 7
Exercise 8
To hand in: Exercise 9.
Week 9
This week we cover the partial trace and quantum operations, this is the last part of section 5 and section 6 of the quick reference note, which has been revised. The slides on the webpage on quantum information theory also have material on quantum operations, in particular examples of quantum channels . The material on quantum information theory itself, however, will be postponed until later. The QIP exercises document has been revised again, exercises are from there.
Exercises (note new deadline is Thursday)
To hand in: Exercise 10
Exercise 11
Week 10
This week, we start on Quantum Error Correction and this will continue part of next week. The material we cover can be found in N&C, sections 10-10.2 and 10.4. The last part, on CSS codes, will probably not be covered until next week. In the book, it is mentioned under the code for bit flips that one can determine where and if a bit flip occurred using measurements Z_1Z_2 and Z_2Z_3. These are in fact the measurements we discussed, namely "is the first bit equal to the second?" and "is the second equal to the third?", where measurement result +1 means yes and -1 means no. It is not terribly important that you understand why those two measurements can be written in the form Z_1Z_2, Z_2Z_3, it is much more important to understand what they do.
Exercises
- are from the QIP exercises doc (revised).
Exercise 12
Exercise 13
To hand in: Exercise 14
Week 11
This week we cover CSS codes and the usage of CSS codes for entanglement distillation.
Material: N&C section 10.4.1, 10.4.2, and slides on the course web page.
Exercises
N&C 10.25
to hand in: QIP exercises nr. 15 (recently added to the document)
Week 12
This week, we cover Von Neumann entropy (only the def) , the Holevo bound and
corollary (only the result, not the proof), see the slides on the web page on
quantum information theory and sections 11.3 and 12.1.1 in N&C. We also
covered the Lo-Chau protocol, slides will be put on the web page, see also 12.6.5
from N&C.
Exercise
to hand in: Exercise 16 from the QIP exercises.