Re: quantum Computing

this term keeps poping up recently.  Can anybody give me a pointer
	to where I can find out more info?  Someone said that it is nonsense,
	"quantum computers?, Isn't that something out of a carlos casteneda
	novel?" I'm just trying to find out the real deal.

It's purest bullshit: there are a class of mathematically difficult
problems called "NP-Complete".  These problems are all equivalent to
one another in difficulty, ie if you can solve one you can solve them
all (that's where the complete part comes is - it's NP-complete if
you can prove that equivalence to another NP-complete problem).

The "NP" part is "Non-deterministic, polynomial time".  What that means
is that there is a solution possible in polynomial time (rather than
exponential time) *ONLY* on a *NON-DETERMINISTIC* machine.  And that's
the fun part, because a non-deterministic machine is one that *guesses*
the correct path every time it has a choice to make.  It's like trying
to guess a 3-bit number, and saying "Is the first bit a 1?" Yes!  "Is the
second bit a 0?" Yes!  "Is the third bit a 0?"  Yes!

Clearly, in real life, this doesn't happen.  However, in fairy-tale land
(or quantum physics as it's called) such things *can* happen - because
one interpretation of the Einstein-Podolsky-Rosen thought experiment is
that every time you make a choice based on the outcome of a quantum
event, you fork off a pair of universes!  In one universe you make
one choice; in the other universe you made the other choice.  Consequently
if you loose a computer on such a problem, in *one* of the many many
universes it generates, it'll find the right answer in polynomial time.

The basis of quantum computing as a means to crack NP-complete problems
therefore reduces to finding which of these universes found the answer and
comminicating that answer to all the other universes.  (Of course, you
don't have to do this part, but the 99.9999999999999999999999999999999%
of experimenters in all the universes that didn't find the result are
not going to believe the method words too well...)

Basically, it's a theoretical result with no application in the real
world, and if ever anything happens that makes it mappable to the
real world we'll have been subjected to such a major upheaval in
the way the universe works that no-one will give a damn any more
about such trivial things as encryption because we'll all effectively
have turned into magicians :-)

G

-----BEGIN PGP SIGNED MESSAGE-----

Disclaimer:  I'd never even heard of a quantum machine until quite
	     recently and I have no idea how they relate to the NP
	     Completeness problem.


    Date: Wed, 18 May 1994 17:47:34 +0100
    From: gtoal@an-teallach.com (Graham Toal)

    . . . it's NP-complete if you can prove that equivalence to
    another NP-complete problem).

    The "NP" part is "Non-deterministic, polynomial time".  What that means
    is that there is a solution possible in polynomial time (rather than
    exponential time) *ONLY* on a *NON-DETERMINISTIC* machine.

Not true.  What that means is that a polynomial time solution exists
for an NFA.  The only part has not been shown.

    And that's the fun part, because a non-deterministic machine is
    one that *guesses* the correct path every time it has a choice to
    make.

That's one way of viewing it, well close anyway.  Typically it's
described as guessing the correct path and then verifying its
correctness.  Another, equally valid way to view a non-deterministic
machine is as one which executes all paths simultaneously.

    Clearly, in real life, this doesn't happen.

Perhaps.  In any case, if you have a proof that the NP-Complete
problems cannot be done in polynomial time on a deterministic machine,
by all means, please share it with us . . . and collect your prize :-)

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdpS7RaZNKPPNj41AQE6qAQAueihy10qYc5HCeJ1Fx2WbR8mvxfRc94i
FK7zkHv916Uo2dPfwnldDvapUAamkALiPpTJ6+6g8L/XuLB+rOc9Nwrzs5WzjVgN
KNKSZ5dN8Fa21RB1gd9jD/hC3ND1Fz/HyYOi6fMtzMFqh08nC27e4C4CDL+QqpHG
glCM7qMVOIY=
=0lM1
-----END PGP SIGNATURE-----

Rick Busdiecker writes:
 > Not true.  What that means is that a polynomial time solution exists
 > for an NFA.  The only part has not been shown.

While we're being picky, I'll point out that (unless I'm wrong of
course) it's not really an NFA, but a non-deterministic Turing
machine (an "NTM"?) that's the automaton at issue here.

--
| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

-----BEGIN PGP SIGNED MESSAGE-----

    Date: Wed, 18 May 94 12:46:46 CDT
    From: m5@vail.tivoli.com (Mike McNally)
    
    While we're being picky, I'll point out that (unless I'm wrong of
    course) it's not really an NFA, but a non-deterministic Turing
    machine (an "NTM"?) that's the automaton at issue here.

No, NFA is acceptable and correct, it's Non-determinisic Finite
Automaton.  A non-deterministic Turing machine is a perfectly
reasonable example, however.

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdpWthaZNKPPNj41AQEttwQAnCs9sZ+fV9BhCMf/PXyM6w59NjIc8ZwF
vVL394XfzqvQKUzwK8pV04d5YMusfgbVibj+IuEaAEkn9qMYkaoX9XL65tzhPf8N
6bilBkRVIuCmLye9J0vpylouqS7bAakF7Htu06EDOzTQArBXEWUaBGkaH5P+m8xu
xQLMS1RmmKk=
=H5dW
-----END PGP SIGNATURE-----

