Quantum computing is poised to be one of the next waves of disruptive technology that will transform communication, industry and commerce in the way that the Internet has done the same. The field has, as yet, very few players albeit large ones: Both Google and Microsoft are actively seeking to build quantum computers. D-Waveof British Columbia, Canada claims to have built a quantum computer and open-sourced part of its tooling.

Recently, teleportation, the subject of countless Star Trek movies, became reality for electrons in an experiment conducted in Calgary, Canada. What will quantum computers be able to achieve? While subject of debate, we can extrapolate based on the vaunted characteristics of quantum mechanics. NASA operates a Quantum Artificial Intelligence Laboratory which will operate the D-Wave quantum processor.

Support structure for installation of the D-Wave Vesuvius processor, which is cooled to 20 millikelvin (near absolute zero).

Artificial intelligence, cryptanalysis & cryptography, teleportation and advanced radar systems are but some of the potential applications of quantum computing.

QBits

At the core of quantum computer is the QBit or Quantum Bit. It is the analog to classical bits making up conventional computer memory and which are traditionally either 0 or 1. Quantum bits, by contrast, are said to exist in “superposition,” which is to say they may simultaneously exists in both states.

As such a QBit is described in terms of the probabilities of a QBit being either 0 or 1.

$|\psi \rangle =\alpha |0\rangle +\beta |1\rangle ,\,$

Alpha is the probability that the QBit is zero. Beta is the probability that the QBit is 1. Alpha and beta are termed the QBit’s probability amplitudes. Varying probability amplitudes, and this is critical, imply that an infinite amount of information can be encoded in a QBit, a major departure from classical computation.

Superposition

There is but one fly in the ointment – or rather a cat, and the cat was the imaginary pet of Erwin Rudolf Josef Alexander Schrödinger. Schrödinger postulated in a famous thought experimenttied to quantum mechanics that a cat may be simultaneously alive and not alive – in “superposition” — until observed at which point the fate of the cat becomes decided simply through observation.

While the intuition behind this thought experiment is challenging to the human mind, the mechanics can be proven in the so called double slit experiment by the British scientist Thomas Young. Intriguingly, you can repeat this experiment at home.

Here is the implication for building a general purpose quantum computer the way we think of computers now. Computers are programmed using programming languages. Most, like Java or C++ herald from the Algol family of programming languages based on the Van Neumann architectureof modern computers. The concept is simple: a set of instructions is executed by one or more processors and values are read from and written to a memory unit using one or more input/output devices. Here is a very simple, imperative, programming language construct:

x = x + 1

The above statement takes the value of the variable x, adds 1 to it and assigned the result to the same variable x. Let us imagine, for a moment, what would happen if x was represented not by classical bits but by quantum bits. The first step in decomposing the statement was “take the value of x.” In quantum terms, this means “observing the value of x.” The problem with doing this is that it immediately collapses superposition. Therefore this construct and any other like it is infeasible in quantum computing. Imperative programming at large is incompatible with quantum computing. Lambda calculus, by contrast is imminently compatible with quantum computing. Peter Selinger and Benoˆıt Valiron have proposed a Quantum Lambda Calculus.

How to Program a Quantum Computer

So how is a Quantum computer programmed? Understandingly D-Wave are tight-lipped about the internals of their system but we can make inferences based on job ads. D-Wave, being tight-lipped, have removed the ad, but the Wayback Machinesnapshotted it. The ad states:

“The successful candidate will be responsible for architecting, designing, programming, testing and maintaining the entire suite of software necessary to support the testing and operation of D-Wave’s quantum computing hardware. The software is predominantly Common Lisp-based and is an integral part of the quantum computing system.”

What is suggested here is that despite D-Wave’s open source offering being C and their API being Python, that the internals of the D-Wave quantum computer itself are written in Common Lisp.

While the benefits of scalability of quantum computing can only be realised on quantum hardware, the elementary operations of quantum computing and their probabilistic models can very well be simulated in classical computers. This means that given an implementation of the Lambda Calculus it is possible to program a theoretical quantum computer — if all we want is to understand the concepts and familiarise ourselves with the domain.

Actually writing a Quantum Program…

Let’s get cracking… We will use QGAME, the Quantum Gate and Measurement Emulator. QGAME was sponsored by the National Science Foundation (NSF), the Defense Advanced Research Projects Agency (DARPA) and the United States Air Force Research Laboratory. An unofficial port of QGAME is available on Github at https://github.com/thephoeron/qgame. We will be using Steel Bank Common Lisp and the Superior Lisp Interaction Mode for Emacs(SLIME).

Loading QGame…

This was surprisingly easy. We have a functioning Quantum Computing programming environment.

Our first program…

Without further ado, here is our first quantum program: Grover’s Algorithm as applied to a 3 QBit quantum system to facilitate a database search through an unordered database. We will elaborate why this is interesting later.

We are starting see some of the core abstractions that make up a quantum program: gates, transforms (functions) and QBits. These make up a graph. The graph for the above quantum program is shown below:

