M2 Quantum, Mathematics, and Computer Science

Quantum information theory seeks to understand the absolute limits of information processing using quantum systems. This course will explore a variety of information processing tasks including  data compression, channel coding and entanglement distillation. For each task, we will develop the necessary tools to analyse their properties and demonstrate how their rates can be characterised in terms of entropic quantities. We will also cover recent major advances in the field and discover so-called one-shot information theory which examines the rates of protocols within the non-asymptotic regime.

Lecture 1

- Compression

Lecture 2-3:

- Channel capacities (classical, quantum, entanglement-assisted, private) (degradable, anti-degradable channels)

Lecture 4:

- LOCC, entanglement distillation

Lecture 5:

- State discrimination and hypothesis testing (relative entropy)

Lecture 6:

- Data processing, tightness and recovery maps

Lecture 7-8:

- One shot info theory, AEP, Chain rule, channel discrimination

Linear algebra, basic quantum algorithms (DJ, Grover, Shor). Having followed courses on group theory and representation theory is welcome, but these will in any case be covered at length in the lectures.

Contrary to what we hear in the media, it is very unlikely that quantum computing unlocks a universal computation speedup: it seems there are only specific problems that it solves faster, sometimes dramatically so. Can we identify those problems, and understand why quantum algorithms perform so well on them? This is of course a question of prime importance, both foundational – for understanding the true power of quantum computing, beyond mere examples –, and practical – for instance for making sure that our post-quantum cryptography techniques will indeed remain quantum-secure. In this course, we will discover two strikingly different approaches to this question. The first, Quantum Singular Value Transform (QSVT), finds that quantum algorithms are good at polynomial transformations of matrices; the second, Hidden Subgroup Problems (HSP), finds that they perform well at spotting group-theoretic regularities. This will also be an occasion to discover some lesser-known quantum algorithms, such as the eigenvalue threshold, HHL, and discrete logarithms. The course will end on open research questions in these highly dynamic research domains.

Prerequisites: linear algebra, basic quantum algorithms (DJ, Grover, Shor). Having followed courses on group theory and representation theory is welcome, but these will in any case be covered at length in the lectures.

List of sessions

• Lecture 1 (3h) –  Quantum signal processing, amplitude amplification, block encodings, and an application to Grover.
• Lecture 2 (3h) – Quantum Eigenvalue Transforms and the QSVT, applications to the eigenvalue threshold problem and to HHL
• TD 3 (3h) – Polynomial approximation for the QSVT with Chebyshev polynomials 
• Lecture 4 (3h) – Groups and representations
• Lecture 5 (3h) – The regular representation and the Quantum Fourier Transform; HSPs and how they generalise Shor and the discrete logarithm
• Lecture 6 (3h) – Solving the abelian HSP
• TD 7 – Variations on the abelian HSP
• Lecture 8 – The HSP frontier: results and conjectures on the non-abelian case

Linear algebra, basics of quantum statistical inference, elementary complexity theory.

This course aims to present the rigorous theoretical foundation of the notion of quantum advantage. The main quantum computational models will be introduced in detail as well as the associated quantum complexity classes. We will cover the known theoretical separation between quantum and classical from discrete to continuous variable quantum computing, providing a large panorama of the benefit we can expect from quantum technologies when it comes to theoretical computational complexity.

Introduction to quantum complexity theory:

(Titouan Carette: 6 hours lecture + 6 hours TD)

• Computational models: Quantum Turing machines and quantum circuits, variations, gate set, approximate universality, Solovay-Kitaev.
• Complexity classes: BQP, QMA, QIP, known inclusions and equalities.
• Quantum query complexity: query model, polynomial bound, adversary bound, separation classical/quantum.

Analog model of quantum computation with continuous variable systems:

(Marco Fanizza: 3 hours lecture + 1 TD)

• States on separable Hilbert spaces, L^2(R^m), canonical commutation relations, harmonic oscillator, Fock space.
• Gaussian states and Gaussian operations, universal gate sets, classical simulability.
• Towards advantage with continuous variables: non-linearities, photon counting

Proofs of quantum advantage:

(Cambyse Rouzé: 6 hours lecture + 2 hours TD)

• More on decision problems, the polynomial hierarchy 
•  Counting problems and the class #P
•  Sampling problems and the connection to counting
•  Quantum advantage with Boson Sampling

