Byron wrote: "However, the
>computational burden of doing this is massive, supposedly too
>massive for current digital computers."
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:
http://xxx.lanl.gov/abs/quant-ph/9809016.
This survey explains the role of tensor spaces in the parallel speed up with QCs.
Regards, Bill Halchin
>From: Byron Hale <[EMAIL PROTECTED]>
>To: "Bill Halchin" <[EMAIL PROTECTED]>
>Subject: Re: quantum computing, monads, and FP in general
>Date: Fri, 04 Oct 2002 18:44:12 -0700
>
>It's my understanding that quantum theory is rather contradictory,
>as it stands. It's capable of predictions, but not a very neat
>package, logically. There are controversies. Quantum computing,
>itself, is somewhat controversial. However, it appears to be
>justified experimentally by a recent factorization of "15."
>
>BIll Halchin is right that quantum computing is considered
>reversible. The idea of collapse of a wave function providing
>information does appear to be contradictory, although some may rush
>to save any apparent contradictions. As I understand quantum logic,
>it can be represented by a certain non-distributive lattice and as
>Bill says, by composition of matrices, so perhaps we don't have to
>worry so much about the details of quantum theory.
>
>As for wave functions, they might be represented as sampled
>functions, lazily, in infinite "lists." My understanding of quantum
>computing is that whole distributions are computed, not just a
>single possible outcome. Then one is only concerned with computing
>the sampled probability distribution of the outcomes. However, the
>computational burden of doing this is massive, supposedly too
>massive for current digital computers.
>
>Byron Hale
>
>At 01:06 AM 10/5/2002 +0000, you wrote:
>
>>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 | [EMAIL PROTECTED]
>> > than astronomy is about telescopes." -Dijkstra |
>>www.isi.edu/~hdaume
>> >
>> >
>> >_______________________________________________
>> >Haskell mailing list
>> >[EMAIL PROTECTED]
>> >http://www.haskell.org/mailman/listinfo/haskell
>>
>>
>>----------
>>Chat with friends online, try MSN Messenger: Click Here
>>_______________________________________________ Haskell mailing
>>list [EMAIL PROTECTED]
>>http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
