Adiabatic computing and variational methods

Garant předmětu:

Jakub Mareček

Přednášející:

Jakub Mareček

Cvičící:

Jakub Mareček

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

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.

Požadavky:

Osnova přednášek:

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.

Osnova cvičení:

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.

Cíle studia:

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.

Studijní materiály:

<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>

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/QNI-AVM/

Další informace:

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

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Kvantová informatika (povinně volitelný předmět)