Course Objective

This course introduces the hardware used for quantum information technologies and the associated practical challenges involved in realizing quantum information processing systems which theorists should take into account. The aim is to bridge the gap between theoretical quantum algorithms and protocols and their real-world implementation on hardware.

Problem Setting

We can illustrate these aspects with a quantum algorithm that we want to run on a real quantum computer. Assume a quantum algorithm on n qubits, corresponding to qubit initialization, unitary transformation U and qubit measurements. U can be approximated using a universal gate set (e.g., CNOT and arbitrary single-qubit gates) and in theory, we should simply run this quantum circuit on physical qubits to obtain the desired result. However, when interacting with experimentalists, you will face hardware-specific limitations that may prevent direct implementation. This course provides the practical knowledge to anticipate such constraints, estimate runtime and feasibility, and define a hardware-specific theoretical model for executing quantum algorithms.

Course Breakdown (6 Lectures + Labs)

1–2: Quantum Systems, Gates implementation, and orders of magnitude.

• The “physics” of hardware components:
  • Discrete energy levels in atoms and ions
  • Solid-state physics (semiconductor / metal)
  • Photons and quantized modes of the electromagnetic field
• Mechanisms for defining a qubit in these systems (e.g. DV / CV encoding)
• Gate operations: physical mechanisms of interaction and dynamics under the Schrödinger equation

3–6: Quantum computing hardware model and popular hardware platforms: Introduction to hardware Using cold atoms platforms as an illustration, we will introduce all the important concepts of QC on real hardware (gate implementation techniques, operational timescales, noise sources. . . ). We will extend these general concepts to superconducting circuits quantum computing and photonic quantum computing as well. Quantum Computing hardware model Introducing general concepts to consider hardware from a theorist perspective. The goal is to understand the key constraints (e.g. connectivity constraints, noise. . . ) imposed by different hardware platforms and to abstract them out with a more theoretical perspective, and understanding the interest and limitations of such hardware models.

Projects / Labs: The objective is to apply these concepts in a lab projects. To experience them on real experimental platforms (such as the ones accessible on the cloud).

Linear algebra ; Notions of quantum computation.

Quantum computing is a computational model able to bring drastic changes in a wide spectrum of fields: high-performance computing, chemistry, cryptography, machine learning... There is however an important gap between the mathematical presentation of a quantum algorithm and its concrete implementation details: This course aims at presenting and highlighting the issues at stake. To illustrate the situation, we shall consider a non-trivial example: HHL, an algorithm aiming at solving linear systems of equations. The algorithm requires several building blocks: Hamiltonian simulation, Trotterization, Phase Estimation, and oracle encodings. We will discuss the compilation of each of these constructions with a focus on time and space resource estimation, with a discussion on the effectiveness of the algorithm depending on the underlying structure of the chosen linear system.

Rough sequencing of the 8x3h sessions of the course:
1 - The computational model of quantum circuits, QFT and QPE.
2 - The HHL algorithm.
3 - Lab session: coding HHL with QisKit.
4 - Compilation of Hamiltonian Simulation and Trotterization:
presentation and discussion of the tradeoffs
5 - Lab session
6 - Compilation of oracles: presentation and discussion of the tradeoff
7 - Lab session
8 - Coming back to HHL : lessons learnt, and discussion of other aspects such as: code optimization, hardware constraints, qubit layout, etc.

Quantum computers in theory, are predicted to outperform classical computers in certain tasks. Quantum computers in practice however, are fragile, having to contend with sources of noise and decoherence both in a quantum memory persisting over time and in the implementation of computational gates. Quantum error correction is the study of solutions to this problem based on the encoding of logical information into larger more protected physical systems. The design of such codes is an active area of research and an inherently interdisciplinary topic, at the intersection of physics, computer science, and mathematics. In this course we will learn the necessary pre-requisites to design, analyze, and use quantum error correcting codes. We will particularly focus on the toric / surface code due to its simplicity, its performance, and its relevance to current research. It will serve as a tool to introduce more advanced concepts.

Organization.

This lecture is structured into 8 time slots, each lasting 3 hours: 6 time slots of lecture + tutorials, mixed. The last 2 time slots will consist of programming labs.

Syllabus

1. Introduction

2. CSS codes and simple examples

3. QEC codes and stabilizer formalism

