INF587 Quantum Information and Applications
Introduction
This course is an introduction to the concept of a quantum computer. It
uses quantum-mechanical principles and generalizes
classical computers. It has been demonstrated that such a computer can
solve in polynomial time problems that are considered
to be hard for a classical computer such as factoring large integers or
solving the discrete logarithm problem (this is Shor's algorithm).
The security of virtually all public-key cryptography used in practice
right now relies on the hardness of these problems
and a quantum computer would break those cryptosystems. It has also been
found that such a computer is able to search in an unstructured
set much more efficiently than a classical computer (this is Grover's
algorithm).
We will cover in this course the bases of quantum computation and
present the main quantum algorithms that offer a speedup over classical
algorithms.
We will also cover other applications of quantum mechanics, such as
simulating physical systems or quantum cryptography. The latter exploits
the laws of quantum physics to establish the security of certain
cryptographic primitives, such as key distribution protocols.
Lectures
- January 8, Introduction
- qubits and quantum registers
- measurement and unitary evolution
- elementary gates
- quantum teleportation, superdense coding
- The first algorithms : Deutsch-Josza and Bernstein-Vazirani
Lecture 1.
- January 15, Fundamentals of quantum information
- density matrix
- quantum evolutions
Lecture 2.
- January 22, The circuit model
- classical and quantum circuits
- universality of quantum computation with a restricted set of
elementary gates
Lecture 3.
- January 29, Advanced algorithms based on the quantum Fourier
transform
- the quantum Fourier transform
- the abelian hidden subgroup problem
- application : phase estimation
- application : Shor's algorithm for factoring and solving the discrete
logarithm problem
Lecture 4.
- February 5, Advanced algorithms
- Grover's algorithm,
- the amplitude amplification algorithm,
- other algorithms that are relevant to
cryptography such as collision algorithms
Lecture 5.
- February 12, Quantum walks
- classical random walks and applications
- quantum random walks
- applications
Lecture 6.
- February 26, Hamiltonian simulation; an advanced algorithm for solving large linear systems the
Harrow-Hassidim-Lloyd algorithm
- Hamiltonians
- applications to quantum chemistry
- the Lie-Suzuki-Trotter method
- the block encoding method
- the Harrow-Hassidim-Lloyd algorithm
Lecture 7.
- March 4, Quantum error correcting codes
- the Shor code
- CSS codes
- stabilizer codes
Lecture 8.
- March 11 Quantum cryptography, quantum key distribution
Lecture 9
Project/Final exam
- Breaking symmetric cryptosystems with Simon's algorithm,
Crypto 2016 paper by
Marc Kaplan, Gaetan Leurent, Anthony Leverrier and María Naya-Plasencia
- The hidden nonabelian subgroup problem and the Kuperberg
algorithm,
see Chapters 11-13 in the
lecture notes on quantum computing by
Andrew Childs
- A nice application of the HHL algorithm
Quantum recommendation systems
by Iordanis Kerenidis and Anupam Prakash
- Another nice application of the HHL algorithm
Quantum support
vector machine for big data classification
by Patrick Rebentrost, Masoud Mohseni and Seth Lloyd
- The Phd thesis of Stuart Andrew Hadfield contains several
chapters that are a good introduction to several approximation
algorithms, some of them are potentially implementable on noisy quantum
devices
-
Approximating ground and excited state energies on a quantum
computer
Chapter 3
-
Divide and Conquer Approach to Hamiltonian Simulation
Chapter 4
-
Quantum Approximate Optimization
Chapter 6
- Quantum query lower bounds
Chapter 11 of
the lecture notes of Ronald de Wolf
- Quantum communication complexity
Chapter 14 of
the lecture notes of Ronald de Wolf
Bibliography
- Michael A. Nielsen, Isaac L. Chuang, "Quantum Computation and Quantum
Information: 10th Anniversary Edition". Cambridge, 2010.
Oral examination schedule
Tuesday March 17, PC 24
| Schedule |
élèves |
| 13h00-13h40 |
Erwin Kuhn |
| 13h40-14h20 |
Florian Hofhammer |
| 14h20-15h00 |
Briac Thomas |
| 15h00-15h40 |
Louis Dubois |
| 15h40-16h20 |
Thimothée Paquatte |