Delinearization of Polyhedral Abstractions to Characterize Quantum Assembly

Abstract

Increasingly complex quantum algorithms are designed in a hardware-agnostic fashion, implemented leveraging high-level programming languages, and then lowered to simpler sequences of quantum operations (gates) using a format such as the Open Quantum Assembly (OpenQASM). Unfortunately, lowering the program to a quantum assembly representation also results in a loss of structured information that can be extremely useful in later compilation passes. As a result, several quantum optimization passes simply operate on arbitrary network layers determined by the QASM-level program's dependence graph, or focus on relatively small sliding windows with peephole optimizations. For the era of Noisy Intermediate-Scale Quantum (NISQ) devices and beyond, more robust quantum compiler passes are required to tailor these decompositions and subsequent optimizations to match stringent topological and fidelity constraints.

In this paper we introduce QRANE, a tool for lifting QASM-based quantum programs into the polyhedral compilation model. QRANE groups and identifies linear relationships in the qubit indices used in two-qubit and single-qubit gates to construct iterations domains and access relations, all while preserving the original semantics of the quantum program. We explore various policies for deciding among different delinearization strategies, and discuss their effect on the quality of the reconstruction. Our experimental evaluation demonstrates the high coverage and efficiency of QRANE while also permitting to assess the potential benefits of affine transformations on large quantum circuits. Specifically, QRANE reconstructs affine iteration domains of up to 6 dimensions, and consisting of up to 128 points per domain. The parallel reconstruction of affine abstractions achieves strong scaling, facilitating the usage of higher search parameters to produce denser domains. Preliminary results also show the strong impact that affine transformations can have once domain-specific knowledge is considered.