Scott D Pakin

This work develops a novel approach to exploit synthesized, approximate circuits for the ansatz of variational quantum algorithms (VQA) and demonstrates its effectiveness for NchooseK, a domain-specific language supporting quantum-based solving of constraint-based problems. Synthesis is generalized to produce parametric circuits of short depth in close approximation of the original circuit offline. This removes syn-thesis from the critical path (online) between repeated quantum circuit executions of VQA while reducing circuit depth, thereby resulting in higher fidelity results than the baseline without synthesis. Simulation experiments indicate improvements of 98% on average. Further, experiments indicate that this approach can obtain viable solutions when the baseline could not. All of this is achieved with an average variation in circuit depth of less than 10%.

Specialized processors designed to accelerate tensor operations are evolving faster than conventional processors. This trend of architectural innovations greatly benefits artificial intelligence (AI) workloads. However, it is unknown how well AI-optimized accelerators can be retargeted to scientific applications. To answer this question we explore (1) whether a typical scientific modeling kernel can be mapped efficiently to tensor operations and (2) whether this approach is portable across diverse processors and AI accelerators. In this paper we implement two versions of tracer advection in an ocean-modeling application using PyTorch and evaluate these on one CPU, two GPUs, and Google's TPU. Our findings are that scientific modeling can observe both a performance boost and improved portability by mapping key computational kernels to tensor operations.

This work presents a generalization of NchooseK, a constraint satisfaction system designed to target both quantum circuit devices and quantum annealing devices. Previously, NchooseK supported only hard constraints, which made it suitable for expressing problems in NP (e.g., 3-SAT) but not NP-hard problems (e.g., minimum vertex cover). In this paper we show how support for soft constraints can be added to the model and implementation, broadening the classes of problems that can be expressed elegantly in NchooseK without sacrificing portability across different quantum devices. Through a set of examples, we argue that this enhanced version of NchooseK enables problems to be expressed in a more concise, less error-prone manner than if these problems were encoded manually for quantum execution. We include an empirical evaluation of performance, scalability, and fidelity on both a large IBM Q system and a large D- Wave system.

Characterization of program execution plays a key role in performance improvement. There are numerous transformations applied to each step a program takes on its lowering from source code to a compiler intermediate representation to machine language to microarchitecture-specific execution. The unpredictable benefit of each transformation step could lead a notionally superior algorithm to exhibit inferior performance once actually run, and it can be opaque at what step in the transformation path contradicted the code developer's assumptions. However, conventional approaches to program execution characterization consider the behavior after only a single one of those steps, which limits the information that can be provided to the user. To help address the issue of myopic views of program execution, this paper presents a novel cross-level characterization approach for understanding the behavior of program execution at different levels in the process of writing, compiling, and running a program. We show that this approach provides a richer view of the sources of performance gains and losses and helps identify program execution in a more accurate manner.

Program behavior can be defined as a collection of executions [1]. Program behavior strongly relates to actual program performance but can be complicated to be characterized and analyzed. Characterization is important as it helps better understand program behavior by measuring various operations a program performs. There are many existing techniques [2]-[7] for program characterization, which operate at different levels of instrumentation: source code, intermediate representation (IR), instruction set architecture (ISA), and CPU microarchitecture. Each of these levels provides different capabilities and limitations. In this paper, we introduce Cross-Level Characterization (CLC), an analysis of similarities and differences in resource counts as measured at each level of instrumentation during a program's transformation from source code through execution on a specific microarchitecture.

Quadratic pseudo-Boolean functions (i.e., quadratic functions with real-valued coefficients and two-valued variables) are the native input to quantum annealers and also a common problem format to optimize with the QAOA algorithm on circuitmodel quantum computers. In both cases, large, complex optimization problems can be expressed in terms of combinations of simpler problems. A key challenge in problem set-up lies in finding the coefficients for the constituent sub-problems. These need to be chosen such that the function is minimized on valid inputs and is higher elsewhere. One difficulty is that it is not possible in general to solve for a sub-problem's coefficients without introducing ancillary variables, the number of which and their corresponding per-row values being unknown a priori. These unknowns lead to solving for a sub-problem's coefficients being an NP-complete problem.In this paper we present a simple heuristic that considers a prioritized subset of the exponential number of possibilities for each per-row ancillary variable. Using this heuristic, coefficients can be found substantially faster than would be possible using a brute-force search and with less software complexity than is required by prior approaches.

A quantum annealer solves optimization problems by exploiting quantum effects. Problems are represented as Hamiltonian functions that define an energy landscape. The quantum-annealing hardware relaxes to a solution corresponding to the ground state of the energy landscape. Expressing arbitrary programming problems in terms of real-valued Hamiltonian-function coefficients is unintuitive and challenging. This paper addresses the difficulty of programming quantum annealers by presenting a compilation framework that compiles a subset of C code to a quantum machine instruction (QMI) to be executed on a quantum annealer. Our work is based on a modular software stack that facilitates programming D-Wave quantum annealers by successively lowering code from C to Verilog to a symbolic "quantum macro assembly language" and finally to a device-specific Hamiltonian function. We demonstrate the capabilities of our software stack on a set of problems written in C and executed on a D-Wave 2000Q quantum annealer.

Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.

From a compiler's perspective, a quantum annealer represents a fundamentally different hardware target from a CPU, GPU, or other von Neumann architecture. Quantum annealers are special-purpose computers that use quantum effects to heuristically determine the set of Boolean variables that minimize a quadratic pseudo-Boolean function (an NP-hard problem). Natively programming such systems involves supplying them with a vector of function coefficients and receiving a vector of function-minimizing Booleans in return. The contribution of this work is to demonstrate how to compile conventional code into a minimization problem for solution on a quantum annealer. The resulting code can run either forward (from inputs to outputs) or backward (from outputs to inputs). We show how this capability can be exploited to simplify the expression and solution of problems in the NP complexity class.