Quantum Information Processing

2009 version, Ivan Damgård

For students who consider taking this course: have a look here for additional information and questions/answers

This is the home page of the course in Quantum Information Processing.

The course runs the entire semester (both quaters). See below for contents of course.

Time and Place

Monday 12-14, Shannon 157

Thursday 12-14, Shannon 157

Weekly Updates and Exercises

Slides on QKD updated.

Additional info on Exam added below.

Documentation

Will consist of hand-in exercises during the course. There will probably be about 11-12

of them. You need to collect at least 9 points:

Handing in a correct exercise gives 1 point

Handing a partially correct one gives 1/2 point, you can hand in later and get another 1/2 point

Handing in nothing or nonsense gives 0 points, you can hand in later, but this will give at most 1/2 point.

The course ends with an oral exam.

Course Material

Nielsen and Chuang: Quantum Computation and Quantum Information
QIP Exercises (revised November 18)
Ivan Damgård: Quantum Mechanics Quick Reference (revised December 3)
Brassard, Høyer, Mosca and Tapp: Quantum Amplitude Amplification and Estimation
Ivan Damgård: Note on Quantum Fourier Transforms

Salvail: Slides on Quantum Information theory

Salvail: Slides on CSS codes

Salvail: Slides on QKD (updated December 22)

More material, such as course notes and papers, will be added here as we move along,

in case we have it available electronically.

Background Material

Course Plan

We will be covering the following main points in roughly the order listed.

Basic Quantum Mechanics, qbits and operations
Simple quantum computing, basic complexity classes
More advanced algorithmics

Hidden subgroups (factoring and discrete log)
Quantum searching and amplitude amplification
Lower bounds

Quantum information theory and error correction
Quantum Cryptography

Quantum key distribution
Bit Commitment and Oblivious Transfer

On the Exam

You will draw one of 6 subjects at random, and should prepare to talk about

the subject you get in about 20 minutes. The default is that as long as you talk

about something that is relevant to the subject and makes sense, we will not

stop you, so the more you can say, the less time we have for unpleasant

questions...

You may bring any material you want to the exam. Please note that it is

not a competition in learning by heart, we want to hear about your understanding

of the subject. So you may look at your notes while you speak, but do not

take this to the point where you read from a manuscript, this is not a good idea.

Remember to use the board, it's very important to write stuff that can help you

remember where you are, and help us remember what you said.

The list below of the subjects also contains some suggestions of what you might

talk about. But it is NOT meant to say that you have to cover everything. In fact

that is probably not possible.

Exam subjects

Quantum circuits and basic algorithms

The quantum circuit model, elementary gates
Quantum circuits are as powerful as classical
Quantum circuits can approximate any unitary mapping
The Deutch-Josza algorithm

Quantum Search

The unordered search problem, the classical complexity

Grover's algorithm, interpretation as a rotation, complexity
Quantum lower bound for unordered search
The lower bound technique based on polynomials

The quantum Fourier Transform

The quantum Fourier transform, definition, proof it is unitary
Basic Fourier algorithm to find period for a function given multiple of period
Fourier Sampling
Connection between factoring and period finding
Finding the period in general

Quantum Error Correction

Quantum operations, operator sum formalism as model for transmission errors
The Shor code
Correction for bit, phase flips or both enough to correct anything
The CSS codes

The Lo-Chau QKD Protocol

Outline of the protocol, model for communication
Getting a state close to the EPR state is enough:
The Holevo bound (only result is curriculum)
Large Fidelity implies low entropy
Small number of errors means you get exactly the EPR state
Test for errors implies number of errors is low with high probability

The BB84 QKD protocol

Outline of the starting point: (modified) Lo-Chau, model for communication
Alice decides on check bits and v_k, x,z in the beginning, results in CSS code prot.
Alice doesn't need to send z, if z removed, state she sends can be prepared easily
Simple manipulations using that x is random results in "almost BB84"
Send twice the number of qubits, Bob guesses bases to use to remove need to store qubits