Co-designing Quantum Computer Architectures and Algorithms to Bridge the Quantum Resource Gap

Abstract

Quantum computing is a new computational paradigm based on the laws of quantum physics that have been developed over the last century. Quantum computers (QCs) manipulate quantum states and exploit non-classical phenomena, such as superposition and entanglement, to perform computations. Given this computational model, many quantum algorithms have been developed which are theoretically capable of outperforming any classical computer for certain applications such as factoring large integers, optimization, and simulating highly entangled quantum systems. However, the quantum programs implementing these high impact applications are extremely resource demanding. Their time and space requirements outstrip the capabilities of current QC systems by many orders of magnitude. I refer to this mismatch between the resources demanded by applications and what is available on current hardware as the Quantum Resource Gap (QRG). This dissertation presents a strategy for overcoming the QRG by advocating for the design of domain-specific quantum accelerators. I discuss how this strategy may be pursued using quantum benchmarks and program profiling to identify matches between applications and architectures that are well suited to one another. Once a particular application-architecture match is found, the algorithm's execution can be optimized with cross-layer, co-design techniques that incorporate relevant information from across the entire hardware-software stack. To demonstrate the advantages of this approach, I discuss three examples covering molecular simulation, data set clustering, and constrained combinatorial optimization applications.