Re: qubits

From: Cristiano Sadun (cristianoTAKEsadun_at_THIShotmailOUT.com)
Date: 10/14/04 

Date: Thu, 14 Oct 2004 08:09:12 +0000 (UTC)

"H. S. Lahman" <h.lahman@verizon.net> wrote in
news:4zfbd.74$OK1.3@trndny06:

> That's assuming the program's language fully exploits Qubits for the
> factorization. B-) My point is that I suspect a port of existing
> 3GLs would be pure emulations (i.e., they would only utilize two of
> the available hardware states), in which case the program might run
> slower on a Qubit machine than on a binary machine.

Yes, I think I can see what you meant. Certainly if used with no change
whatsoever, software won't necessarily run faster. And technologically
the first step would be to use "traditional" languages emulating them.

Shor's factorization algorithm, tough, was explicitly tought for
exploiting the particular properties of a quantum turning machine - and
cannot be implemented without one.

If we had QTM-equivalent hardware (with all the usual limitations of
ideal TMs translated into real hardware), it could be implemented
immediately, and form the basis for a relatively simple password-cracking
application - you intercept and record, say, an HTTPs conversation
between Mr X. and his bank, then decrypt it with the algorithm in a
reasonbly short amount of time.

To do that, you'd certainly need a language that allows direct usage the
QTM properties - namely, direct measurement of both internal and tape
slots state which are both quantistic. But that - once made the
breaktrough of building a viable hardware equivalent of a QT - is "just"
a matter of technology. It wouldn't happen overnight, but would happen
relatively soon.

Of course most software suffers from a different type of complexity than
the pure computational one - and there QTMs don't help a (qu) bit.. :-D

I'm not sure if I'm being clear enough on what I mean..

 
> That applies abstractly as well. For example, if the algorithm
> utilizes boolean FALSE/NOT-FALSE conditions for decision making when
> encoded, having Qubits will not help with evaluating the gazillions of
> branches made during the processing; one needs to have a richer notion
> of conditions in mind AND syntax support for it _as one encodes the
> algorithm_.

The peculiarity of Shor's algorithm should be that it uses features
allowed only by the QTM - and Shor's showed how this does improve, in
terms of computational "speed", on the previous best - the probabilistic
TM. I read the paper so many years ago I don't recall the details (we can
check together) but the point should be that the algorithm does *not*
utilizes normal conditions.

> IOW, before implementing any algorithm /effectively/ on a Qubit
> machine we would need a whole new set of software toys and training to
> use them properly.

Yes, that's for sure. In other words, how many QTM-specific algorithms do
we have besides Shor's one? An interesting question, to which I don't
know the answer, but now you've stimulated my curiosity so I'll try and
find out..

Relevant Pages