Computer Science Masters Thesis Presentation

Wednesday, May 19, 2021 - 3:00pm to 4:00pm


Virtual Presentation - ET Remote Access - Zoom


SCOTT MIONIS, Masters Student

Optimized Quantum Circuit Generation with SPIRAL

Quantum Computers have been at the bleeding edge of computational technology for nearly 40 years, and while the challenges most often touted are those concerning the physical construction of such a device, the efficient compilation and optimization of quantum algorithms is not nearly as developed as will be necessary to realize the benefits of the quantum era. In the near-term, Noisy Intermediate-Scale Quantum (NISQ) devices only maintain sparse connectivity between qubits, meaning that quantum programs assuming dense connectivity must be efficiently routed onto the hardware. This process often requires the compiler to insert an overwhelming number of data movement instructions; these alone can violate the practicability of the circuit, since quantum states are fragile and degrade rapidly with circuit depth. In this work we leverage SPIRAL, a code generation platform built on the GAP computer algebra system, and present an application of the system towards optimizing quantum circuits. SPIRAL takes, as input, the adjacency information of the target hardware and the desired algorithm as expressed in a high-level syntax. Utilizing a series of decomposition rules that can be natively expressed in SPIRAL via the matrix or tensor product of smaller non-terminals, we constructively form an optimized quantum program with both the architecture and high-level algorithmic symmetries as first-class design constraints. This approach alleviates the traditional need to transplant, or 'transpile', a pre-compiled quantum assembly (QASM) program; This process often relies on peephole optimizations and is limited to manipulating the program stream, from which it is extremely difficult to derive high-level transformations. Alternatively, we generate architecture-compliant code directly from an algorithmic specification, allowing us to leverage high-level directives to make smarter scheduling decisions. We then cast circuit generation as a search problem, with each possible sequence of divide-and-conquer decomposition rules providing one of many paths from algorithm to physical implementation. We ultimately demonstrate that SPIRAL is a viable supplemental tool for future quantum software frameworks, and provides tangible benefits when compiling symmetric algorithms like the fourier transform.

Thesis Committee
Franz Franchetti (Chair)
Seth Goldstein

Zoom Participation. See announcement.

For More Information, Contact:


Master's Thesis Presentation