What would a very simple quantum program look like? 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.
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                .........
    \--&gt; ( E ) ---&gt; (M:0)     v
(N) ---&gt; (   ) ------------&gt; (X) ---&gt; 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;
 ==&gt;  | CPU | ------------&gt; | QPU |  ==&gt; { q1 } ,  []
                 start()
      |     | ------------&gt; |     |  ==&gt; { } , [q1: 0]
                 read(q1)         
      |     | ------------&gt; |     |
                  q1: 0 
 0    |     | &lt;-----------  |     |
 &lt;==


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




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