Towards a Scalable Software Stack for Resource Estimation and Optimization in General-Purpose Quantum Computers

Abstract

Recent years have seen tremendous progress in quantum computing research, due in no small part to significant investment from major companies (Google, NASA, IBM, Intel, Microsoft) and governments (USA, EU, Japan, Australia). Small quantum computers have already been built, and medium-size computers with 100 - 1000 qubits are expected in the next few years. Building larger scale computers can have profound effects on the fundamentals of feasible computation, with major applications in cryptography, medicine and artificial intelligence.

In contrast to mathematical algorithms and physical fabrication, quantum software tools have received relatively little attention. This is despite the fact that there is still a wide gap between the resource requirements of quantum applications (qubits and time) and feasible physical implementations. Good software tools can help bridge this gap.

This thesis conducts an end-to-end study of system design issues for error-corrected, general-purpose quantum computers, focusing especially on design decisions arising in compilation, mapping, and scheduling stages. While drawing from decades of classical system design, it proposes novel techniques tailored to the specific constraints of the quantum domain, such as the central importance of error correction, problems of scalability, and alternative forms of data communication. By evaluating a wide range of potential applications, architectures and target technologies, valuable insights are obtained regarding design tradeoffs, guiding future developments on more efficient paths.

Crucially, this thesis answers a question that could not have been accurately answered without the tools for realistic modeling of such systems: what is the best type of error correction for running a certain program on a given device? This question gains significant importance given that error correction is the leading source of cost overhead in highly fragile quantum systems. Various conditions are identified under which certain error correction codes are more efficient than others. It is shown that the rate of communication contention, which is directly related to application characteristics, can play a central role in determining the best method of communication and hence the type of error correction.