Read this first: The Quantum Software Challenge.
This is the fourth of a series of posts on the software stack for quantum computing. This post describes the software layers. We focus on the problems that software engineers need to solve to implement a quantum compiler, programming language, functions, libraries and applications.
Looking for the firmware layers? You can read about them here.
Layer 3: Compiler & Quantum programming language
Now we’re getting to higher level software that is completely abstracted from the particular hardware implementation. Here we must make quantum programming debuggable, efficient, and intuitive.
Recently, several of the talented authors of the quantum programming language Quipper wrote an excellent article in the ACM, entitled Programming the Quantum Future. I would encourage you to read its overview of the challenges with quantum programming languages.
Here are a few main points:
Simple things need to be rethought: we cannot simply put a checkpoint in the middle of a quantum computation. A checkpoint would have to act as a measurement of the quantum state at that point. Such measurements would unavoidably affect the result of the computation as measurement collapses the quantum state. Printing out a quantum state with sometimes exponentially many relevant amplitudes would be intractable anyway. We need novel methods (e.g. choosing the right strong types) to make quantum programming as safe as possible.
Optimizations matter. There’s a great slide (34:38) from a talk by Dave Wecker regarding this for a particular quantum simulation problem. Assuming a 10 nanosecond gate time on their quantum computer, the researchers were able to reduce the time needed to solve their problem from 24 billion years to 1 hour. These optimizations were achieved using symbolic manipulations of the quantum circuits themselves. A simple example of such a rewrite for the X and controlled not (CNOT) gates is:
Can we design a programming language to make quantum computing intuitive and accessible for as many programmers as possible?
With these high level concepts in mind, there are several features of quantum computing that this level must address:
- We will need to mix classical and quantum data types, figuring out how to optimally mix classical and quantum operations.
- Quantum data cannot always be exactly copied.
- All operations on quantum data need to be reversible (unitary).
- Because quantum circuits are often too large to directly store in hardware memory for execution, we need to choose appropriate generators so that code can be unrolled at lower hardware layers.
- Appropriate compiler “hints” that will help us optimize fault-tolerance to make optimal use of available quantum processor resources.
- We want to compile down to some “universal gate set.” This acts as a basis set for computation so that the hardware and fault-tolerant levels can focus on implementing a particular set of universal gates.
- We need to reason about subroutines where, for example, classical routines may be conditioned on quantum ones.
You can download, install, and program with Quipper on your computer. Go ahead and check it out.
Dave Wecker and Krysta M. Svore, LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing, February 2014.
Green et al. An Introduction to Quantum Programming in Quipper. 2013. ArXiv:1304.5485
Green et al. Quipper: A Scalable Quantum Programming Language. 2013. ArXiv:1304.3390
Parent et al. Reversible Circuit Compilation with space constraints. 2015. ArXiv:1510.00377
Layer 4: Functions and algorithms
This layer implements efficient quantum functions and algorithms and exposes them for use, either through an API or as part of larger applications. As in the example given above, proper implementation can make a huge difference.
The zoo has many categories of algorithms that are ripe for implementation, but here are a few examples of near-term algorithms from the toolbox that have broad applications in many contexts:
Many of these algorithms have interacting classical and quantum parts, such as loading data to be trained in Boltzmann machine learning. The classical-quantum interaction must be managed to prevent bottlenecks.
In general, the implementations of these algorithms must use all the features provided by a quantum programming languages (like interacting quantum and classical data types) to, basically, write good software.
Hastings et al. Improving Quantum Algorithms for Quantum Chemistry. 2014. ArXiv:1403.1539
Wecker et al. Towards Practical Quantum Variational Algorithms. 2015. ArXiv:1507.08969v1.pdf
Harrow, Hassidim, Lloyd. Quantum Algorithm for solving linear systems of equations. 2008. ArXiv:0811.3171
Grover. A fast quantum mechanical algorithm for database search. ArXiv:9605043
Wiebe et al. Quantum Deep Learning. ArXiv:1412.3489
McClean et al. The theory of variational hybrid quantum-classical algorithms. ArXiv:1509.04279
Layer 5: Libraries and applications
To enable the many different use cases for quantum computing we’ll need the right libraries and the right front-ends to integrate quantum hardware into existing computing systems and workflows. This is the interface between the quantum machine and classical machines, and the quantum machine and users.
It’s worth remembering that the challenge here is also a UX one, where your likely users are other engineers familiar with high performance computing. All of the structural challenges that have been investigated with integrating, for example, GPUs into machine learning have their analogs in QPUs.
The readings here indicate some of the most interesting applications for the first generations of noisy quantum chips. These are mostly quantum simulation algorithms based on variational methods:
There is a lot for software engineers to do to integrate these algorithms into real libraries and applications, and we’re excited to show off what we’re working on.
Where to go from here.
All of this is just scratching the surface. These problems are real. They are here today, and of the relatively few people who have been trying to solve them, fewer still are software engineers.
We need more software engineers looking at these challenges. Difficulties are just things to overcome, after all.
Building this stack is a chance to impact an entire technology (and entire new industry) at the embryonic stage. There do not yet exist large quantum code bases.
Right now, we have a chance to learn as much as possible from the history of classical software development and to devise architectures that will be used for decades, like C. They will need to be elegant and creative solutions and will need to leverage the very best of applied and theoretical computer science.