Title: Combinatorial Optimization with Variational Quantum Imaginary Time Evolution

Abstract: While quantum computing can achieve exponential speed-ups for many problems, it is unclear, what speed-up it can bring for NP-hard Combinatorial Optimization problems. In this thesis, we investigate the potential of Variational Quantum Imaginary Time Evolution (VarQITE), a recently proposed quantum heuristic that can be used to solve classically hard problems. The algorithm can always find the optimal solution using an appropriate variational circuit of sufficient depth, potentially exponential in the number of qubits. However, it is unclear how the minimum required depth increases with the number of variables for a particular problem. We run exact and shot-based quantum simulations, to find how the requirements for a successful VarQITE scale with the problem size. While we find that VarQITE performs well on the tested problems, it requires further analysis on problems of increasing size to ultimately answer the question of quantum advantage for combinatorial optimization.