97263 - Mathematical Foundations of Quantum Computation

Learning outcomes

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.

Course contents

Prerequisites

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

Syllabus

Historical introduction; overview of the course

Hilbert spaces and Dirac notation; spectral theorem (no proof); positive semidefinite operators; Hilbert-Schmidt inner product

Density operators; Pauli matrices; the Bloch sphere; unitary evolution; quantum measurements; projective measurements; distinguishing quantum states; quantum observables; compatible observables; single-qubit projective measurements

Tensor product of Hilbert spaces and of linear operators; composite quantum systems; partial measurements; partial trace; reduced density operator; singular value decomposition; Schmidt decomposition

EPR paradox and CHSH inequality

Turing machines; uncomputability of the halting function; Boolean circuits; the strong Church-Turing thesis; decision problems; formal languages; the complexity classes P, BPP, NP and PSPACE; reducibility; NP-complete problems; reversible computation

Quantum circuits; duality between the operator norm and the trace norm; Helstrom bound; Solovay-Kitaev theorem (no proof); CNOT gate; universality of {H,T,CNOT} gates

The complexity class BQP; BPQ is included in PSPACE; quantum parallelism; oracles

Deutsch algorithm; Deutsch-Jozsa algorithm; Bernstein-Vazirani algorithm; Simon's algorithm

The quantum Fourier transform; quantum phase estimation

The period-finding algorithm; the order-finding algorithm; Shor's algorithm; the hidden subgroup problem

The one-time pad; public key cryptography; the RSA protocol; Grover's algorithm; quantum counting algorithm; optimality of quantum counting

Quantum operations; Kraus representation; isometric dilations; bit-flip and phase-flip channels; depolarizing channel

Quantum key distribution; the BB84 protocol

Quantum error correction; classical repetition code; bit-flip and phase-flip codes; Shor's 9-qubit code

Readings/Bibliography

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/

Teaching methods

Classroom lectures

Assessment methods

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.

Office hours

See the website of Giacomo De Palma