Hello,

     One very thing to keep in mind about quantum computing is that all computations are reversible because the evolution over time of a quantum system is represented by unitary operators (in a Hilbert space) on elements in the particular HS. In QC, the spaces are finite dimensional where elements are quibits and the operators are represented by matrices. "classical" programming is anything but reversible. My .02 for what it us worth.

Regards, Bill Halchin



 

>From: Hal Daume III
>To: Haskell Mailing List
>CC: Rob Pierry ,Ryan Barrett
>Subject: quantum computing, monads, and FP in general
>Date: Fri, 4 Oct 2002 16:46:44 -0700 (PDT)
>
>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
>
>
>_______________________________________________
>Haskell mailing list
>Haskell@haskell.org
>http://www.haskell.org/mailman/listinfo/haskell

Chat with friends online, try MSN Messenger: Click Here