Programming the Quantum Future

The earliest computers, like the ENIAC, were rare and heroically difficult to program. That difficulty stemmed from the requirement that algorithms be expressed in a “vocabulary” suited to the particular hardware available, ranging from function tables for the ENIAC to more conventional arithmetic and movement operations on later machines. Introduction of symbolic programming languages, exemplified by FORTRAN, solved a major difficulty for the next generation of computing devices by enabling specification of an algorithm in a form more suitable for human understanding, then translating this specification to a form executable by the machine. The “programming language” used for such specification bridged a semantic gap between the human and the computing device. It provided two important features: high-level abstractions, taking care of automated bookkeeping, and modularity, making it easier to reason about sub-parts of programs.

Back to Top

Quantum computation is a computing paradigm where data is encoded in the state of objects governed by the laws of quantum physics. Using quantum techniques, it is possible to design algorithms that outperform their best-known conventional, or classical, counterparts.

While quantum computers were envisioned in the 20th century, it is likely they will become real in the 21st century, moving from laboratories to commercial availability. This provides an opportunity to apply the many lessons learned from programming classical computing devices to emerging quantum computing capabilities.

Back to Top

Quantum Coprocessor Model

How would programmers interact with a device capable of performing quantum operations? Our purpose here is not to provide engineering blueprints for building an actual quantum computer; see Meter and Horsman¹³ for a discussion of that agenda. What we describe is a hypothetical quantum architecture in enough detail to cover how one would go about programming it.

Viewed from the outside, quantum computers perform a set of specialized operations, somewhat analogous to a floating-point unit or a graphics coprocessor. We therefore envision the quantum computer as a kind of coprocessor that is controlled by a classical computer, as shown schematically in Figure 1. The classical computer performs operations (such as compilation, conventional bookkeeping, correctness checking, and preparation of code and data) for the quantum unit. The quantum coprocessor performs only the quantum operations (such as initializations, unitary operations, and measurements). This model of quantum computation is known as Knill’s QRAM model¹¹ and is believed to ultimately be the most likely realization of quantum computers.¹³

Certain hardware-intensive low-level control operations (such as quantum error correction) may optionally be integrated directly into the quantum unit. We envision the quantum unit containing a high-speed, specialized firmware in charge of such a low-level “quantum runtime.” The quantum firmware is specific to each physical realization of a quantum coprocessor, programmed separately off site. Although tightly dependent on the physical specifications of the particular hardware, the quantum firmware is independent of the algorithms to be run.

The source code of any quantum programs resides on the classical unit. Through a conventional classical compilation, it produces executable code to be run on the conventional computer. We envision the quantum coprocessor will communicate with its classical controller through a message queue on which the classical computer is able to send elementary instructions (such as “allocate a new quantum bit,” “rotate quantum bit x,” and “measure quantum bit y“). After an operation is performed, the classical computer can read the results from the message queue. In this model, the control flow of an algorithm is classical; tests and loops are performed on the classical device. Both classical and quantum data are first-class objects.

Via the message queue, the classical runtime receives feedback (such as the results of measurements) from the quantum unit. Depending on the algorithm, this feedback may occur only at the end of the quantum computation (batch-mode operation) or interleaved with the generation of elementary instructions (online operation). The possibility of online operation raises additional engineering challenges, as it requires the classical controller to be fast enough to interact with the quantum runtime in real time. On the other hand, many common quantum algorithms require only batch-mode operation. We assume a quantum programming model flexible enough to address either type of operation.

As with a conventional programming environment, we separate the logical data structures from their physical representation on the hardware. In our proposed paradigm, the algorithms are implemented at the logical level, but the quantum bits are physically encoded at the hardware level. The tasks of mapping logical quantum bits and operations to stable physical representations, and of applying suitable error correction, are left to the compiler and to the quantum firmware.

Back to Top

Describing Quantum Algorithms

To motivate the need for an expressive quantum programming language (QPL), we briefly consider some of the ways quantum algorithms are typically specified in the literature. A quantum algorithm generally consists of a mix of classical and quantum operations. The quantum parts of an algorithm are usually aggregated into quantum circuits, in which quantum gates are represented by boxes and quantum bits by wires, as in Figure 2. Some restrictions apply to circuits. For example, they cannot contain loops, so wires must flow in only one direction. The gates can have multiple inputs and outputs. With the exception of gates corresponding to the creation and destruction (measurement) of quantum bits, elementary operations are always unitary transformations, implying they must have the same number of inputs and outputs.

