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