[Colloquium] Danylo Lykov Dissertation Defense/Jun 11, 2024

[Megan Woodward via Colloquium]

This is an announcement of Danylo Lykov's Dissertation Defense.
===============================================
Candidate: Danylo Lykov

Date: Tuesday, June 11, 2024

Time:  2 pm CT


Location: JCL 298

Title: Large-scale classical simulations for development of Quantum optimization algorithms

Abstract: "Tensor networks allow to model probabilistic processes over many variables. Quantum computing is built on using complex numbers in place of conventional probability, which is an easy change to add to tensor networks. Despite the availability of efficient tools for physics simulations, simulating quantum circuits presents unique challenges, which I address in this work, specifically using the Quantum Approximate Optimization Algorithm (QAOA) as an example.

In this work I start by delving into two basic steps of using TNs for quantum simulation: creating a TN from quantum circuit and efficiently computing inference from (contracting) a TN. Both steps have interesting optimizations that allow for orders of magnitude cost reduction. This also includes discussion on how to contract TNs on GPUs.

For large-scale contraction of tensor networks, I propose a step-dependent parallelization approach which performs slicing of partially contracted tensor network. Finally, I study tensor network contractions on GPU and propose an algorithm of contraction which uses both CPU and GPU to reduce GPU overhead. In our benchmarks, this algorithm reduces time to solution from 6 seconds to 1.5-2 seconds.

These improvements allow to predict the performance of Quantum Approximate Optimization Algorithm (QAOA) on MaxCut problem without running the quantum optimization.
This predicted QAOA performance is then used to systematically compare to the classical MaxCut solvers. It turns out that one needs to simulate a deep quantum circuit in order to compete with classical solvers.

In search for provable speedups, I then turn to a different combinatorial optimization problem, Low-Autocorrelation Binary Sequences (LABS). This study involves simulating ground state overlap for deep circuits. This task is more suited for a state vector simulation, which requires advanced distributed algorithms when done at scale."

Advisors: Fred Chong and Yuri Alexeev

Committee Members: Fred Chong, Yuri Alexeev, and Robert Rand






-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240529/f31f72d6/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: phd_thesis_uc (1).pdf
Type: application/pdf
Size: 1757853 bytes
Desc: phd_thesis_uc (1).pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240529/f31f72d6/attachment-0001.pdf>