Abstract & Overview
In this thesis, we aim to answer one research question: What is the algorithmic role of classical computing in scaling up quantum computing applicability? Quantum computers have promising potential in offering more efficient solutions to some of the most demanding computational problems in the industry. There has been phenomenal progress in the theory and realization of quantum computers in the last few decades. However, quantum computing is a nascent field of technology and scaling up its computing capacity remains impeded by many open engineering/scientific challenges. One emerging solution to alleviate some of the present limitations is finding clever use of classical pre- and post-processing techniques in tandem with quantum algorithms. This helps to advantageously use scarce quantum computing resources for only a portion of a problem that benefits the most from a quantum computer. In other words, it leads to a hybrid framework in which quantum computers are considered special-purpose co-processors for accelerating specific computational tasks. We aim to develop a hybrid theoretical framework for the role of classical algorithms in scaling up quantum computing. We investigate this by focusing on three distinct limitations. We review each limitation in the context of a different application and propose an original hybrid classical-quantum solution to it. First, we focus on classical algorithms' role in a more resource-efficient compilation and embedding of quantum programs. We propose a classical algorithm that helps to embed larger optimization problems in a quantum annealer. Then we explore how a problem decomposition technique and preprocessing of the input problem can help solve significantly larger optimization problems on a quantum computer. Finally, we propose a completely hybrid quantum algorithm for preparing ground states of quantum Hamiltonians. We achieve orders of magnitude faster convergence by combining classical optimization with variational quantum state preparation.