What would a very simple quantum program look like?

Question

In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first programs I ever wrote was something like

for i = 1 to 10
  print i
next i

Can anybody give an example of code of comparable simplicity that would utilize quantum photonic chips (or similar hardware), in pseudocode or high level language? I am having difficulty making the conceptual jump from traditional programming to entanglement, etc.

Answer 1

Caveat Emptor: the following is heavily biased on my own research and view on the field of QC. This does not constitute the general consensus of the field and might even contain some self-promotion.

The problem of showing a 'hello world' of quantum computing is that we're basically still as far from quantum computers as Leibnitz or Babbage were from your current computer. While we know how they should operate theoretically, there is no standard way of actually building a physical quantum computer. A side-effect of that is that there is no single programming model of quantum computing. Textbooks such as Nielsen et al. will show you a 'quantum circuit' diagram, but those are far from formal programming languages: they get a little 'hand-waving' on the details such as classical control or dealing with input/output/measurement results.

What has suited me best in my research as a programming language computer scientist, and to get the jist of QC across to other computer scientist, is to use the simplest QC model I've come across that does everything.

The simplest quantum computing program I have seen that contains all essential elements is a small three-instruction program in the simplest quantum programming model I've come across. I use it as you would a 'hello world' to get the basics across.

Allow me to give quick simplified summary of the The Measurement Calculus by Danos et al.1 that is based on is based on the one-way quantum computer2: a qubit is destroyed when measured, but measuring it affects all other qubits that were entangled with it. It has some theoretical and practical benefits over the 'circuit-based' quantum computers as realized by the photonic chip, but that is a different discussion.

Consider a quantum computer that has only five instructions: N, E, M, X and Z. Its "assembly language" is similar to your regular computer, after executing one instruction it goes to the next instruction in the sequence. Each instruction takes a target qubit identifier, we use just a number here, and other arguments.

N 2          # create a new quantum bit and identify it as '2'
E 1 2        # entangle qubits '1' and '2', qubit 1 already exists and is considered input
M 1 0        # measure qubit '1' with an angle of zero  (angle can be anything in [0,2pi]
             # qubit '1' is destroyed and the result is either True or False
             # operations beyond this point can be dependent on the signal of '1'
X 2 1        # if the signal of qubit '1' is True, execute the Pauli-X operation on qubit '2'

The above program thus creates an ancilla, entangles it with the input qubit, measures the input and depending on the measurement outcome performs an operation on the ancilla. The result is that qubit 2 now contains the state of qubit 1 after Hadamard operation.

The above is naturally at such low level that you wouldn't want to hand-code it. The benefit of the measurement calculus is that it introduces 'patterns', some sort of composable macros that allow you to compose larger algorithms as you would with subroutines. You start off with 1-instruction patterns and grow larger patterns from there.

Instead of an assembler-like instruction sequence, it is also common to write the program down as a graph:

 input                .........
    \--> ( E ) ---> (M:0)     v
(N) ---> (   ) ------------> (X) ---> output

where full arrows are qubit dependencies and the dotted arrow is a 'signal' dependency.

The following is the same Hadamard example expressed in a little programming tool as I would imagine a 'quantum programmer' would use.

edit: (adding relation with 'classical' computers) Classical computers are still really efficient in what they do best, and so the vision is that quantum computers will be used to off-load certain algorithms, analogous to how current computer offloads graphics to a GPU. As you have seen above, the CPU would control the quantum computer by sending it an instruction stream and read back the measurement results from the boolean 'signals'. This way you have a strict separation of classical control by the CPU and quantum state and effects on the quantum computer.

For example, I'm going to use my quantum co-processor to calculate a random boolean or cointoss. Classical computers are deterministic, so its bad at returning a good random number. Quantum computers are inherently probabilistic though, all I have to do to get a random 0 or 1 is to measure out a equally-balanced qubit. The communication between the CPU and 'QPU' would look something like this:

 qrand()       N 1; M 1 0;
 ==>  | CPU | ------------> | QPU |  ==> { q1 } ,  []
                 start()
      |     | ------------> |     |  ==> { } , [q1: 0]
                 read(q1)         
      |     | ------------> |     |
                  q1: 0 
 0    |     | <-----------  |     |
 <==

Where { ... } is the QPU's quantum memory containing qubits and [...] is its classical (signal) memory containing booleans.

---

1. Danos et al. The Measurement Calculus. arXiv (2007) vol. quant-ph
2. Raussendorf and Briegel. A one-way quantum computer. Physical Review Letters (2001) vol. 86 (22) pp. 5188-5191

Answer 2

I assume that C's libquantum, Haskell's quantum monads or Perl's Quantum::Entanglement all represent quantum computations faithfully. You might look at their examples.

