97263 - MATHEMATICAL FOUNDATIONS OF QUANTUM COMPUTATION

Conoscenze e abilità da conseguire

At the end of the course the student is acquainted with the basic aspects of quantum computation like those of entanglement, qubits, quantum algorithms and information. He is able to deal with the classical problems of the subject.

Contenuti

Prerequisites

The basic courses of the BSc (Laurea Triennale) in Mathematics. Knowledge of linear algebra is particularly important.

Syllabus

Historical introduction.

Hilbert spaces; Dirac notation; Orthogonal projectors, unitary operators, positive-semidefinite operators.

Density operators, pure quantum states.
The qubit; Pauli matrices and their properties.
The Bloch sphere; Unitary evolution; U(2) and SO(3).
Unitary evolution in the Bloch sphere; The tensor product and its properties; Tensor product of operators; Composite quantum systems.
Quantum measurements; projective measurements.
Measurement in a basis; Distinguishing quantum states; Quantum observables; Compatibility of observables.
Partial measurement; Partial trace; Reduced density operator; Singular value decomposition; Schmidt decomposition.
EPR paradox; CHSH inequality.

Turing machines; The halting problem; Logic circuits; The Church-Turing thesis and the strong Church-Turing thesis.
Formal languages; the complexity classes P and NP; NP-complete languages; Toffoli gate and reversible computation.

Quantum circuits; Measurement in the computational basis; Single-qubit gates; Operator norm and trace norm; Hellstrom bound; The Solovay-Kitaev theorem (no proof).
Controlled quantum gates; Universality of {H, T, CNOT}; The complexity class BQP.
Quantum parallelism; Classical and quantum oracle models; Deutsch's algorithm; Deutsch-Jozsa algorithm; Bernstein-Vazirani algorithm.
Simon's algorithm; The quantum Fourier transform.
Quantum phase estimation; the quantum period-finding algorithm.
The quantum order-finding algorithm; Shor's algorithm.
The hidden subgroup problem; The one-time pad; Private-key cryptography and the RSA cryptosystem; Grover's quantum search algorithm.
The quantum counting algorithm; Optimality of quantum search.

Quantum operations; Kraus representation; Isometric dilations; Bit-flip and phase-flip channels; Depolarizing channel.
Quantum key distribution; The BB84 protocol; The classical repetition coding.
Quantum error correction; The bit-flip and phase-flip 3-qubit codes; Shor's 9-qubit code.
The Knill-Laflamme theorem.

Testi/Bibliografia

The lectures will mostly follow the books

Michael A. Nielsen, Isaac L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2010

Wolfgang Scherer, "Mathematics of Quantum Computing", Springer, 2019

Further resources available online are

Ronald de Wolf, "Quantum Computing: Lecture Notes", arXiv:1907.09415, https://arxiv.org/abs/1907.09415

John Preskill, "Quantum Computation" (lecture notes), http://theory.caltech.edu/~preskill/ph229/

Metodi didattici

Classroom lectures

Modalità di verifica e valutazione dell'apprendimento

The grade will be assigned upon oral examination. Each exam will include theoretical questions and the solution of a simple exercise. The student will be evaluated both on the understanding of the content of the lectures and on the ability to apply it. The students who achieve an organic vision of the topics, are able to critically apply them and master the specific language will be assessed with a grade of excellence. The students who show a mechanic or mnemonic knowledge of the topics, have limited capabilities of analysis and synthesis or a correct but not always appropriate language will be assessed with an average grade. The students who show a minimal knowledge of the topics and of the appropriate language will be assessed with the minimum passing grade. The students who show poor knowledge of the topics, inappropriate language and are not able to properly understand the material will be assessed with a non-passing grade.

Orario di ricevimento

Consulta il sito web di Giacomo De Palma