A typical description of a quantum algorithm consists of one or more of the following pieces, which may be specified at various levels of formality:

Mathematical equations. These can be used to describe state preparations, unitary transformations, and measurements. For example, Harrow et al.⁹ described a quantum algorithm for solving linear systems of equations. A certain subcircuit of the algorithm is defined as follows:

Invocation of known quantum subroutines. Examples include the quantum Fourier transform, phase estimation, amplitude amplification, and random walks. For example, the algorithm in Harrrow et al.⁹ asks to “decompose |b〉 in the eigenvector basis, using phase estimation”;

Oracles. These are classical computable functions that must be made reversible and encoded as quantum operations. They are often described at a very high level; for example, Burham et al.³ defined an oracle as “the truth value of the statement f(x) ≤ f(y)”;

Circuit fragments. For example, the circuit in Figure 3 is from Childs et al.⁴ Note, strictly speaking, the figure describes a family of quantum circuits, parameterized by a rotation angle t and a size parameter n, as indicated by ellipses “…” in the informal circuit. In a formal implementation, this parameter dependency must be made explicit;

High-level operations on circuits. Examples include “inversion,” where a circuit is reversed, and “iteration,” where a circuit is repeated, as in Figure 4; and

Classical control. Many algorithms involve interaction between the classical unit and the quantum unit. This interaction can take the form of simple iteration, running the same quantum circuit multiple times from scratch, as in Figure 5, or of feedback, where the quantum circuit is generated on the fly, possibly based on the outcome of previous measurements, as in Figure 6.

Back to Top

Requirements for QPLs

Ideally, a quantum programming language should permit programmers to implement quantum algorithms at a level of abstraction that is close to how one naturally thinks about the algorithm. If the algorithm is most naturally described by a mathematical formula, then the programming language should support such a description where possible. Similarly, if the algorithm is most naturally described by a sequence of low-level gates, the programming language should support this description as well.

The standard methods used to present many algorithms in the literature can therefore be taken as guidelines in the design of a language. Knill¹¹ laid out requirements for quantum programming, including:

Allocation and measurement. Make it possible to allocate and measure quantum registers and apply unitary operations;

Reasoning about subroutines. Permit reasoning about quantum subroutines, reversing a subroutine, and conditioning a subroutine over the state of a quantum register; and

Building quantum oracles. Enable the programmer to build a quantum oracle from the description of a classical function.

Our experience implementing^a quantum algorithms suggests some additional features that would be requirements for a quantum programming language:

Quantum data types. In classical languages, data types are used to permit the programmer to think abstractly about data instead of managing individual bits or words. For example, in most situations, a floating-point number is best viewed as a primitive data type supporting certain arithmetic operations, rather than an array of 64 bits comprising an exponent, a mantissa, and a sign. Likewise, many quantum algorithms specify richer data types, so the language should also provide these abstractions. For example, the Quantum Linear System Algorithm⁹ requires manipulation of quantum integers and quantum real and complex numbers that can be represented through a floating-point or fixed-precision encoding. Another example is Hallgren’s algorithm⁸ for computing the class number of a real quadratic number field. One type of data that occurs in this algorithm, and that must be put into quantum superposition, is the type of ideals in an algebraic number field;

Specification and verification. In classical programming, there is a variety of techniques for ascertaining the correctness of programs, including compile-time type checking, runtime type checking, formal verification, and debugging. Among them, formal verification is arguably the most reliable but also the most costly. The availability of strong compile-time guarantees requires very carefully designed programming languages. Debugging is cheap and useful and therefore ubiquitous in classical-program development.

In quantum computation, the cost of debugging is likely to be quite high. To begin with, observing a quantum system can change its state. A debugger for a quantum program would therefore necessarily give incomplete information about its state when run on actual quantum hardware. The alternative is to use a quantum simulator for debugging. But this is not practical due to the exponential cost of simulating quantum systems. Moreover, it can be expected that the initial quantum computers will be rare and expensive to run and therefore that the cost of runtime errors in quantum code will initially be much higher than in classical computing. This shifts the cost-benefit analysis for quantum programming toward strong compile-time correctness guarantees, as well as formal specification and verification.

A quantum programming language should have a sound, well-defined semantics permitting mathematical specifications of program behavior and program correctness proofs. It is also beneficial for the language to have a strong static type system that can guarantee the absence of most runtime errors (such as violations of the no-cloning property of quantum information);^b and

