Quantum Algorithms for Machine Learning, Optimization, and Simulation

In this report we survey quantum algorithms developed by the team in the areas of machine learning, optimization, and simulation of physical systems. First, we consider purely classical computational tasks such as classification problems for data with group structure, learning of Boolean functions, combinatorial optimization problems including MaxCut and graph k-coloring, linear programming, and statistical inference based on Markov Chain Monte Carlo algorithms. For each of these problems we give a quantum algorithm improving upon the state-of-the-art. Secondly, we consider problems relevant for chemistry and material science where the goal is to simulate certain properties of a quantum many body system. This includes ground state preparation for Hamiltonians describing electronic structure of molecules and systems with a topological quantum order that host non-abelian anyons. We show how to tackle these simulation problems more efficiently by combining classical and quantum computational resources. Finally, we investigate computational complexity of simulating quantum many-body systems at the thermal equilibrium and improve existing algorithms for simulation of open quantum systems whose dynamics is governed by the Lindblad master equation.