4. Knill-Laflamme theory of quantum-error-correcting codes

5. Toric code and generalization

6. Decoding the toric code

7. Lab: Decoders

8. Lab: Fault-tolerance and syndrome extraction circuits

Linear algebra, basic quantum information, and a taste for abstraction. Having followed the P1 course “ZX calculus” is a plus but not required.

What are the mathematical structures encapsulating the weirdness of quantum theory? How can they be formally pinned down to ease their handling? How, in particular, can the crucial notion of causal structure be salvaged within a theory that seems to disregard it in such a careless way? Can one also superpose causal influences? These are the questions that this course will answer. We will show how recently developed mathematics (based in particular on category theory) help us to reformulate quantum theory from the ground up as a process theory, by taking its peculiar properties (first and foremost entanglement) as axioms. This opens to a renewed perspective on the notion of causal structure. Going to higher-order quantum processes – processes that map a quantum evolution to another quantum evolution –, we will discover that even causal structures might be put in a superposition in a quantum computer, leading to new speedups and applications.

List of sessions

• Lecture 1 (2h) –  Quantum theory as a process theory, symmetric monoidal categories, daggers, entanglement as cups and caps
  then TD 1 (1h) – categories of quantum processes, category of relations.  
• Lecture 2 (2h) –  Classical structures as Frobenius algebras, no-cloning, no-broadcasting, CJ isomorphism, quantum curryfication
  then TD 2 (1h) – Markov categories, quantum lambda calculus.
• Lecture 3 (2h) –  Doubling, discarding, the causality condition, purification
  then TD 3 (1h) – purification in the alternative categorical model (rel, )
• TD 4 (3h) – Categorical axiomatisation of Hilb.
• Lecture 5 (2h) –  OPTs and re-axiomatisations of quantum theory
  then TD 5 (1h) – Local tomography and real quantum theory
• Lecture 6 (2h) –  Quantum causal models
  then TD 2 (1h) – Causal decompositions
• Lecture 7 (2h) –  Higher-order quantum computation
  then TD 7 (1h) – The quantum if
• TD 8 (3h) – Properties of higher-order maps: purifications, type systems, causal structure

This course explores quantum information processing through the lens of quantum correlations. We will develop an understanding of quantum correlations and the main mathematical tools to characterise them: from the well-known Bell-nonlocality and self-testing to new techniques based on graph inflation. We will discover direct applications and insights that can be gained from this approach, including results on communication complexity and non-local computation. We will further explore deep problems that leverage variations of the acquired techniques, such as parallel repetition theorems, Tsirelson's problem and marginal problems in general.

Plan of the course:

Lecture 1: Bell-nonlocality, Tsirelson bound, nonlocal games.

Lecture 2: Self-testing.

Lecture 3: Parallel repetition theorems, introduction to the Tsirelson problem.

Lecture 4: From nonlocality to information processing and computation, communication complexity, information causality, nonlocal computation. Physical principles for quantum theory.

Lecture 5: Non-signalling, information processing and computation beyond quantum theory (GPTs).

Lecture 6: The multipartite setting, entanglement swapping, entangled measurements vs. LOCC measurements, networks.

Lecture 7: Tools to analyse networks, entropy cone and non Shannon entropy inequalities, covariance matrices, Inflation.

Lecture 8: Marginal problems.

Convex optimization has emerged as a critical tool for quantum information scientists, leveraging the natural convexity of quantum theory to offer powerful techniques for solving a variety of complex problems in the field. In this course we will develop these tools, with a focus on semidefinite optimization, analysing their mathematical properties and discussing their practical usage. The course will be driven by applications throughout quantum information science, using the tools we develop to solve important problems and provide new powerful perspectives on the field.

Plan of the course.

Lecture 1 (Convexity and convex optimisation)

Convex sets, cones and functions. Convex optimization problems and their properties.

Lecture 2 (Linear, semidefinite and conic optimisation)

Simple examples. Duality, Slater's theorem, Complementary slackness. Practical considerations and symmetries.

Lecture 3 (Basic applications to quantum theory)

Applications to: discrimination tasks, entanglement witnessing, cloning machines, complexity theory, channel coding.

Lecture 4 (The DPS hierarchy)

The separability problem and the DPS hierarchy. De finetti theorem. Applications.

