Optimized Quantum Circuit Generation with SPIRAL

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 naively,

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 transform.