Session RR08: V: Quantum Software Stack

Verifiable Quantum Advantage without Structure

"Structure" has long played a central role in proposals for super-polynomial quantum advantage. This is especially true for problems whose solutions can be efficiently verified, where all prior results require algebraic computational conjectures or oracles with very specific features. We show a new approach for verifiable quantum advantage which, for a reasonable complexity-theoretic notion of "structure", requires no structure at all.   

Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis

We propose a novel hierarchical qubit mapping and routing framework. First, a circuit is decomposed into blocks that span an identical number of qubits. In the second permutation-aware synthesis (PAS) stage, each block is synthesized with different input and output permutations and different topologies. The third stage is a permutation-aware mapping (PAM) algorithm that maps and routes the blocks based on the permutation information. Our approach is based on the following insight: 1) with PAS, any block can implement an arbitrary input → output qubit mapping  (e.g. q0 → q1) that minimizes its communication; and 2) with PAM, for two adjacent blocks we can select input-output permutations that optimize each block together with the amount of communication required at a block boundary. While existing mapping algorithms only introduce ''minimal''  communication via inserting SWAP or bridge gates, the PAS+PAM approach can additionally remove any spurious communication. 

Our experiments show that we can produce better quality circuits than existing mapping algorithms or commercial compilers (Qiskit, Tket). For a combination of benchmarks, we significantly reduce the two-qubit gate count. Furthermore, the approach scales and it can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure.   

Nuwa: A Quantum Circuit Transpiler Based on a Finite-Horizon Heuristic for Placement and Routing

We introduce a novel transpiler for the placement and routing of quantum circuits on arbitrary target hardware architectures. We use finite-horizon, and optionally discounted, reward functions to heuristically find a suitable placement and routing policy. We employ a finite lookahead to refine the reward functions when breaking a tie between multiple policies. We benchmark our transpiler against multiple alternative solutions and on various test sets of quantum algorithms to demonstrate the benefits of our approach.   

Intermediate Representations for Quantum Computing

The proliferation of qubit manipulation and generation methods (ranging from optical to topological qubits) has now been matched by an explosion in terms of user-level libraries (Q#, Qiskit, etc.) which have somehow been termed "quantum programming languages". We will develop on this theme by contrasting the classical computing programming languages and the algorithms / computational model therein (von Neumann machines) and demonstrate the gap manifest between what are essentially libraries and not programming languges. In particular we will cover the closest analogs in existing libraries to formal language, grammars, parsers and finally type safety. We will explore some programming paradigms (functional, imperative, object oriented) for typical quantum algoritms (Shor's, Grovers, Simmulated Annealing). Finally, we will posit test suites for a true quantum computing language, one which has strict correspondence to the formal theory of compilers and can express algorithms compactly (grammar) while also ensuring correctness (compilation). We note that the core of compiler development has been execution independence, the ability to run on multiple platforms, and to this end, rather than describing an entire language down to a specific qubit generation method, we will instead focus on developing a quantum intermediate representation akin to LLVM compiler project.   

Intel Quantum SDK Version 1.0: Extended C++ Compiler, Runtime and Quantum Hardware Simulators for Hybrid Quantum-Classical Applications

The Intel Quantum Software Development Kit (SDK) is a full-stack platform allowing programmers to design their applications on a system consisting of an LLVM-based compiler providing intuitive C++ language extensions to support the expression and optimizations of quantum circuits. The SDK provides a quantum runtime library to control the context switch between classical and quantum kernels to perform hybrid execution. The quantum runtime allows a set of quantum circuit parameters to be determined at runtime. With these capabilities, both quantum and classical procedures of a variational algorithm can be specified in the same program and only need to be compiled once for all iterations. This design makes the execution latency of a variational algorithm significantly reduced. A set of quantum simulators are integrated in the SDK, including a simulation of Intel quantum hardware (qubit control processor, control electronics and quantum dot qubits). The Intel Quantum SDK is designed to provide a uniform interface to users to target ideal qubit simulators, realistic Intel quantum hardware simulators, as well as future Intel quantum hardware. The Intel Quantum SDK can efficiently perform optimization, compilation, and execution of scalable hybrid quantum-classical variational algorithms.   

Efficient execution of quantum algorithms using the Intel Quantum SDK

Quantum computers are expected to be capable of solving certain classically intractable problems efficiently. A practical quantum computer will require high-quality physical qubits, dedicated control electronics, and a software stack capable of generating hardware-targeted quantum circuits as well as processing results from quantum circuit execution. The efficient transformation of quantum algorithms into practical quantum circuits is imperative in extracting the best performance from available quantum hardware. In this talk I will describe the capabilities of the Intel Quantum SDK which utilizes many optimizations within the quantum compiler, as well as generates binary executables to enable tight integration during execution of workloads -- especially for variational algorithms. Examples will be provided to demonstrate the benefits of a holistic optimization approach in contrast to a collection of discrete local optimizations. The tools available to examine the flow through the software toolchain will also be surveyed.   

A Functional Approach to the Modular Construction of Quantum Logic: Part I

Many quantum languages use an object-oriented approach for the construction and manipulation of quantum circuits and logic. However, this approach is challenging for a compiled quantum binary in a NISQ accelerator model, as hardware-native instruction blocks must be determined and built at compile time. Thus the compiler must reason about the structure of the quantum logic without runtime memory access, i.e. it must avoid side-effects. Our solution is to introduce a quantum functional language extension to the C++ derived language of the Intel Quantum SDK. We introduce a new built-in type which abstracts a quantum accelerator call, allowing it to be passed into and out of C++ functions before being passed to the quantum accelerator. We also include several core built-in functions that users and libraries can use to build more elaborate transformations. In this talk, we introduce the basic concepts of this functional extension, different parts of its syntax and how it can be used alongside other C++ constructs to build modular quantum algorithms with the Intel Quantum SDK.   

A Functional Approach to the Modular Construction of Quantum Logic: Part II

Many quantum languages use an object-oriented approach for the construction and manipulation of quantum circuits and logic. However, this approach is challenging for a compiled quantum binary in a NISQ accelerator model, as hardware-native instruction blocks must be determined and built at compile time. Thus the compiler must reason about the structure of the quantum logic without runtime memory access, i.e. it must avoid side-effects. Our solution is to introduce a quantum functional language extension to the C++ derived language of the Intel Quantum SDK. We introduce a new built-in type which abstracts a quantum accelerator call, allowing it to be passed into and out of C++ functions before being passed to the quantum accelerator. We also include several core built-in functions that users and libraries can use to build more elaborate transformations.

In this talk, we walk through the basic methods used in the compilation of this functional language extension, including the use of the LLVM toolchain for parsing and generating an intermediate representation (IR) and the use of a Pauli-based representation to uniformly build the quantum logic from the call structure of the IR.