Hybrid Quantum-Classical Algorithms for Solving Combinatorial Optimization and Material Science Problems

<p dir="ltr">Noisy Intermediate-Scale Quantum (NISQ) computers are expected to surpass classical computers in terms of computational capabilities in the near future. In particular, combinatorial optimization problems are estimated to be among the most prominent areas to benefit from quantum computing. However, the sizes of the problems that could be solved on NISQ computers are limited by the number of qubits, their connectivity, high noise, and short coherence times. Hybrid quantum classical algorithms are one of the approaches in use today to tackle practical applications with existing quantum computers. These algorithms divide problems into classical and quantum subcomponents and achieve the `best of both worlds.' This thesis investigates the applications of hybrid algorithms in various combinatorial optimization problems: dynamic asset allocation with expected shortfall, maximum independent set, and vehicle routing problems. Furthermore, we benchmark our algorithms on different quantum or quantum-inspired platforms, including D-Wave's quantum annealers, QuEra's quantum computers with neutral atoms, Fujitsu's digital annealer and Quantinuum's quantum computers with trapped ions. Our methods perform competitively with state-of-the-art classical solvers in many instances. Additionally, we demonstrate the scalability of our algorithms for distributed quantum computer architectures.</p><p><br></p><p dir="ltr">Another area of study this thesis explores is simulations of quantum dynamics of geometrically frustrated Ising models. Geometric frustration in two-dimensional Ising models allows for a wealth of exotic universal behavior, both Ising and non-Ising, in the presence of quantum fluctuations. While the quantum dynamics of modestly-sized systems can be simulated classically using tensor-based methods, these methods become infeasible for larger lattices. This thesis investigates quantum dynamics of the triangular antiferromagnet and Villain models in a transverse field and presents an iterative, classical 'shimming' procedure to calibrate qubits on D-Wave quantum annealers, achieving coherent quantum simulations. Furthermore, on Quantinuum's trapped-ion platform, we study classical Ising spin models on unit cells of square, Shastry-Sutherland and triangular lattices. Using the quantum approximate optimization algorithm (QAOA), we observe that only a modest number of measurements (≲100) are needed to find the ground state, demonstrating the viability of QAOA for materials ground state preparations.</p>