Quantum Circuit Optimization with SPIRAL

What is it?

In the SPIRAL quantum package we define the primitives and directives necessary to leverage SPIRAL’s code generation framework for quantum circuit optimization. The input to our system is a functional circuit description written in terms of symbolic transform objects. SPIRAL outputs both a simplified mathematical formula representing the optimized circuit implementation and QASM [2] code that can be executed on a quantum computer.

Overview

Quantum computers have been at the bleeding edge of computing technology for nearly 40 years and promise to make several classically difficult problems tractable. Specifically, these systems have been theorized to violate the security of RSA encryption [7] and possibly even the extended Church-Turing thesis [4, 3]. In an effort to harness the revolutionary potential of these systems, research has largely focused on the physical construction of at-scale quantum devices. However, despite many hardware and algorithm breakthroughs, the software infrastructure that compiles programs for these devices requires further development in order to produce sufficiently scalable code.

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 [1] but have not yet fully capitalized on relevant advancements in the classical domain due to their input representations. Specifically, because compilers commonly take an imperative program stream as input (i.e. a quantum circuit), we are often limited to local, peephole optimizations since we lack prior knowledge of the algorithm being compiled.

Using SPIRAL [6], we instead consider the global optimization problem. Rather than mapping individual programs onto quantum hardware, we capture the input as a high-level mathematical transform and generate a multitude of architecture-compliant programs directly from that specification, allowing us to search over a much larger space of implementations to select the best output. Specifically, this is achieved by casting circuit generation as a sparse matrix factorization task and recursively searching over a host of divide-and-conquer decomposition rules in the breakdown phase. By generating programs from the top down, we retain high-level information about the program we are compiling and can explore algorithm-specific rewrites that are nearly impossible to recognize given only a program stream.

Benchmarks

Our initial version can compete with Qiskit (v0.24.1) [1] and Tket (pytket v0.13.0) [5] when comparing SWAP count on select circuits. SPIRAL takes in programs expressed at a high level of abstraction, and therefore relies on algorithm-specific heuristics that consider the dataflow and qubit topology in order to prune unpromising rule trees. We developed an initial set of heuristics for the quantum Fourier Transform and intend to extend our approach to other algorithms.

poster barchart

Software Download

A `First Look` version of the SPIRAL Quantum package, initially presented at SC20, can be downloaded here.

An extended version, presented at HPEC2021, can be downloaded here (coming soon).

For further reading, you can view the following:

References

  1. H. Abraham et al., "Qiskit: An Open-source Framework for Quantum Computing," 2019. doi:10.5281/zenodo.2562110
  2. Andrew W. Cross, Lev S. Bishop et al, ”Open Quantum Assembly Language,” arXiv preprint arXiv:1707.03429, 2017
  3. F. Arute et al., "Quantum Supremacy using a Programmable Superconducting Processor," Nature, vol. 574 (2019), pp. 505–510
  4. E. Bernstein and U. Vazirani, "Quantum Complexity Theory," SIAM J. Comput., 1997, pp. 1411–1473. First appeared in ACM STOC 1993. doi:10.1137/S0097539796300921
  5. A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmons and S. Sivarajah, “On the Qubit Routing Problem,” in 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Dagstuhl, Germany, May 2019, pp. 1-32. doi:10.4230/LIPIcs.TQC.2019.5
  6. F. Franchetti, et al. "SPIRAL: Extreme Performance Portability," Proceedings of the IEEE, Vol. 106, No. 11, 2018. Special Issue on From High Level Specification to High Performance Code
  7. P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994. doi:10.1137/S0097539795293172

Copyrights to many of the above papers are held by the publishers. The attached PDF files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. Some links to papers above connect to IEEE Xplore with permission from IEEE, and viewers must follow all of IEEE's copyright policies.

More Information

Contact: Scott Mionis, smionis (at) xxxandrew.cmu.edu (delete xxx)

Pittsburgh Quantum Institute (PQI), Franz Franchetti, Faculty Member of PQI