Introduction to Quantum Computation, Winter Semester 2003/4
Generalities
Who/where:
Course meetings: 
Fridays, 14:0016:00 
IFW A32 
Exercise session: 
Fridays, 16:0017:00 
IFW A32 
References:
Recommended text: 
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang
Cambridge University Press, 2000
errata in various forms can be found here
can be purchased from Amazon.de by following this link.
(to be referred to as [NC]) 
An online text: 
Preskill's Lecture Notes
John Preskill (Caltech), 19978
[very good, from a physicsoriented direction]
(to be referred to as [P]) 
And another: 
Lecture Notes on Quantum Computing
Mark Oskin (University of Washington), 2002
[largely similar to [NC], but it's online!]
(to be referred to as [O])

An online reference on abstract algebra and
number theory: 
A Computational Introduction to Number Theory and Algebra
Victor Shoup (New York University), 2002
[Concise, beautiful, exactly what one needs.]
(to be referred to as [S])

Outline
Week 1: 
Introduction, baby QM and advertisement
 References:
 Chapter 1 of [P], online here
 Chapter 1 of [NC]
 There are many popular accounts, such as:
 Topics:
 Turing machines go quantum: computation with unitary gates
and state vectors
 Simon's problem (at least, the beginning)

Week 2: 
Better QM and some mathematical background
 References for the basic mathematics:
 §2.1 of [NC] is quite good
 A very basic online resource
 Topics:
 Some linear algebra over the complex numbers
 complex vector spaces and inner products
 linear transformations and their adjoints
 Hermitian and unitary operators/matrices
 tensor products of vector spaces
 simplified postulates of QM  measurement with respect
to the computational basis
 qubits, gates, circuits
 Deutsch's problem
 making invertible unitary gates from noninvertible
boolean functions

Week 3: 
More QM, more mathematics and notation, more sophisticated
measurements
 References:
 §2.2 of [NC]
 §§2.12.4 of [O]
 An entire course on quantum mechanics can
be found here;
it includes sections on basic
linear algebra and the postulates of QM, but
talks more about wave functions than we will
ever need.
 [If you like wave functions in quantum
mechanics, check out the movies at the
web site of
the book Visual Quantum
Mechanics]
 Topics:
 unitary operators as changes of o.n.b.
 dual spaces, more tensor products
 the linear algebra definition of "entanglement"
 projections in the "ketbra" form
 the spectral theorem for Hermitian operators
 EPR pairs and their repeated measurements
(without fasterthanlight communication)
 the Pauli gates X, Y and Z and Hadamard H
 the CNOT gate, general "controlled gates"
 measuring the first of a pair of qubits
 Homework I:

Week 4: 
First sophisticated applications  beam me up, Scotty, it's
very
uncertain down here!
 References:
 §§1.3.7 and 2.2.5 and Boxes 2.1 and 2.4 of [NC]
 here is
a good page about the Uncertainty Principle (and
here is a
very typical, very bad page)
 Topics:
 tensor products of linear transformations
 teleportation
 commutator, anticommutator
 expectation (mean), variance, standard deviation
 The CauchySchwarzBunyakovsky inequality
 the expectation of a measurement when in a given state
 The Heisenberg Uncertainty Principle
 Homework II:

Week 5: 
Next sophisticated applications, circuits and gates
 References:
 §§1.3.5, 2.3, 4.5 of [NC]
 Topics:
 The Nocloning Theorem
 the statement
 the proof
 an elementary consequence: no naive eavesdropping!
 Superdense coding
 towards universal families of gates
 density, approximating gates
 Homework III:

Week 6: 
Universal families of gates
 References:
 Topics:
 "twolevel" unitary matrices  many copies of SU(2) in SU(n)
 making a swap out of CNOTs; making coordinate permutations
out of several swaps
 "twolevel unitaries" are universal (Gaussian elimination)
 "single qubit" operations and CNOTs make all "twolevel unitaries"
 T and H give an irrational rotation about an irrational angle
 The standard universal family of gates is:
{Hadamard, phase, CNOT, T=pi/8}
 Homework IV:

Week 7: 
Another universal family of gates; preparing for QECC
 References:
 §§ 4.3, 4.5 and 2.4 of [NC]
 Topics:
 multiplycontrolled gates
 the Toffoli gate
 its role in reversible classical computation  gives
FANOUT and NAND (with preset ancilla)
 {Hadamard, phase, CNOT, Toffoli} is another universal family
 starting density matrices
 definition
 pure vs. mixed
 action by unitaries, measurement
 traces, partial traces
 density matrices on subsystems
 convexity
Homework V:

Week 8: 
Quantum errorcorrecting codes (QECC), part I
 References:
 §2.4, Chapter 8 (especially §8.2) and Chapter 10 of [NC]
 Topics:
 finishing density matrices
 criterion for purity
 relation of mixed states to entanglement
 quantum operations
 generally, unitary evolution of the whole system, measurement
 when unitary evolution acts separately on the computer
and the environment
 operator sum representation
 expanding in a nice basis over one qubit
 the Steane 7bit code
 classically:
 the paritycheck matrix
 codewords
 locating and correcting errors
 quantum version:
 using 3 ancilla qubits to mimic classic error correction
 Homework VI:

Week 9: 
QECC, part II
 References:
 Topics:
 finishing the Steane code 7bit code
 correcting bitflips
 correcting phaseflips
 correcting bit and phaseflips
 some circuits (encoding, decoding, syndrome measurement...)
 some ideas towards faulttolerance
 faulttolerant Toffoli circuit
 the threshold theorem
 Homework VII:


Weihnactsferien 

Week 10: 
Fourier Transforms & the "QFT"
 References:
 Topics:
 characters of groups, the dual group
 the general Fourier transform
 the Fourier transform for Z_{n}
 the "Quantum Fourier transform"
 the definition
 an alternative formula
 a circuit which computes it
 Homework ... see next week

Week 11: 
Phase estimation, order finding, factoring
 References:
 again Chapter 5 of [NC]
 [S], for group and number theory
 Topics:
 the alternate formula for the QFT, again
 Schor's idea for how to use the QFT, onequbit case
 the general circuit to use the QFT with a unitary operator and
an eigenvector  phase estimation
 order finding out of phase estimation
 factoring out of order finding
 Homework VIII:

Week 12: 
CLASS CANCELLED ON FRIDAY, 23 JANUARY 2004 ...
but see the homework
sheet from last week, and look over §§5.4.2 and 5.4.3 to
see applications of the QFT
much like what we did last week (and, if you have time, do the homework
in those sections)

Week 13: 
Q Database search and Q cryptography (the BB84 key exchange
protocol)
 References:
 Chapter 6 and §12.6 of [NC]
 Topics:
 Searching
 "oracle" problems
 Grover's Algorithm, the geometric picture:
 reflections
 products of reflections being rotations
 sufficiently many rotations to get onto the unique solution vector,
or into the solution space, which solutions are not unique
 Cryptography
 onetime pads
 quantize key distribution: BB84
 the protocol  encoding randomly chosen bits with different bases
 most naive attact impossible by the Nocloning Theorem
 another attack  the measure the flying qubit, replace it with
a
new one  and its error rate
 Homework IX:

Week 14: 
Physical systems for QC
 References:
 Topics:
 the DiVincenzo criteria
 Ion traps
 optical QC
 liquidphase NMR QC

Afterward... 
 There will be a final exam
 Between 8am and 10:30am on Wednesday, March 24th
 Contact me
(by email) in case of
scheduling difficulty
 Topics:
 Basically, everything on the above outline
 Be ready to do the exercises
 Be prepared on welldefined specific topics from class, such as
 protocols, their properties and elementary calculations
about them
 repeatedlyused theorems, their statements and proofs
 Feel free to
send me email and/or arrange
(by email) long and
frequent in
person consultations
 Keep in touch with me afterwards if you want contacts in the quantum
computing world, or suggestions for further work or study

