Quantum Computing

Fourth year course on Advanced Topics in Computability and Complexity in the honours programme on Mathematics of Computer Science.

Lecturer
Vasco Brattka

Department of Mathematics & Applied Mathematics
University of Cape Town

Time Table (2006)

The lectures and tutorials take place as follows:

Lecture on Mondays from 13:00-14:00 (period M) in M214,
Tutorial on Tuesdays from 14:00-15:00 (period 6) in M207 and
Lecture on Thursdays from 9:00-11:00 (period 2 & 3) in M202.

Course Description
This year the course on Advanced Topics in Computability and Complexity will be devoted to Quantum Computing. In the 1980s the physicist Richard Feynman noticed that quantum physics cannot be efficiently simulated on classical computers. This was taken as an indication that computers which exploit quantum physics could be substantially more powerful than computers build on the basis of classical physics. The essential reason for this potential efficiency is the fact that quantum systems can use superpositions and entanglement as a way to compute quasi in parallel. Since the development of real-world quantum computers requires enormous resources, theoretical computer science finds itself in the responsible situation to explore the possible benefits and limitations of such systems beforehand. The now famous factoring algorithm of Shor can be considered as another theoretical indication that quantum computers are more powerful than classical computers since no comparably efficient algorithms are known for classical machines. However, as plausible the thesis of higher efficiency of quantum systems is, it is yet still unproven. In this course we will develop the mathematical tools which are required to handle such questions on a sound basis.
The emphasis of the course will be on quantum complexity theory and among others we will treat the following topics:

Elementary Quantum Physics
Linear operators on Hilbert spaces
Shor's factoring algorithm
Grover's search algorithm
Probabilistic complexity theory
Quantum Turing machines
Quantum complexity theory

Part A: Quantum Physics

Introduction
- Introduction
- Feynman on Quantum Computers
- Polarized Light
- Superposition, Interference and Entanglement
- Einstein-Podolsky-Rosen Paradox
- Realism and Locality
- Bell's Inequality
- Interpretations of Quantum Mechanics
- Quantum Algorithms
- Hilbert Spaces in Quantum Mechanics
Hilbert Spaces
- Scalar Products
- Cauchy-Schwarz Inequality
- Banach Spaces
- Hilbert Spaces
- Some Examples of Hilbert Spaces
- Tensor Product
Orthogonality
- Orthogonality
- Gram-Schmidt Procedure
- Theorem of Pythagoras and Bessel's Inequality
- Orthonormal Bases and Parseval's Identity
- Dimension of Hilbert Spaces and Fourier Series
- Examples of Hilbert Space Bases
Linear Operators
- Linear Operators
- Trace of Matrices and Operators
- Tensor Product of Matrices and Operators
- The Pauli Matrices and the Hadamard-Walsh Matrix
- Continuous and Bounded Linear Operators
- Theorem on Orthogonal Projections
- Dual Spaces and the Representation Theorem of Fréchet-Riesz
- Dirac's Notation and von Neumann's Notation
Self-Adjoint Operators
- Adjoint Operators
- Conjugate and Transposed Matrices
- Self-Adjoint, Normal and Unitary Operators
- Complex Self-Adjoint Operators
- Norm of Normal and Self-Adjoint Operators
- Characterization of Orthogonal Projections
Eigenvalues and Spectral Decomposition
- Eigenvalues and Eigenvectors
- Spectrum of Self-Adjoint and Normal Operators
- Spectral Decomposition Theorem
- Square Root of Self-Adjoint Operators
Unitary Operators
- Commutators and Simultaneous Diagonalization
- Hamilton Operators
- Eigenvalues and Spectral Decomposition of Unitary Operators
- Theorem of Stone
- Schrödinger Equation
The Uncertainty Principles and Density Matrices
- Expectation Value and Dispersion
- The Uncertainty Principle
- Density Matrices
- Gleason's Theorem
Postulates of Quantum Mechanics
- The State Space Postulate
- The Evolution Postulate
- The Measurement Postulate
- The Composite System Postulate
- An Example System

Part B: Quantum Circuits and Gates

