Adiabatic computing and variational methods

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Applied Mathematics

Synopsis:

The course introduces adiabatic computing and variational quantum algorithms (VQA). We start with a broad introduction to variational methods in physical chemistry (e.g., for calculating ground state of small molecules) and a recapitulation of advances in theoretical computer science (computational complexity and problems such as MAXCUT). We will present the EQA Conjecture and the unique games conjecture. We will present the adiabatic theorem and quantum speedup by quantum annealing (QA). We will build up an understanding of variational quantum algorithms by introducing and analysing, in turn, Variational quantum eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), and their Warm-started variants. As applications, we will highlight variational solvers for systems of linear equations and variational solvers for Markowitz portfolio management, with some discussion of the challenges in benchmarking of VQA.

Requirements:

Syllabus of lectures:

1. A view from physical chemistry (energy levels of molecules) vs. a view from theoretical computer science (MAXCUT).

2. EQA Conjecture.

3. Inapproximability and the unique games conjecture.

4. Adiabatic theorem and quantum speedup by quantum annealing (QA).

5. Variational quantum eigensolver (VQE).

6. Quantum Approximate Optimization Algorithm (QAOA).

7. Parameter shift rule (PSR).

8. Iteration complexity of QAOA with PSR.

9. Per-iteration complexity of QAOA.

10. Warm-starting quantum optimization: rounded.

11. Warm-starting quantum optimization: continuous-valued.

12 Applications: variational solvers for systems of linear equations.

13.Applications: variational solvers for Markowitz portfolio management.

Syllabus of tutorials:

1. Background: MAXCUT

2. Background: SDP

3. Background: Goemans-Williamson Hyperplane Rounding

4. Variational quantum eigensolver (VQE)

5. Quantum Approximate Optimization Algorithm (QAOA)

6. Parameter shift rule (PSR)

7. Experimenting with iteration complexity of QAOA with PSR

8. Experimenting with depth of circuits in QAOA

9. Warm-starting quantum optimization: rounded

10. Warm-starting quantum optimization: continuous-valued

11. 1:1 advice on individual projects.

12. 1:1 advice on individual projects.

13. 1:1 advice on individual projects.

Study Objective:

The course introduces adiabatic computing and variational quantum algorithms (VQA). We start with a broad introduction to variational methods in physical chemistry (e.g., for calculating ground state of small molecules) and a recapitulation of advances in theoretical computer science (computational complexity and problems such as MAXCUT). We will present the EQA Conjecture and the unique games conjecture. We will present the adiabatic theorem and quantum speedup by quantum annealing (QA). We will build up an understanding of variational quantum algorithms by introducing and analysing, in turn, Variational quantum eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), and their Warm-started variants. As applications, we will highlight variational solvers for systems of linear equations and variational solvers for Markowitz portfolio management, with some discussion of the challenges in benchmarking of VQA.

Study materials:

<kniha>

<id_lit>1</id_lit>

<autor>Abbas, A., Ambainis, A. ..., Mareček, J., et al.</autor>

<nazev>Quantum optimization: Potential, challenges, and the path forward. arXiv preprint arXiv:2312.02279. (Lectures 1 and 2.)</nazev>

</kniha>

<kniha>

<id_lit>2</id_lit>

<autor>Kungurtsev, V., Korpas, G., Marecek, J., Zhu, E. Y.</autor>

<nazev>Iteration Complexity of Variational Quantum Algorithms</nazev>

<vydavatelstvi>Quantum</vydavatelstvi>

<rok>2024</rok>

<ISBN>https://arxiv.org/abs/2209.10615 (Lecture 8)</ISBN>

</kniha>

<kniha>

<id_lit>3</id_lit>

<autor>Zhang, R., Wang, G., Johnson, P.</autor>

<nazev>Computing Ground State Properties with Early Fault Tolerant Quantum Computers</nazev>

<vydavatelstvi>Quantum 6, 761</vydavatelstvi>

<rok>2022</rok>

<ISBN>https://arxiv.org/abs/2109.13957v2 (Lectures 1 and 2)</ISBN>

</kniha>

<kniha>

<id_lit>4</id_lit>

<autor>Bittel, L., Kliesch, M.</autor>

<nazev>Training variational quantum algorithms is NP-Hard</nazev>

<vydavatelstvi>Physical review letters 127, 120502</vydavatelstvi>

<rok>2021</rok>

<ISBN>https://arxiv.org/abs/2101.07267 (Lecture 9)</ISBN>

</kniha>

<kniha>

<id_lit>5</id_lit>

<autor>Somma, R. D., Nagaj, D., Kieferová, M.</autor>

<nazev>Quantum speedup by quantum annealing</nazev>

<vydavatelstvi>Physical review letters 109(5)</vydavatelstvi>

<rok>2012</rok>

<ISBN>https://arxiv.org/abs/1202.6257 (Lecture 4)</ISBN>

</kniha>

<kniha>

<id_lit>6</id_lit>

<autor>Egger, D. J., Marecek, J., Woerner, S.</autor>

<nazev>Warm-starting quantum optimization</nazev>

<vydavatelstvi>Quantum 5, 479</vydavatelstvi>

<rok>2021</rok>

<ISBN>https://arxiv.org/abs/2009.10095 (Lectures 10, 11, 13)</ISBN>

</kniha>

Note:

Information about the course and teaching materials can be found at https://courses.fit.cvut.cz/QNI-AVM

Further information:

https://courses.fit.cvut.cz/QNI-AVM

No time-table has been prepared for this course

The course is a part of the following study plans:

• Quantum Informatics (compulsory elective course)