quantum computing, monads, and FP in general
Bill Halchin
bhalchin@hotmail.com
Sat, 05 Oct 2002 02:34:51 +0000
<html><div style='background-color:'><DIV>
<P><BR><BR></P>
<DIV>
<DIV></DIV>
<P>Hello,</P></DIV>
<P>Byron wrote: "However, the </P></DIV>
<DIV></DIV>
<DIV></DIV>
<P>>computational burden of doing this is massive, supposedly too </P>
<DIV></DIV>
<DIV></DIV>
<DIV></DIV>
<P>>massive for current digital computers." </P>
<DIV></DIV>
<P> The main reason for the parallelism of QC is that we are dealing with tensor spaces. The ACM publised in Computing Surveys a very nice overview of QC:</P>
<DIV></DIV>
<P><A href="http://xxx.lanl.gov/abs/quant-ph/9809016">http://xxx.lanl.gov/abs/quant-ph/9809016</A>.</P>
<DIV></DIV>
<P>This survey explains the role of tensor spaces in the parallel speed up with QCs.</P>
<DIV></DIV>
<P>Regards, Bill Halchin</P>
<DIV></DIV>
<P><BR><BR> </P>
<DIV></DIV>
<DIV></DIV>
<DIV></DIV>
<DIV></DIV>
<DIV></DIV>>From: Byron Hale <BYRON.HALE@EINFO.COM>
<DIV></DIV>
<DIV></DIV>>To: "Bill Halchin" <BHALCHIN@HOTMAIL.COM>
<DIV></DIV>
<DIV></DIV>>Subject: Re: quantum computing, monads, and FP in general
<DIV></DIV>
<DIV></DIV>>Date: Fri, 04 Oct 2002 18:44:12 -0700
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>It's my understanding that quantum theory is rather contradictory,
<DIV></DIV>
<DIV></DIV>>as it stands. It's capable of predictions, but not a very neat
<DIV></DIV>
<DIV></DIV>>package, logically. There are controversies. Quantum computing,
<DIV></DIV>
<DIV></DIV>>itself, is somewhat controversial. However, it appears to be
<DIV></DIV>
<DIV></DIV>>justified experimentally by a recent factorization of "15."
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>BIll Halchin is right that quantum computing is considered
<DIV></DIV>
<DIV></DIV>>reversible. The idea of collapse of a wave function providing
<DIV></DIV>
<DIV></DIV>>information does appear to be contradictory, although some may rush
<DIV></DIV>
<DIV></DIV>>to save any apparent contradictions. As I understand quantum logic,
<DIV></DIV>
<DIV></DIV>>it can be represented by a certain non-distributive lattice and as
<DIV></DIV>
<DIV></DIV>>Bill says, by composition of matrices, so perhaps we don't have to
<DIV></DIV>
<DIV></DIV>>worry so much about the details of quantum theory.
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>As for wave functions, they might be represented as sampled
<DIV></DIV>
<DIV></DIV>>functions, lazily, in infinite "lists." My understanding of quantum
<DIV></DIV>
<DIV></DIV>>computing is that whole distributions are computed, not just a
<DIV></DIV>
<DIV></DIV>>single possible outcome. Then one is only concerned with computing
<DIV></DIV>
<DIV></DIV>>the sampled probability distribution of the outcomes. However, the
<DIV></DIV>
<DIV></DIV>>computational burden of doing this is massive, supposedly too
<DIV></DIV>
<DIV></DIV>>massive for current digital computers.
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>Byron Hale
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>At 01:06 AM 10/5/2002 +0000, you wrote:
<DIV></DIV>
<DIV></DIV>>
<DIV></DIV>
<DIV></DIV>>>Hello,
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>> One very thing to keep in mind about quantum computing is
<DIV></DIV>
<DIV></DIV>>>that all computations are reversible because the evolution over
<DIV></DIV>
<DIV></DIV>>>time of a quantum system is represented by unitary operators (in a
<DIV></DIV>
<DIV></DIV>>>Hilbert space) on elements in the particular HS. In QC, the spaces
<DIV></DIV>
<DIV></DIV>>>are finite dimensional where elements are quibits and the operators
<DIV></DIV>
<DIV></DIV>>>are represented by matrices. "classical" programming is anything
<DIV></DIV>
<DIV></DIV>>>but reversible. My .02 for what it us worth.
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>Regards, Bill Halchin
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>> >From: Hal Daume III
<DIV></DIV>
<DIV></DIV>>> >To: Haskell Mailing List
<DIV></DIV>
<DIV></DIV>>> >CC: Rob Pierry ,Ryan Barrett
<DIV></DIV>
<DIV></DIV>>> >Subject: quantum computing, monads, and FP in general
<DIV></DIV>
<DIV></DIV>>> >Date: Fri, 4 Oct 2002 16:46:44 -0700 (PDT)
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Hi All,
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >I realize most people are currently at PLI and that this might
<DIV></DIV>
<DIV></DIV>>>not be the
<DIV></DIV>
<DIV></DIV>>> >most appropriate place to bring up such questions. Nevertheless,
<DIV></DIV>
<DIV></DIV>>>there
<DIV></DIV>
<DIV></DIV>>> >are smarter and more knowledgable people on this mailing list
<DIV></DIV>
<DIV></DIV>>>than most
<DIV></DIV>
<DIV></DIV>>> >other places I know of, so here it goes.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Does anyone know if anyone has tried to model quantum computing
<DIV></DIV>
<DIV></DIV>>>in a
<DIV></DIV>
<DIV></DIV>>> >monadic sense. What I mean is this:
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Let's say we had a quantum computer. This basically gives us a
<DIV></DIV>
<DIV></DIV>>>bunch of
<DIV></DIV>
<DIV></DIV>>> >complex numbers on which we can perform calculations. Sort of an
<DIV></DIV>
<DIV></DIV>>>extreme
<DIV></DIV>
<DIV></DIV>>> >SIMD situation, though the type of operations we can perform are
<DIV></DIV>
<DIV></DIV>>>only
<DIV></DIV>
<DIV></DIV>>> >unitary matrix multiplications. Let's forget this for now.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >There are two primary characteristics of quantum computations:
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> > 1) once you observe the result, you lose everything else and
<DIV></DIV>
<DIV></DIV>>> > can't say "well, let's go back"
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> > 2) observing the result is probabilistic. that is, each possible
<DIV></DIV>
<DIV></DIV>>> > solution has an associated probability (it's squared amplitude)
<DIV></DIV>
<DIV></DIV>>> > and the probability of getting a solution back is equal to
<DIV></DIV>
<DIV></DIV>>> > this.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >This strikes me as a very monad-like setup. We can have a monad
<DIV></DIV>
<DIV></DIV>>>P, where
<DIV></DIV>
<DIV></DIV>>> >a value of type 'P a' is a distribution over all elements of type
<DIV></DIV>
<DIV></DIV>>>a with
<DIV></DIV>
<DIV></DIV>>> >associated probabilities. That is, 'P Bool' is a probability
<DIV></DIV>
<DIV></DIV>>>space with
<DIV></DIV>
<DIV></DIV>>> >two elements, True and False, each with an associated
<DIV></DIV>
<DIV></DIV>>>probability.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >We need a bind operation. This is essentially associated with the
<DIV></DIV>
<DIV></DIV>>>sorts
<DIV></DIV>
<DIV></DIV>>> >of unitary matrix multiplications we can perform. So, we can
<DIV></DIV>
<DIV></DIV>>>write
<DIV></DIV>
<DIV></DIV>>> >something like 'a `bind` f' where a is a distribution over as and
<DIV></DIV>
<DIV></DIV>>>f is a
<DIV></DIV>
<DIV></DIV>>> >function which takes some a to a distribution over bs. Then, the
<DIV></DIV>
<DIV></DIV>>> >probability associated in the new distribution with a value x of
<DIV></DIV>
<DIV></DIV>>>type b is
<DIV></DIV>
<DIV></DIV>>> >simply the sum over all possible way of getting to it.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >So, for instance, suppose we had a flat distribution of type P
<DIV></DIV>
<DIV></DIV>>>Bool; call
<DIV></DIV>
<DIV></DIV>>> >it 'flat'. We then had a function of type 'Bool -> P Bool' which
<DIV></DIV>
<DIV></DIV>>>took a
<DIV></DIV>
<DIV></DIV>>> >boolean and with 50% probability returned it as is and with 50%
<DIV></DIV>
<DIV></DIV>>> >probability flipped its value. Call this function 'maybeFlip'.
<DIV></DIV>
<DIV></DIV>>>Now,
<DIV></DIV>
<DIV></DIV>>> >'flat `bind` maybeFlip' produces a new probability distribution
<DIV></DIV>
<DIV></DIV>>>equal to
<DIV></DIV>
<DIV></DIV>>> >'flat' (basically because there's a 50% probability of flat
<DIV></DIV>
<DIV></DIV>>>spitting out
<DIV></DIV>
<DIV></DIV>>> >True, which gets to be True with 50% probability and False with
<DIV></DIV>
<DIV></DIV>>>50%
<DIV></DIV>
<DIV></DIV>>> >probability; similar reasoning if flat spits out False gives an
<DIV></DIV>
<DIV></DIV>>>overall
<DIV></DIV>
<DIV></DIV>>> >probability for True of 50% and False of 50%).
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >When we deal with actual complex numbers and can have negatives,
<DIV></DIV>
<DIV></DIV>>>things
<DIV></DIV>
<DIV></DIV>>> >become more interesting, but the reasoning remains essentially
<DIV></DIV>
<DIV></DIV>>>the same.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >The 'return' funciton would simply return its argument with
<DIV></DIV>
<DIV></DIV>>>probability 1
<DIV></DIV>
<DIV></DIV>>> >and everything else with probability 0 (read probability =
<DIV></DIV>
<DIV></DIV>>>amplitude).
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Though I haven't formally verified it, I'm almost positive this
<DIV></DIV>
<DIV></DIV>>>obeys the
<DIV></DIV>
<DIV></DIV>>> >monad laws (the only non-trivial verification is on the
<DIV></DIV>
<DIV></DIV>>>distributivity
<DIV></DIV>
<DIV></DIV>>> >law, but I think it will work out).
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >The only work I've seen regarding programming quantum computers
<DIV></DIV>
<DIV></DIV>>>is the
<DIV></DIV>
<DIV></DIV>>> >'Quantum Programming' paper from Sanders and Zuliani at MPC (I
<DIV></DIV>
<DIV></DIV>>>think) and
<DIV></DIV>
<DIV></DIV>>> >they took an imperate approach, essentially augmenting Dijkstra's
<DIV></DIV>
<DIV></DIV>>>GCL
<DIV></DIV>
<DIV></DIV>>> >programming language to pGCL by giving it probabilism. Perhaps
<DIV></DIV>
<DIV></DIV>>>it's just
<DIV></DIV>
<DIV></DIV>>> >my personal bias, but functional programming seems to be a more
<DIV></DIV>
<DIV></DIV>>>natural
<DIV></DIV>
<DIV></DIV>>> >fit. I also like the thin connection between lazy evaluation and
<DIV></DIV>
<DIV></DIV>>>the
<DIV></DIV>
<DIV></DIV>>> >important role observation has in quantum computing.
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Obviously I don't know much about monads and I know even less
<DIV></DIV>
<DIV></DIV>>>about
<DIV></DIV>
<DIV></DIV>>> >quantum computing. Does anyone know if anyone has taken the
<DIV></DIV>
<DIV></DIV>>>approach
<DIV></DIV>
<DIV></DIV>>> >outlined above or anything similar or can point out that I'm just
<DIV></DIV>
<DIV></DIV>>>way off
<DIV></DIV>
<DIV></DIV>>> >track....
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >Thanks!
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> > - Hal
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >--
<DIV></DIV>
<DIV></DIV>>> >Hal Daume III
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> > "Computer science is no more about computers | hdaume@isi.edu
<DIV></DIV>
<DIV></DIV>>> > than astronomy is about telescopes." -Dijkstra |
<DIV></DIV>
<DIV></DIV>>>www.isi.edu/~hdaume
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >
<DIV></DIV>
<DIV></DIV>>> >_______________________________________________
<DIV></DIV>
<DIV></DIV>>> >Haskell mailing list
<DIV></DIV>
<DIV></DIV>>> >Haskell@haskell.org
<DIV></DIV>
<DIV></DIV>>> >http://www.haskell.org/mailman/listinfo/haskell
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>
<DIV></DIV>
<DIV></DIV>>>----------
<DIV></DIV>
<DIV></DIV>>>Chat with friends online, try MSN Messenger: Click Here
<DIV></DIV>
<DIV></DIV>>>_______________________________________________ Haskell mailing
<DIV></DIV>
<DIV></DIV>>>list Haskell@haskell.org
<DIV></DIV>
<DIV></DIV>>>http://www.haskell.org/mailman/listinfo/haskell
<DIV></DIV>
<DIV></DIV>
<DIV></DIV></div><br clear=all><hr>MSN Photos is the easiest way to share and print your photos: <a href='http://g.msn.com/1HM1ENUS/c156??PI=44364'>Click Here</a><br></html>