Quantum Bits
- Quantum Bits
- Standard Bases
- Quantum Registers
- Decomposable and Entangled States
- Unobservability of the Global Phase
- Polar Coordinates and the Bloch Sphere
- Rotation Operators and Phase Shifts
- Euler's Rotation Normal Form of Unitary Operators
- Cancelling Normal Form of Unitary Operators
- No-Cloning Theorem
Quantum Circuits
- Quantum Gates and Circuits
- Quantum Circuits as Acyclic Graphs
- Controlled Not Gate
- Controlled Not Gate with Inverted Control
- Crossover Gate
- Controlled Unitary Gates
- The Toffoli Gate
- Quantum Simulation of Digital Circuits
- Reversibility and Landauer's Principle
Universality of Quantum Gates
- Universal Sets of Quantum Gates
- Approximation and Measurement Results
- Universality Theorem
- Strong Universality of Two-Level Gates
- Strong Universality of Unitary Single Qubit Gates
- Approximation of Quantum Circuits
- Approximation of Rotations
- Approximation of Unitary Gates on Single Qubits
- A Universal Set of Quantum Gates

Part C: Quantum Algorithms

Deutsch's Algorithm
- Parity and Balanced Boolean Function
- Deutsch's Algorithm
- The Deutsch-Josza Algorithm
Some Group Theory
- Groups
- Subgroups and Cosets
- Theorem of Lagrange
- Normal Groups and Quotient Groups
- Cyclic Groups
- Group Homomorphisms
Discrete Fourier Transform
- Characters of Abelian Groups
- Characters of Cyclic Groups
- The Character Space of Finite Abelian Groups
- Orthogonality Relations of Characters
- Discrete Fourier Transform
- Discrete Fourier Transform as Unitary Operation
- Inverse Discrete Fourier Transform
- Fourier Transform and Periodicity
Quantum Fourier Transform
- Quantum Fourier Transform
- Hadamard-Walsh Transform as Quantum Fourier Transform
- Product Representation of Quantum Fourier Transform
- Quantum Circuit for Inverse Quantum Fourier Transform
Quantum Phase Estimation
- Quantum Phase Estimation
Modular Arithmetic
- Bezout's Identity
- Modular Arithmetic
- Chinese Remainder Theorem
- Euler's Function
- Euler's Theorem and Fermat's Little Theorem
- Prime Number Estimation
- Esimation of Coprime Numbers
Quantum Order Computation
- Reduction of Order Computation to Phase Estimation
- Modular Exponentiation
- Quantum Order Computation Circuit
- Continued Fraction Algorithm
Continued Fraction Algorithm
- Computing the Greatest Common Divisor
- Euclid's Algorithm
- Continued Fractions
- Convergents of Continued Fractions
- Continued Fraction Algorithm
- Continued Fraction Theorem
Shor's Quantum Factorization Algorithm
- Shor's Quantum Factorization Algorithm
Simon's Hidden Subgroup Problem
- Quantum Period Computing Algorithm
- Simon's Hidden Subgroup Problem
- Order Computation and the Hidden Subgroup Problem
- The Discrete Logarithm Problem
- The Hidden Subgroup Problem For Non-Abelian Groups
Grover's Quantum Search Algorithm
- Search Problems
- Search Oracles
- Inversion About the Mean
- Quantum Circuit for Inversion About the Mean
- Grover Iteration
- Grover Iteration as Rotation in Search Space
- Grover's Quantum Search Algorithm
Quantum Counting
- Grover Iteration as Rotation in the Search Space
- Quantum Counting Algorithm
- Quantum Decision Algorithm
- Quantum Search Algorithm With Unknown Solution Number
Optimality of Grover's Search Algorithm
- Complexity of Grover's Quantum Search Algorithm
- A General Quantum Search Algorithm
- Deviation of Quantum Search Algorithms
- Average Distance to an Orthonormal Basis
- Optimality of Grover's Quantum Search Algorithm
- Grover's Search Algorithm and NP-Completeness

Part D: Quantum Complexity Theory

