Quantum computers [55] have been at the bleeding edge of computing technology for nearly 40 years, and while there are several barriers that prevent their immediate utility, research in this area continues to progress due to their immense promise. Specifically, these systems have been theorized to decrease the complexity of several important problems, most tangibly violating the security of RSA encryption [56] and possibly the extended Church-Turing thesis [8]. In an effort to harness the revolutionary potential of these systems, research has largely focused around the physical construction of at-scale quantum devices. However, the software infrastructure that compiles programs for these devices also requires further development before the benefits of the quantum era can be realized; this area has been traditionally under-emphasized.

In the near-term, Noisy Intermediate-Scale Quantum (NISQ) devices maintain only sparse connectivity between qubits, meaning that quantum programs assuming dense connectivity must be efficiently routed onto the hardware. If done naïvely, this process often requires the compiler to insert an overwhelming number of data movement operations; these alone can violate the practicability of the program since quantum states are fragile and degrade rapidly if the critical path is too long. Existing approaches have made great strides in making this process more efficient, but have failed to capitalize on relevant advancements in the classical domain and are plagued by a representation mismatch that limits the scope of program transformations that can be applied.

In this work, we present a novel approach to compiling more efficient quantum programs. We capture the input algorithm as a high-level mathematical transform, and after generating a multitude of architecture-compliant programs directly from that specification, we apply traditional search techniques to select the best output. This approach allows us to produce shorter quantum programs as we can leverage high-level symmetries of the target transform to perform global rewrites; this task is nearly impossible given only a program stream. To implement the proposed framework we leverage SPIRAL [26][24][54], a code generation platform built on the GAP [57] computer algebra system, and restate quantum computing in terms of pure linear algebra such that we can treat this seemingly domain-specific problem as a generic matrix factorization task. We ultimately demonstrate that SPIRAL is a viable supplemental tool for future quantum software frameworks, and provides tangible benefits when used to compile symmetric algorithms like the Fourier tranform.

111 pages

Thesis Committee:
Franz Franchetti (Chair)
Seth Goldstein

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu