quantum computing, monads, and FP in general

[Hal Daume III]

Hi All,

I realize most people are currently at PLI and that this might not be the
most appropriate place to bring up such questions.  Nevertheless, there
are smarter and more knowledgable people on this mailing list than most
other places I know of, so here it goes.

Does anyone know if anyone has tried to model quantum computing in a
monadic sense.  What I mean is this:

Let's say we had a quantum computer.  This basically gives us a bunch of
complex numbers on which we can perform calculations.  Sort of an extreme
SIMD situation, though the type of operations we can perform are only
unitary matrix multiplications.  Let's forget this for now.

There are two primary characteristics of quantum computations:

 1) once you observe the result, you lose everything else and
    can't say "well, let's go back"

 2) observing the result is probabilistic.  that is, each possible
    solution has an associated probability (it's squared amplitude)
    and the probability of getting a solution back is equal to
    this.

This strikes me as a very monad-like setup.  We can have a monad P, where
a value of type 'P a' is a distribution over all elements of type a with
associated probabilities.  That is, 'P Bool' is a probability space with
two elements, True and False, each with an associated probability.

We need a bind operation.  This is essentially associated with the sorts
of unitary matrix multiplications we can perform.  So, we can write
something like 'a `bind` f' where a is a distribution over as and f is a
function which takes some a to a distribution over bs.  Then, the
probability associated in the new distribution with a value x of type b is
simply the sum over all possible way of getting to it.

So, for instance, suppose we had a flat distribution of type P Bool; call
it 'flat'.  We then had a function of type 'Bool -> P Bool' which took a
boolean and with 50% probability returned it as is and with 50%
probability flipped its value.  Call this function 'maybeFlip'.  Now,
'flat `bind` maybeFlip' produces a new probability distribution equal to
'flat' (basically because there's a 50% probability of flat spitting out
True, which gets to be True with 50% probability and False with 50%
probability; similar reasoning if flat spits out False gives an overall
probability for True of 50% and False of 50%).

When we deal with actual complex numbers and can have negatives, things
become more interesting, but the reasoning remains essentially the same.

The 'return' funciton would simply return its argument with probability 1
and everything else with probability 0 (read probability = amplitude).

Though I haven't formally verified it, I'm almost positive this obeys the
monad laws (the only non-trivial verification is on the distributivity
law, but I think it will work out).

The only work I've seen regarding programming quantum computers is the
'Quantum Programming' paper from Sanders and Zuliani at MPC (I think) and
they took an imperate approach, essentially augmenting Dijkstra's GCL
programming language to pGCL by giving it probabilism.  Perhaps it's just
my personal bias, but functional programming seems to be a more natural
fit.  I also like the thin connection between lazy evaluation and the
important role observation has in quantum computing.

Obviously I don't know much about monads and I know even less about
quantum computing.  Does anyone know if anyone has taken the approach
outlined above or anything similar or can point out that I'm just way off
track....

Thanks!

 - Hal


--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume