Quantum Programming

Submitted by Greg Buchholz on Fri, 12/02/2005 - 4:48pm.

Lately I've been pondering the programming of quantum computers. Just because we don't have the hardware yet seems like an awfully bad excuse for not having languages and emulators/simulators. I really don't know much about quantum computing (book recommendations anyone?), but it seems to be based on a somewhat nondeterministic model. Is it going to be like programming in Prolog, but with backtracking that doesn't cost anything in terms of efficiency? Curious.

Quantum computers won't support quantum control any time soon, only quantum data. So in the early days, it's probably not going to be much different from what we have now, except that there will be a new "quantum word" data type, which is like a standard machine word, except the bits are quantum. Quantum word types will support a few operations that you might not be used to seeing.
One of them is a half exclusive or operation, which is pretty weird.
It works something like this:

```LOAD \$0, r0     ; Load a literal 0 into R0
HXOR \$1, r0     ; Half exclusive-or.
HXOR \$1, r0     ; Half exclusive-or.  At this point,
; a full exclusive or operation has now been
; performed, and r0 = 1.
HXOR \$1, r0
HXOR \$1, r0     ; Again, another exclusive or operation has
; been performed in two halves.  Now r0 = 0.
```

I deliberately didn't say what happened to r0 between the each pair of HXOR instructions, because it's very hard to describe. But basically, the least significan qbit in r0 has been half-negated. Applying it twice gives a full negation.
You can kind of think of the bit as being a complex number, with 1 being binary 1 and -1 being binary 0. A half-negation is like multiplying it by i.

Quantum data but no quantum control still gives us an "amb" of sorts though, right? Stuff like below should be possible with 28 qubits (7 for each of "a" and "b" and 14 for the result) and some "classical" hardware (and the necessary mental compilation into a suitable quantum lanugage)...

```import Control.Monad
main = print ( do a <- [2..127]
b <- [2..127]
if a*b == 8633 then return (a,b) else mzero )
```

Or is that example completely off-base? I guess I'll be reading up on Shor's algorithm

Very comprehensive lectures on the topic by David Deutsch: http://www.quiprocone.org/Protected/DD_lectures.htm

Unfortunately not all lectures are online yet...