Toward quantum advantage: Quantum variational algorithms for NP-hard approximations

Abstract

Quantum computing is a computing paradigm that promises computational advantage (and in some cases, supremacy) across many domains. Diverse applications across fields (cryptography, complexity theory, generative chemistry, finance) make the development and understanding of quantum algorithms extremely valuable. In this thesis, we consider the application of quantum computing to NP-hard approximation. Through the use of semidefinite relaxations of linear program formulations of the maximum graph bisection problem, and quantum-classical hybrid methods, we show that a novel quantum variational method (HTAAC-QSDP) provides solution quality equivalent to the best classical approximation algorithms. We simulate these hybrid circuits using feed-forward neural networks and determine that the solution quality (cut ratio) achieved is CQ/CSDP = 0.987 for the training graph and CQ/CSDP ≥ 0.97 for all other graphs, where CQ is the cut achieved by the quantum variational method and CSDP is the cut achieved by the classical solver. Our results experimentally verify the results provided in literature and show that quantum variational algorithms may be the path towards achieving near-term quantum advantage.