Rick Busdiecker says:
>     From: m5@vail.tivoli.com (Mike McNally)
>     
>     While we're being picky, I'll point out that (unless I'm wrong of
>     course) it's not really an NFA, but a non-deterministic Turing
>     machine (an "NTM"?) that's the automaton at issue here.
> 
> No, NFA is acceptable and correct, it's Non-determinisic Finite
> Automaton.  A non-deterministic Turing machine is a perfectly
> reasonable example, however.

A turing machine is not a finite automaton -- it has an infinite tape.

Perry

Rick Busdiecker writes:
 > No, NFA is acceptable and correct, it's Non-determinisic Finite
 > Automaton.  A non-deterministic Turing machine is a perfectly
 > reasonable example, however.

Uhh, isn't it the case that a Turing machine can simulate an NFA, but
not the reverse?  An NFA has no tape, and therefore is not as powerful
an automaton as a Turing machine.  Thus an NFA can be implemented by
an NTM, but not the reverse.

I think.

--
| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

Mike McNally says:
> 
> Rick Busdiecker writes:
>  > No, NFA is acceptable and correct, it's Non-determinisic Finite
>  > Automaton.  A non-deterministic Turing machine is a perfectly
>  > reasonable example, however.
> 
> Uhh, isn't it the case that a Turing machine can simulate an NFA, but
> not the reverse?  An NFA has no tape, and therefore is not as powerful
> an automaton as a Turing machine.  Thus an NFA can be implemented by
> an NTM, but not the reverse.
> 
> I think.

Correct. The hierarchy as I remember it is roughly (from least to most
powerful in terms of size of the recognizable languages) FAs, PDAs
(that is, deterministic push-down automata), NPDAs, TMs. Its been a
while, but I seem to recall that non-deterministic pushdown automata
could recognise some languages that deterministic ones could not.

Perry

-----BEGIN PGP SIGNED MESSAGE-----

    Date: Wed, 18 May 1994 14:14:41 -0400
    From: "Perry E. Metzger" <perry@imsi.com>

    Its been a while, but I seem to recall that non-deterministic
    pushdown automata could recognise some languages that
    deterministic ones could not.

Yes, that's correct.

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdpcUxaZNKPPNj41AQHRRQQAjzRo7nSxd5meEjSoExGUhJJSQ2H63wEZ
VDlZ9627j7kAVZHGvM0H6JNeN5IIgRX7hv2cruZwE8Gm49bZxE/iEgOLA1p0/IK+
T31BzIEebccwbKYF97Ndnf3kFHD36XVL8QEVJ09yGHjX7uyL5Vd2Gk7cb8ljp3JU
C3QX3YTB4FU=
=sV/8
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----

    Date: Wed, 18 May 94 13:03:43 CDT
    From: m5@vail.tivoli.com (Mike McNally)
    
    An NFA has no tape . . .

Mine does :-)

It's a matter of definition, I suppose.  Hopcroft and Ullman describe
an NFA as having a tape.

On the other hand, they also descript the NP Completeness in terms of
an NTM, so I'll concede your point.

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdpbIRaZNKPPNj41AQHG+gQAtYMYanQzNIYeWV8DlIr+LAT8Lu7UNZWD
DzZMa30vlliUU9twWZW23fiQltWKGx0GG73IG3egLJ01Qeo1t7aN6Dl20+Jm2CIQ
xDxOrQc+I+rakSW4/MmC5PgfoXazKTtF3X+BaRXdkfZqvH0Lt9hvzaEJ0nA43iG9
YIpXYDesqcc=
=/Plo
-----END PGP SIGNATURE-----

> From: Rick Busdiecker <rfb@lehman.com>
> It's a matter of definition, I suppose.  Hopcroft and Ullman describe
> an NFA as having a tape.

I find this a little odd, given that the "F" stands for "finite".
Checking Hopcroft and Ullman, they define an NFA formally as a
tuple: states, inputs, initial state, final states, and a mapping
from states cross inputs to 2^states.  No tape.

   Eli   ebrandt@hmc.edu

-----BEGIN PGP SIGNED MESSAGE-----

I was in a hurry and misread something to be supporting something else
that I had misremembered.  I apologize for not being more careful and
I continue to concede the point that NP completeness is defined in
terms of NTMs rather than NFAs.

FWIW, what I misread was a blurb near the front of Formal Languages
and Finite Automata (I'm guessing at the title, the book is no longer
near by) H&U simply described the input to the machine as a tape.

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdq6lBaZNKPPNj41AQH/EAP/eZlxtjQbzlsVssKmY9n7Smh0bGwgVPQr
tQ8mhBBQFPeByTR24wPp2qINws8WgzDI9EOTnrkSxs0NI6Ig3uusXxHEdPfhUfnl
kO2uTgAJ/pFztQXyvCIkGyAs0RlthLaatpquZFue07r2JFOo0AB7XG6CprF9kvGH
eTjfWvb+Ygo=
=BUsf
-----END PGP SIGNATURE-----