Adiabatic computing and variational methods

Garant předmětu:

Přednášející:

Cvičící:

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

Nutno doplnit

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:

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)

Poznámka:

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

Další informace:

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

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

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

• Quantum Informatics (volitelný předmět)