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:

Nutno doplnit

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:

1.Abbas, A., Ambainis, A. ..., Mareček, J., et al.: Quantum optimization: Potential, challenges, and the path forward. arXiv preprint arXiv:2312.02279. (Lectures 1 and 2.)

2. Kungurtsev, V., Korpas, G., Marecek, J., Zhu, E. Y.: Iteration Complexity of Variational Quantum Algorithms

Quantum 2024

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

3. Zhang, R., Wang, G., Johnson, P.: Computing Ground State Properties with Early Fault Tolerant Quantum Computers

Quantum 6, 761 2022

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

4. Bittel, L., Kliesch, M.: Training variational quantum algorithms is NP-Hard

Physical review letters 127, 120502 2021

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

5. Somma, R. D., Nagaj, D., Kieferová, M.: Quantum speedup by quantum annealing

Physical review letters 109(5) 2012

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

6. Egger, D. J., Marecek, J., Woerner, S.: Warm-starting quantum optimization

Quantum 5, 479 2021

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

Note:

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

Further information:

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

No time-table has been prepared for this course

The course is a part of the following study plans:

• Quantum Informatics (elective course)