Danylo Lykov: Quantum approximate optimization algorithm

#research #QAOA #graphs #quantum

Danylo is a Research Assistant at Argonne National Laboratory with a PhD in Computer Science from the University of Chicago. In this interview we are discussing his recent paper: "Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm"

EPISODE LINKS:
Danylo's LinkedIn profile: https://www.linkedin.com/in/danlkv/
Danylo's Google Scholar: https://scholar.google.com/citations?user=__lbrC4AAAAJ&hl=en
Link to the paper: https://www.nature.com/articles/s41534-023-00718-4

OUTLINE:
00:00 - Introduction
06:06 - 3-regular graphs
10:23 - QAOA algorithm
18:41 - Baseline classical algorithms
27:01 - Performance comparison
30:39 - Performance considerations for QAOA
37:25 - Sampling frequency
40:12 - Conclusions & next steps

CORRECTIONS:
02:24: It is stated that "Cut fraction is just the number of edges". Rather, it is the number of edges we cut divided by the total number of edges.
9:56 There is a connection between MIS and MaxCut, as between all NP-hard problems: https://courses.cs.duke.edu/fall19/compsci638/fall19_notes/lecture22.pdf
21:14: The statement "Gurobi is a branch-and-bound algorithm" is a slight simplification. Gurobi uses other approaches, especially in the beginning of the solution.
45:33: Regarding the statement "Very hard to solve classically for even 54", the largest known solution is for N=66.

SOCIAL MEDIA LINKS:
https://www.linkedin.com/in/forsstrom...
https://niklasopf.github.io/