Introduction to Quantum Computation, Winter Semester 2003/4

Generalities

Who/where:

Instructor: Jonathan A Poritz (e-mail: jap@zurich.ibm.com)
Course meetings: Fridays, 14:00-16:00 IFW A32
Exercise session: Fridays, 16:00-17: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 on-line text: Preskill's Lecture Notes
John Preskill (Caltech), 1997-8
[very good, from a physics-oriented 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 on-line!]
(to be referred to as [O])
An on-line 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
Week 2: Better QM and some mathematical background
  • References for the basic mathematics:
    • §2.1 of [NC] is quite good
    • A very basic on-line 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 non-invertible
        boolean functions
Week 3: More QM, more mathematics and notation, more sophisticated
measurements
  • References:
    • §2.2 of [NC]
    • §§2.1-2.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 "ket-bra" form
    • the spectral theorem for Hermitian operators
    • EPR pairs and their repeated measurements
      (without faster-than-light 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, anti-commutator
    • expectation (mean), variance, standard deviation
    • The Cauchy-Schwarz-Bunyakovsky 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 No-cloning 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:
    • §§ 4.5 of [NC]
  • Topics:
    • "two-level" unitary matrices -- many copies of SU(2) in SU(n)
    • making a swap out of CNOTs; making coordinate permutations
      out of several swaps
    • "two-level unitaries" are universal (Gaussian elimination)
    • "single qubit" operations and CNOTs make all "two-level 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:
  • multiply-controlled 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 error-correcting 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 7-bit code
        • classically:
          • the parity-check 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:
      • Chapter 10 of [NC]
    • Topics:
      • finishing the Steane code 7-bit code
        • correcting bit-flips
        • correcting phase-flips
        • correcting bit- and phase-flips
        • some circuits (encoding, decoding, syndrome measurement...)
      • some ideas towards fault-tolerance
        • fault-tolerant Toffoli circuit
      • the threshold theorem
    • Homework VII:
    Weihnactsferien
    Week 10: Fourier Transforms & the "QFT"
    • References:
      • Chapter 5 of [NC]
    • Topics:
      • characters of groups, the dual group
      • the general Fourier transform
      • the Fourier transform for Zn
      • 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, one-qubit 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
        • one-time pads
        • quantize key distribution: BB84
          • the protocol -- encoding randomly chosen bits with different bases
          • most naive attact impossible by the No-cloning 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:
      • Chapter 7 of [NC]
    • Topics:
      • the DiVincenzo criteria
      • Ion traps
      • optical QC
      • liquid-phase NMR QC
    Afterward...
    • There will be a final exam
      • Between 8am and 10:30am on Wednesday, March 24th
        • Contact me (by e-mail) in case of scheduling difficulty
      • Topics:
        • Basically, everything on the above outline
        • Be ready to do the exercises
        • Be prepared on well-defined specific topics from class, such as
          • protocols, their properties and elementary calculations
            about them
          • repeatedly-used theorems, their statements and proofs
    • Feel free to send me e-mail and/or arrange (by e-mail) 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

    Jonathan Poritz (jonathan.poritz@gmail.com)
    		 Page last modified: Saturday, 14-Jan-2012 10:16:22 MST