Resource sensitivity and resource estimation. At first, quantum computers will probably not have many qubits. The language should thus include tools to estimate the resources required for running a particular piece of code (such as number of qubits, number of elementary gates, or other relevant resources) prior to deployment. One particular issue for language designers is how to handle quantum error correction. As the field advances, a decision must be made as to whether error correction should be exposed to the programmer (potentially allowing for optimization by hand) or whether it is more efficient to let the compiler or some other tool apply error correction automatically. Due to the potential for undesirable interactions between quantum error correction (which adds redundancy) and the optimization step of a compiler (which removes redundancy), the design and implementation of any quantum programming language must be aware of the requirements of quantum error correction.

Back to Top

Prior Work on QPLs

Several quantum programming languages have been developed by researchers around the world.⁵ Some, including van Tonder’s quantum lambda calculus,¹⁸ are primarily intended as theoretical tools. The first quantum programming language intended for practical use was arguably Ömer’s QCL,¹⁴ a C-style imperative language supporting “structured quantum programming.” QCL provides simple registers but no high-level quantum data types. It could also benefit from greater support for specification and verification. Partly building on Ömer’s work, Bettelli et al.² proposed a language that is an extension of C++. The guarded command language qGCL of Sanders and Zuliani¹⁶ hints at a language for program specification.

The first quantum programming language in the style of functional programming was the quantum lambda calculus of Selinger and Valiron,¹⁷ providing a unified framework for manipulating classical and quantum data. The quantum lambda calculus has a well-defined mathematical semantics that guarantees the absence of runtime errors in a well-typed program. The language is easily extended with inductive data types (such as lists) and recursion. One shortcoming of the quantum lambda calculus, however, is that it does not separate circuit construction from circuit evaluation. It thus lacks the ability to manipulate quantum circuits as data, as well as the ability to automatically construct unitary circuits from a classical description. These problems were partly addressed by the Quantum IO Monad of Green and Altenkirch,⁷ a functional language that is a direct predecessor of Quipper.

Back to Top

The Quipper Language

Building on this previous work, we introduce Quipper, a functional language for quantum computation. We chose to implement Quipper as a deeply embedded domain-specific language (EDSL) inside the host language Haskell; see Gill⁶ for an overview of EDSLs and their embedding in Haskell. Quipper is intended to offer a unified general-purpose programming framework for quantum computation. Its main features are:

Hardware independence. Quipper’s paradigm is to view quantum computation at the level of logical circuits. The addition of error-correcting codes and mapping to hardware are left to other components further down the chain of compilation;

Extended circuit model. The initialization and termination of qubits is explicitly tracked for the purpose of ancilla management;

Hierarchical circuits. Quipper features subroutines at the circuit level, or “boxed subcircuits,” permitting a compact representation of circuits in memory;

Versatile circuit description language. Quipper permits multiple programming styles and can handle both procedural and functional paradigms of computation. It also permits high-level manipulations of circuits with programmable operators;

Two runtimes. A Quipper program typically describes a family of circuits that depends on some classical parameters. The first runtime is “circuit generation,” and the second runtime is “circuit execution.” In batch-mode operation, as discussed earlier, these two runtimes take place one after the other, whereas in online operation, they may be interleaved;

Parameter/input distinction. Quipper has two notions of classical data: “parameters,” which must be known at circuit-generation time, and “inputs,” which may be known only at circuit-execution time. For example, the type Bool is used for Boolean parameters, and the type Bit is used for Boolean inputs;

Extensible data types. Quipper offers an abstract, extensible view of quantum data using Haskell’s powerful type-class mechanism; and

Automatic generation of quantum oracles. Many quantum algorithms require some nontrivial classical computation to be made reversible and then lifted to quantum operation. Quipper has facilities for turning an ordinary Haskell program into a reversible circuit. This feature is implemented using a self-referential Haskell feature known as “Template Haskell” that enables a Haskell program to inspect and manipulate its own source code.

Back to Top

Quipper Feature Highlights

We briefly highlight some of Quipper’s features with code examples:

Procedural paradigm. In Quipper, qubits are held in variables, and gates are applied one at a time. The type of a circuit-producing function is distinguished by the keyword Circ after the arrow, as in Figure 7. The function mycirc inputs a and b of type Qubit and outputs a pair of qubits while generating a circuit;

Block structure. Functions generating circuits can be reused as subroutines to generate larger circuits. Operators (such as with_control) can take an entire block of code as an argument, as in Figure 8. Note “do” introduces an indented block of code, and “$” is an idiosyncrasy of Haskell syntax that can be ignored by the reader here;