Lecture 5-6 (SDPs as proof tools)

Semidefinite representability of functions. Applications to proving properties of trace norm, fidelity and entropies. Additivity, data processing, inequalities.

Lecture 7 (Noncommutative polynomial optimization)

Basic problem, semidefinite hierarchy solution.  Applications to Bell-nonlocality, cryptography, ground state energy problem.

Lecture 8 (Sum of squares).

Sum of Hermtian squares polynomials, properties, duality to NCPOPs, applications.

Linear algebra. Information theory basics: channel, entropy, capacity, linear codes.

The advent of fault-tolerant application scale (FASQ) machines would radically jeopardize the security of current public-key cryptography. Conversely, quantum communications, combined with existing classical and quantum processors, can be used to perform cryptographic tasks that cannot be achieved only with quantum means. Understanding modern cryptography, and the transition towards so-called post-quantum cryptography (PQC), and understanding quantum cryptography (QC) and its positioning and possible combination with PQC is therefore central for the future of cryptography. The objective of this course is to present the fundamentals of modern cryptography and of quantum cryptography, and to equip the students with a vision of the efforts, challenges and opportunities associated with the ongoing quantum-safe transition.

Plan of the course.

1. Introduction: Quantum Cryptography goals and tools.

2. Quantum Key Distribution Theory

3. Quantum Key Distribution in practice

4. Hash-Based Signature Schemes

5. Design of Post-Quantum Digital Signature Schemes (DSS)

6. Design of Post-Quantum Key-Encapsulation Mechanism (KEM) and beyond

7. Modern topics in Q Cryptography

8. Quantum-Safe Networks

Basics of quantum statistical inference ; Basics of quantum computing ; Linear algebra

Many-body quantum systems are ubiquitous in theoretical and experimental quantum information processing, from the simulation of condensed matter systems to the development of good quantum error-correcting codes. Recent years have seen major developments in our mathematical understanding of these systems' intricacies. In these lectures, we will explore the complexity of physically motivated models of many-body quantum systems, from ground and thermal states of matter to outputs of short-time quantum evolutions. We will consider two notions of complexity: (i) the computational hardness of simulating properties of the system (a.k.a. forward problem); and (ii) the learnability of classical descriptions of the system from access to samples (a.k.a inverse problem).

The course will consist in 26 hours of lectures punctuated with 6 hours of exercises

Part 1: Sampling

• Lecture 1: Simulating real time dynamics, Trotterization, Lieb-Robinson bounds [2h]
• Lectures 2-3: The local Hamiltonian problem, QMA hardness of computing the ground state energy, connections to classical optimization [4h]
• Lecture 4: Adiabatic and variational quantum algorithms [2h]
• Lectures 5-6: Quantum Gibbs sampling and partition function estimation [4h]

Part 2: Learning

• Lectures 1-2: Learning quantum systems in trace distance: single copy algorithms, Schur- Weyl duality, optimal algorithms [4h]
• Lectures 3-4: Learning expectation values of a set of quantum observables: shadow tomography, classical shadows [4h]
• Lecture 5: Learning the Hamiltonian of a many-body systems from Gibbs states [2h]
• Lectures 6-7: Learning the Hamiltonian of a many-body system from time evolution [2h], Learning tensor networks in 1D [2h]

Knowledge of quantum circuit programming is assumed, including Variational Quantum Algorithm. Knowledge of classical ML will be useful, but reminders will be given at the beginning of courses that require it.

This course presents the main concepts and algorithms of quantum ML based on quantum circuits for digital architectures and introduces some methods of quantum ML algorithms on analog architectures. Firstly, the course introduces embedding techniques in Hilbert space and some mechanisms for computing gradients or alternative solutions. Based on these mechanisms, the course presents various quantum algorithms for data clustering, neural networks and generative networks. Built around variational quantum algorithms and quantum circuits, they can run on digital current NISQ or future FTQC architectures to perform classifications or predictions. Finally, the course introduces some quantum algorithms mainly designed for analog quantum architectures: QUBO optimization methods used to train some ML models and quantum reservoir algorithms. Several tutorials and labs on digital or analog quantum development environments, with and without noise, and a few experiments on real QPUs, will fill the course. 

Course outline  

Part I: Principles and basic mechanisms 

1. From ML to Quantum ML 

2. Quantum embedding methods 