In general, you describe a quantum algorithm as a classical algorithm that applies a series of linear operators to a super-position representing the state of your quantum system. Journal articles often depict a circuit with lines for quantum bits/registers and boxes for linear operators.

Of course, the hard part isn't describing the algorithm but understanding why it works, just like probabilistic algorithms. I've always considered Grover's algorithm quite comprehensible. You could also read about the Quantum Fourier transform used by Shor's Algorithm.

Answer 3

It looks like this:

You too can have access to a real quantum processor. Go here and sign up: http://www.research.ibm.com/quantum/

It also includes a simulator so you can test without using actual hardware, or use credits (free) to run on actual hardware.

Answer 4

Checkout implementation of Deutsch algorithm in LanQ.

Answer 5

I think the answer is "A lot like a simple classical program."

If we consider the simply-typed lambda calculus (with products) to be the heart of classical programming, then we can exploit that it is the internal type theory of a closed cartesian category, which gives us a pointer.

Namely, in physics, algebraic structures related to quantum physics are often modeled in category theory with symmetric monoidal categories. (See Hilb, $n$Cob, Tang$_k$.) And symmetric monoidal categories are just a step before cartesian categories (you just need to add duplication and deletion).

So, if the STLC is to cartesian closed categories, what is to closed symmetric monoidal categories? Well, we know that the internal logic of a symmetric monoidal category is MILL. So what we need is a type theory corresponding to MILL -- a linear type theory.

Stepping away from the abstract nonsense, what do we get with a linear type theory? Linearity. We get linearity of resources. And this is exactly what we want. You aren't allowed to clone quantum bits. You aren't allowed to implicitly measure. And linearity means you can't do either of these during reduction.

There has been some work on linear type theories, but not a ton. I got some of the ideas in this post from this paper: Physics, Topology, Logic and Computation: A Rosetta Stone by Mike Stay and John Baez, which goes much more into detail than my handwaving.

Answer 6

Quantum computing programs can actually be written in any general-purpose programming language. You can think of them as programs that have access to a special set of instructions / components powered by the quantum hardware underneath.

Other answers here are more focused in traditional quantum circuit diagrams, which can be easily converted into structured code (and back), for instance:

public class DeutschAlgorithm
{
    public bool IsBalanced(BinaryOperation gate)
    {
        var q1 = new Qubit(false);
        var q2 = new Qubit(true);

        new HGate().Apply(q1);
        new HGate().Apply(q2);

        gate.Apply(q2, q1);

        new HGate().Apply(q1);

        return q1.Measure();
    }
}

This class implements the famous Deutsch Algorithm wrapped in a conventional object oriented programming language dressing. Notice the Qubit, HGate and BinaryOperation classes, as they are the actual quantum components embedded in the code, unlocking the potential of quantum operations.

This sample code is taken from a quantum computing simulator project I implemented for learning purposes, which you can run in your own (classical) computer for producing the outputs of quantum algorithms, but of course without any of the performance improvements provided by actual quantum computers.

Answer 7

I'd probably go with a simple "divide by small n" counter implementation to start with.

For example: given a 10GHz source, generate a 5GHz output (but these numbers are arbitrary and only meant to illustrate the concept).

This lets us ignore issues like storage and Von Neumann architecture, and lets us focus on whether the components are actually doing anything understandable.

The next goal, then, would be to build up a small repertoire of "small n" (but I would also listen for pushback from my researchers - if they felt other small goals would be more immediately fruitful, I'd certainly want to understand what they were telling me.)

Long term goals would include mechanisms for pumping information into and out of the system, and holding onto that information long enough to use it.

(It's probably worth remembering that early computer programs were all "hardwired". It was only after extensive experience with those systems that we were able to implement stored programs.)

Answer 8

I think the programming a quantum computer it should be seen from a different point of view that the normal object-oriented programming.

QC has the same ability of the brain to think and decide. The ability to think means has the power of data-mining a source of data which would be the possible choice, and decide which to pick from the all possible states.

A software at this point would need to be architectured in a way that the qubits represented source of data that can be data-mined and entangled with other groups of data.

QC should have a data-miner that process data reading, linking different option together differents group of datasource which rapresent informations, reading all possible states and choose which one to go on.

Thats how our brain works. The QC is able to understand and act accordingly to the Quantum Mechanic law, that means you give a problem and QC show you all possible solutions to solve it.

that's how powerful could be QC, do you agree?

https://www.cs.rutgers.edu/~mlittman/papers/openhouse11.pdf this is the point to start, then create a dataminer to build the quantum device with gates etc, a reader connected to the dataminer, to read and provide feedback. quantum Datasource component host data and the scope of knowledge where the dataminer act.