Circuit operators. Quipper can treat circuits as data and provide high-level operators for manipulating whole circuits. For example, the operator reverse_simple reverses a circuit, as in Figure 9;

Circuit transformers. Quipper provides user-programmable “circuit transformers” as a mechanism for modifying a circuit on a gate-by-gate basis. For example, the timestep circuit in Figure 9 can be decomposed into binary gates using the Binary transformer, as in Figure 10; and

Automated functional-to-reversible translation. Quipper provides a special keyword build_circuit for automatically synthesizing a circuit from an ordinary functional program, as in Figure 11. The resulting circuit can be made reversible with the operator classical_to_reversible, as in Figure 12.

Back to Top

Experience with Quipper

We have used Quipper to implement seven nontrivial quantum algorithms from the literature, based on documents provided by the Quantum Computer Science program of the U.S. Intelligence Advanced Research Projects Activity (IARPA).¹⁰ All of these algorithms can be run, in the sense that we can print the corresponding circuits for small parameters and perform automated gate counts for circuits of less tractable sizes. Each of these algorithms (see the table here) solves some problem believed to be classically hard, and each algorithm provides an asymptotic quantum speedup, though not necessarily an exponential one. These seven algorithms cover a broad spectrum of quantum techniques; for example, the table includes several algorithms that use the Quantum Fourier Transform, phase estimation, Trotterization, and amplitude amplification. IARPA selected the algorithms for being comparatively complex, which is why some better-known but technically simpler algorithms (such as Shor’s factorization algorithm) were not included.

Using Quipper, we are able to perform semi- or completely automated logical-gate-count estimations for each of the algorithms, even for very large problem sizes. For example, in the case of the triangle-finding algorithm, the command

produces the gate count for the complete algorithm on a graph of 2¹⁵ vertices using an oracle with 31-bit integers and a Hamming graph of tuple size 2⁶. This command runs to completion in less than two minutes on a laptop computer and produces a count of 30,189,977,982,990 gates and 4,676 qubits for this instance of the algorithm.

Examples. As a further illustration, here are two subroutines written in Quipper:

Procedural example. First, we formalize the circuit family in Figure 3. This circuit implements the time step for a quantum walk in the Binary Welded Tree algorithm.⁴ It inputs a list of pairs of qubits (a_i, b_i), and a single qubit r. It first generates an ancilla, or scratch-space, qubit in state |0〉. It then applies the two-qubit gate W to each of the pairs (a_i, b_i), followed by a series of doubly controlled NOT-gates acting on the ancilla. After a middle gate e^iZt, it applies all the gates in reverse order. The ancilla ends up in the state |0〉 and is no longer needed. The Quipper code is in Figure 13, yielding the circuit in Figure 14. If one replaces the “3” with a “30” in the main function, one obtains a larger instance of this circuit family, as in Figure 15; and

A functional-to-reversible translation. This example is from the Quantum Linear Systems algorithm.⁹ Among other things, this algorithm contains an oracle calculating a vector r of complex numbers; Figure 16 shows the core function of the oracle. Note it relies heavily on algebraic and transcendental operations on real and complex numbers (such as sin, cos, sinc, and mkPolar), as well as on subroutines (such as edgetoxy and itoxy) not shown in Figure 16. This function is readily processed using Quipper’s automated circuit-generation facilities. Algebraic and transcendental functions are mapped automatically to quantum versions provided by an existing Quipper library for fixed-point real and complex arithmetic. The result is the rather large circuit in Figure 17.

Back to Top

Conclusion

Practical quantum computation requires a tool chain extending from abstract algorithm descriptions down to the level of physical particles. Quantum programming languages are an important aspect of this tool chain. Ideally, such a language enables a quantum algorithm to be expressed at a high level of abstraction, similar to what may be found in a research paper, and translates it down to a logical circuit. We view this logical circuit as an intermediate representation that can then be further processed by other tools, adding quantum control and error correction, and finally passed to a real-time system controlling physical operations.

Quipper is an example of a language suited to a quantum coprocessor model. We demonstrated Quipper’s feasibility by implementing several large-scale algorithms. The design of Quipper solved some major programming-language challenges associated with quantum computation, but there is still much to do, particularly in the design of type systems for quantum computing. As an embedded language, Quipper is confined to using Haskell’s type system, providing many important safety guarantees. However, due to Haskell’s lack of support for linear types, some safety properties (such as the absence of attempts to clone quantum information) are not adequately supported. The design of ever better type systems for quantum computing is the subject of ongoing research.

Back to Top

Back to Top

Back to Top

Back to Top

Back to Top

Back to top