QUANTUM ALGORITHMS FOR BINARY OPTIMIZATION ON NOISY INTERMEDIATE SCALE QUANTUM DEVICES

Abstract

Within the Noisy Intermediate Scale Quantum (NISQ) era, quantum devices remain uncompetitive with classical solvers for Quadratic Unconstrained Binary Optimization (QUBO) problems.

In this thesis, we first develop an encoding scheme to fit problems onto quantum devices using exponentially fewer qubits. Next, we provide a framework for using additional qubits to capture correlations between the classical variables to improve the performance of the scheme. We evaluate our scheme using industry relevant QUBO instances, the largest instances of their kind to date to be featured using gate-based quantum devices. The heuristic search process limits quantum approaches from competing with classical methods.

Lastly, we introduce a method of confining the search space of solutions inspired by localization landscape function from condensed matter physics. We adapt this function to an analogous quantum state for QUBO problems, and show how this state can be prepared using NISQ-friendly approaches to outperform traditional quantum approaches.