3. Quantum gradient computing methods  

Part II: QML based on VQA and quantum circuits 

4. Quantum data clustering 

5. Quantum Neural Networks 

6. Quantum generator networks 

7. Parallel circuits of neural networks  

Part III: QML on analog quantum architectures 

8. QUBO method for ML 

9. Quantum reservoirs

Some lessons include reminders of classic ML at the beginning

• Linear algebra
• Basics of quantum information

This course provides a graphical approach to represent and study quantum information and computation. Aer exploring general features of quantum information in a graphical yet formal way, we introduce the more specic ZX-calculus, that can be used to represent and manipulate states and operators at an atomic level. We will show some important results about quantum information in this seing, and will further demonstrate its use in applications ranging from verication to simulation.  

Topics Covered

Diagrammatic Approach to antum Information & Computing
• String diagrams
• Compositions and tensor products
• Transpose, dagger, map-state duality
• Partial trace and channels
• CPM construction

Introduction to ZX-Calculus
• Denition of the generators – exsymmetry
• Circuit-to-ZX translation
• Universality
• Stabiliser equational theory – manipulations
• Normal form and reduction in the H-free 0-fragment

Advanced ZX-Calculus
• Graph states, pivoting, local complementation
• Normal form and reduction in stabiliser fragment (Goesman-Knill theorem)
• Euler angles
• Extension to channels
• Extension to scalable notation

Applications
• Verication (teleportation, superdense coding, Bernstein-Vazirani, Deutsch-Jozsa, Simon, pseudo-telepathy games, BB84?, ...)
• MBQC
• Error correction (stabiliser codes?, surface code & laice surgery, ...)
• Simulation in Clifford+T
• [TBC] T-count reduction in circuits
• [TBC] Manipulations with PyZX/iZX

• Learn the basics of diagrammatic quantum computation
• Perform manipulations on ZX-diagrams
• Explore applications of ZX-calculus (MBQC, Goesman-Knill theorem, verication, simulation, ...)

• Linear Algebra (vector spaces, matrix-vector calculus, matrix decompositions - QR, SVD, Cholesky, LU)
• Basic programming in Python

This course explores the theory and applications of tensor computations, ranging from the basic operations on tensors to the numerical algorithms for the formation and manipulation of tensor decompositions and networks. After providing all theoretical fundamentals for the tensor algebra, the course focuses on the state-of-the-art research work that leverages tensor decompositions and networks in the domains of quantum computing, high performance computing, and AI/data analysis.

Topics covered:

Introduction to Tensor Algebra
• Definition and notation
• Scalars, vectors, matrices, and generalization to tensors
• Basic tensor operations: addition, multiplication, contraction
• Tensor products and outer products
• Einstein summation convention and index manipulation

Tensor Decompositions and Networks
• Refresher on matrix decompositions (QR, SVD, Cholesky, LU, low-rank decompositions)
• Introduction to tensor decompositions and networks
• Canonical polyadic decomposition (CPD)
• Tucker and Hierarchical Tucker decompositions
• Tensor-train decomposition (TT), Matrix product states (MPS) and Projected entangled-pair states (PEPS) networks

Numerical Methods for Tensor Computations
• Algorithms for computing tensor decompositions (Tensor SVD)
• Low-rank tensor arithmetic
• Tensor cross-approximation
• Optimization algorithms on tensor manifolds (ALS, AMEN)
• Tensor completion and recovery

Applications in Quantum Computing, High Performance Computing, and AI
• Computational challenges in tensor algorithms
• Tensor networks in quantum chemistry and physics, quantum simulation, etc
• Tensor decompositions in multivariate data analysis, neural networks, recommender systems, etc

• Learn the mathematical foundation of tensors and tensor operations.
• Understand the philosophy of low-rank computations using tensor decompositions/networks.
• Implement tensor network computations using Python libraries such as NumPy or TT-toolbox.
• Explore the applications of tensor computations in in quantum computing, high performance computing, and AI/data science.

• Tensor Decompositions and Applications by Tamara G. Kolda and Brett W. Bader.
• Tensor Ranks for the Pedestrian for Dimension Reduction and Disentangling Interactions by Alain Franc.
• Tensor Spaces and Numerical Tensor Calculus by Wolfgang Hackbusch.
• And many research papers and articles provided throughout the course.