Course Outline for Physics 229
Quantum Information and Computation

John Preskill, Caltech
Fall, 1997

Contents

Foundations of Quantum Theory
Quantum Entanglement
Classical Information Theory
Quantifying Entanglement
Quantum Information Theory
Quantum Computers
Quantum Algorithms
Quantum Error Correction
Some Novel Aspects of Measurement
Physical Implementations of Quantum Computation

Foundations of Quantum Theory

Axioms of quantum theory:

• States = normalized vectors in Hilbert space
• Observables = self-adjoint linear operators
• Measurement = orthogonal projection
• Dynamics = unitary transformation

Simple quantum systems:

• Spin-1/2 (qubit)
• qubits versus classical bits
• Photon polarization
• Harmonic oscillator

Open systems:

• From pure states to density matrices
• Partial trace
• Ensembles
• Schmidt decomposition
• Gleason's theorem
• From orthogonal  measurements to POVM's
• Neumark's theorem
• From unitary evolution to superoperators
• Kraus's operator-sum representation

Master equation and decoherence:

• Infinitesimal superoperators
• Lindblad form
• Oscillator in contact with reservoir
• Decoherence rate

Quantum measurement:

• Models of measurement
• The relevance of decoherence
• Randomness and probability
• The Bayesian viewpoint
• Measurement from unitary evolution

Quantum Entanglement

Nonseparability of EPR pairs:

• Violation of local realism
• Bell inequality and CHSH inequality

Three particle entanglement:

• Local realism and the GHZ state
• Communication complexity

Entanglement as a resource:

• No-cloning theorem; approximate cloning
• Dense coding, teleportation
• Entanglement-based quantum key distribution

Classical  Information Theory

Data compression and Shannon entropy

The noisy channel and the channel capacity

• Mutual information
• Random coding
• Channel coding theorem

Quantifying Entanglement

Number of Bell pairs as a measure of entanglement:

• Concentration of pure state entanglement
• Reversibility

Mixed state entanglement:

• Werner states
• Fidelity
• Nonseparability versus Bell inequality violation
• Criteria for nonseparability
• Classical communication and inequivalent ensembles
• Entanglement of formation and entanglement of distillation

Quantum Information Theory

Quantum data compression theorem:

• Von Neumann entropy

Sending classical information over a quantum channel:

• Nonorthogonal states
• Distinguishability versus disturbance
• Quantum cryptography
• Optimal collective measurements

Holevo's theorem:

• Mutual information and accessible information
• Holevo's bound
• Achievability: random coding and optimal measurement
• Entangled signal states

The quantum channel capacity:

• Depolarizing channel
• Erasure channel
• Bounds on capacity
• Random coding
• Lloyd-Schumacher-Nielsen capacity
• Shor-Smolin code

Parameter estimation

Quantum Computers

Turing machines:

• Classical
• Quantum
• Circuits

Universal gates:

• Classical: NAND gate
• Reversible: Toffoli
• Quantum

Quantum Algorithms

Classical complexity theory

Deutsch-Jozsa algorithm:

• Coin weighing

Quantum simulation:

• Hilbert space is BIG
• Local Hamiltonian evolution

Database search:

• Finding 1 out of 4 in one step
• Finding 1 out of N in square root time
• The Grover algorithm is optimal

Simon Algorithm

Quantum Fourier transform:

• Implementation with one-bit gates

Factoring:

• Number theory background
• Cracking RSA public key cryptography
• Kitaev's version

Quantum communication complexity

Quantum Error Correction

The need for quantum error correction:

• Decoherence
• Unitary errors

Classical error-correcting codes:

• Hamming code
• Linear codes
• Dual codes
• Reed-Muller codes

Quantum error-correcting codes:

• Error models
• Criteria for a good code: reversible operations
• 3-qubit phase code
• 9-qubit code
• 7-qubit code
• Calderbank-Shor-Steane codes
• Quantum Reed-Muller codes
• Quantum Hamming bound
• Knill-Laflamme bound

Stabilizer codes:

• Criteria for a good code
• 4-qubit error-detecting code
• 5-qubit code
• Encoding and decoding

Fault-tolerant quantum computation:

• Classical fault tolerance

• Fault-tolerant recovery
• 7-qubit code
• General stabilizer codes
• Fault-tolerant gates
• 7-qubit code
• General stabilizer codes
• Concatenated codes
• Flow equations
• Accuracy threshold
• Threshold estimates

Topological quantum computation:

• Toric codes
• Physical fault tolerance
• Non-abelian Aharonov-Bohm phenomena
• Universal computation with nonabelions

Some Novel Aspects of Measurement

Homodyne detection

Quantum Zeno effect

Quantum nondemolition

Protective measurement

Quantum eraser and delayed choice

Interaction-free measurement

Coincidence and interferometry

Physical Implementations of Quantum  Computation

Quantum optics:

• Rotating wave approximation
• Jaynes-Cummings Hamiltonian

Ion Trap:

• Sideband cooling of phonons
• Quantum jump readout
• Cirac Zoller scheme
• Limits on gate accuracy

Cavity QED:

• Strong coupling
• Adiabatic passage
• Error correction
• Distribution of entanglement

NMR:

• Effective pure states
• Deterministic algorithms
• Limits on number of qubits

I would welcome comments and suggestions concerning the content of the course (which is still evolving).

preskill@theory.caltech.edu

---

Return to the Physics 229 Home Page