But why is Grover’s algorithm interesting? What does it solve? Imagine you have a database with items and you want to find a particular one – a search. Computer scientists go to extreme lengths to elaborate algorithms that make this easy. First of all, most databases make sure that their content is sorted in some way. A multitude of sorting algorithms exist to make data easily accessible – searchable. But what if the data was unsorted? What then? We would sort it, hopefully relevant to the manner in which we want to retrieve it. In a typical database an employee table might be indexed alphabetically by “name,” or we might wish to index by something like “department,” whatever our dominant use cases for lookup might be.

Now let us imagine a situation whereby we can look at all entries in the database simultaneously and apply a sort of cost function to something called an oracle that “shakes out” the answer “all in one?” We would likely no longer bother building those database indices or ask ourselves the up-front question of how we want to retrieve that data later. If you are a computer programmer, you likely know of that pesky “O notation” which reflects algorithmic complexity. Indeed this is far deeper than mere database lookups. It goes to the heart of a class of problems in combinatorics that is collectively referred to as NP-Complete. Grover’s algorithm is a design pattern of sorts which solves NP-Complete problems.See Solving NP-complete problems with quantum search, Martin Fürer. If you have, as have I, spent much of your life looking for optimal solutions to hard problems using algorithms, you will appreciate how very profound essentially being able to try all answers at once would prove to be. Grover’s algorithm is a quantum design pattern to achieve just that. How might that be possible, trying all answers “all at once“, you ask? Remember those infinite states of the QBit?

With full appreciation of the gravity of the situation, let us return to our example.

A simple problem…

We define our database to be simply an unsortedlist of zeroes and ones. The problem: find the 1. In classic computing, the average number of lookups will be, on average, 1/2 * N. Our task will be to find the 1 “all in one” using Grover’s algorithm.

We write thusly:

This is our quantum system: the quantum program, 3 bits & our input. It’s state after execution is probabilistic rather than discrete as would be the case in classical computing.

Alpha and Beta Amplitudes…

…encode the state of our system. We query qbits 1 and 2 to “shake out” the solution.

Note the exponent in 3 out of the 4 probabilities. We round as follows:

Note how the amplitudes of our 2 QBits’ probabilities give the position of the digit 1 in the database that we sought. This may not appear like an overwhelming outcome in that our input is the same as our output. Yet we have reduced a data structure ( here a list ) to its bit representation where the value of those bits represents the solution to our problem. It is easy to imagine a 16 QBit solution that encodes 2^32 possible database positions in a single 32 bit integer.

That corresponds to over 4 billion possible database entries. We used the exponent 32 here because each QBit has two amplitudes available for encoding. How many QBits do current quantum computers support?

D-Wave recently announced a 2000 qbit quantum system.

This suggests significantly more complex algorithms are possible.

On the Counter-Intuition of Quantum Algorithms

The very first elements of our graph and the first gates we applied to our QBits were so called “Hadamard gates.” A Hadamard gate forms a “uniformly random” QBit which is to say, when measured it behaves like a fair coin toss. This is what we want when we try all possibilities in parallel. Think of it as spinning-up two wobbly coins on a table. At any point in time they have a probability of “leaning” towards head or tail. We then apply an Oracle with a truth table when we “execute” the quantum program – like bumping the table to settle the coins. In essence we test for the input using an algorithm that is required to yield an output, the output being “the truth.” Our algorithm biases the probabilistic model in which the coins will settle. This is a counter-intuitive property of quantum algorithms: We postulate an output and measure (destructively observe) the input that will generate that output. Output is the problem. Input is the answer. This is also called the “back action” of unitary gates.

In imperative computer programming, we have destructive operations (side-effecting) that yield an observable output for a given input. In quantum computing, the prevailing idiom is a hypothesis (output) which is resolved to an input by a destructive observation.

Manufacturing Constraint Optimisation

In our title we alluded to links to manufacturing processes. This technology has particular application to supply chain optimisation. Optimising supply chains involves several classical non-polynomial time algorithmic problems, such as the Travelling Salesman Problemor Fleet Route Optimisation. In general this class of problem revolves around finding an optimum under given constraints where combinatorics yields non-polynomial time execution. This is precisely the class of problem that is solved by quantum computing. Moreover, we may regard a complex system of concurrent actors as a set of continuous time series to optimise in real time. Because problems like the Travelling Salesman Problem or Fleet Route Optimisation are computationally intensive, the overall system will have moved on from any snapshot used as input to calculations. A quantum computer holds out the promise of virtually continuous and massively parallel optimization.

The nation that manages to integrate this technology first into its supply chain can expect a significant economic multiplier.

Where to now…?

If you’ve followed along, you have just written your first program for a not so theoretical quantum computer – in about 25 lines of code. The absolute minimum to express the semantics without syntax getting in the way. Another interesting application of quantum programming is prime number factorisation – the heart of the public key infrastructure that secures the internet. It is secure because integer factoring cannot be done in polynomial time. Shor’s algorithm solves this.