Probabilistic Complexity Theory
- Probabilistic Turing Machines
- Computations of Probabilistic Turing Machines
- Semantics of Probabilistic Turing Machines
- Time Complexity of Probabilistic Turing Machines
- Monte Carlo, Las Vegas and Randomized Turing Machines
- Uniformization of Probabilistic Turing Machines
- Inclusions for Probabilistic Time Complexity Classes
Probabilistic Polynomial Time Classes
- Probabilistic Polynomial Time Complexity Classes
- Completeness in Probabilistic Time Complexity Classes
- Probabilities of Repeated Events
- Amplification of the Acceptance Probability
- Relativized Probabilistic Complexity Classes
Relativized Probabilistic Complexity
- Relativized Bounded Error Probabilistic Polynomial Time
- Relativized Probabilistic Complexity Classes
- Counting Complexity Classes
- Complete Problems for Counting Complexity
- Counting Complexity and Probabilistic Polynomial Time
Monte Carlo Algorithms and Complexity
- Quadratic Residues and the Legendre and Jacobi Symbols
- Euler's Criterion
- Multiplicativity of the Jacobi Symbol
- The Quadratic Reciprocity Law of Gauss
- Solovay-Strassen Algorithm for Primality
- Complexity Results on the Prime Problem
Las Vegas Algorithms and Complexity
- Expected Time
- Zero-Error Probabilistic Polynomial-Time
- Polynomial-Time Algorithm for Square Roots Modulo Primes
- The Algorithm of Adleman, Manders and Miller
- Public-Key Encryption Scheme of Rivest, Shamir and Adleman
Quantum Turing Machines
- Quantum Turing Machines
- Time Evolution Operator of Quantum Turing Machines
- Precision in the Specification of Quantum Turing Machines
- Boundedness of the Time Evolution Operator
- Normal Forms for Quantum Turing Machines
Time Evolution of Quantum Turing Machines
- Locality of the Time Evolution Operator
- Unitarity of the Time Evolution Operator
Quantum Complexity Classes
- Computations of Quantum Turing Machines
- Semantics of Quantum Turing Machines
- Time Complexity of Quantum Turing Machines
- Quantum Polynomial Time Complexity Classes
- Synchronization Theorem
- Deterministic Turing Machines as Quantum Machines
- Hadamard-Walsh Transformation on QTMs
- Probabilistic Turing Machines as Quantum Machines
- Theorem of Yao on Quantum Circuits
Quantum Complexity Versus Probabilistic Complexity
- Quantum Turing Machines with Rational Amplitudes
- Quantum Turing Machines as Probabilistic Machines
- Quantum Polynomial Time Complexity Classes
- Quantum Turing Machines with Unrestricted Amplitudes
- Quantum Oracle Machines
Quantum Postselection
- Postselection
- Boolean Closure of PostBQP
- The Postselection Theorem of Aaronson
- Boolean Closure of PP
- Variants of Quantum Physics for Computing
- Major Open Problems in Quantum Computing
Quantum Cryptography
- Private Key Cryptography and Quantum Key Distribution
- The BB84 Protocol of Bennett and Brassard
- Quantum Teleportation

Slides

The course slides simultaneously serve as lecture notes.

Course Slides (Version 25 October 2006, 2MB)

Problems

References

There will be no textbook prescribed to the course but the following books are helpful for further reading:

Jozef Gruska, Quantum Computing, McGraw-Hill, London, 1999
(in particular: Chapters 1-5)
Mika Hirvensalo, Quantum computing, Springer, Berlin, 2001
Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000
(in particular: Chapters 1-6)
Arthur O. Pittenger, An Introduction to Quantum Computing Algorithms, Birkhäuser, Boston, 2000

The followong references contain some background material:

Chris J. Isham, Quantum Theory, Mathematical and Structural Foundations, Imperial College Press, London, 1995
Asher Peres, Quantum Theory: Concepts and Methods, Kluwer Academic Publishers, Dordrecht, 1993
Ding-Zhu Du and Ker-I Ko, Theory of Computational Complexity, John Wiley & Sons, New York, 2000
(in particular: Chapter 8 on probabilistic complexity theory)

Resources

There is a plenty of material on the topic of this lecture available in the internet. The following sites are particularly recommended: