Sherry Mayo writes

Detractors of the proposed technique say problems of noise and sensitivity to mechanical defects are insurmountable and the technique could never work.

I was wondering if anyone here has any comment. After reading the New Scientist

I was wondering if anyone here had any views (informed or otherwise :-)

My ill informed back of the envelope guestimate is that current art is a factor of one hundred from building a proof of principle quantum computer, a factor of one thousand from building a quantum computer that does something interesting, and a factor of ten thousand from building a quantum computer that does something that is actually useful. Art is improving at (very roughly) a factor of two every four years. These estimates may well be rather optimistic, but they are not totally ridiculous. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com

Sherry Mayo wrote:

Sorry if this has already been brought up (I've been skimming through c'punx lately and may have missed it) but does anyone have any comment on this thread (see title).

I first read about this in New Scientist (Sept 24th, No 1944). To summarize: Shor came up with an algorithm that could use quantum effects to rapidly factorise large primes. To build such a quantum computer requires manufacturing techniques not yet available, although two other researchers (one is called Eckart) streamlined Shor's algorithm and proposed a design for a "factorization engine" using quantum dot technology. You'd need to put a lot more quantum dots on a chip than is currently possible to build such a device, but the suggestion could be possible in a few years time. the article hinted that Hitachi were already hard at work on the problem.

Several companies are pursuing advanced lithography techniques and alternatives to conventional CMOS; the work on "quantum wells" and "quantum dots" is along these lines. I'm not holding my breath. (Rather, I *am* holding my Intel stock, as I see no significant chance that anything will displaced fairly conventional circuitry and lithography anytime soon.) In any case, the Shor work on a quantum factorer is interesting, but is at least several decades away, in my opinion. And even then it is likely to be "workable" out to some number of digits (roughly, number of digits = precision needed), by which time the conventional advances in computer power will mean we're all using 10,000-bit moduli (especially if we have just heard that NSA has just spend $32 billion to build a Shor machine able to factor 3000-bit moduli :-} ). Our own James Donald has written several long essays on Shor's results, taking a more optimistic (or pessimistic, depending on one's goals) view. Also, as Sherry noted, extensive discussion pops up in sci.crypt and the new group, sci.crypt.research. Bennett and Brassard's quantum cryptography, also discussed extensively, is closer to be realized practically. (It uses the Uncertainty Principle for polarized photons in a fiber optic cable to determine if a channle has been tapped.) A plug for the Cyphernomicon FAQ: My FAQ has several entries on quantum methods for crypto. Grep it for quantum, Shor, Brassard, Bennett, etc.

I suppose cypherpunks should keep up with the latest developments (or even possibilities), and where there's quantum cryptanalysis presumably there's also quantum cryptography :-)

Sherry

There is indeed interest in this. But bear in mind that even the most optimistic proponents admit this stuff is many years, probably many decades, away. Sort of like where the crypto that now interests us was in 1925. (And I think conventional number-theoretic crypto will stay way ahead of any machines that can ever be built. A gut feel, but based loosely on the exponential increase in complexity vs. the linear growth in technology.) --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. Cypherpunks list: majordomo@toad.com with body message of only: subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tcmay

Timothy C. May writes:

In any case, the Shor work on a quantum factorer is interesting, but is at least several decades away, in my opinion.

Operating from the assumption that this work by Shor is realistically worthwhile, has there been any research into employing similar techniques for encryption? In other words, in the "world" of quantum algorithmics, are there analogs to the hard problems currently exploited by cryptographic systems in our current Turing machine "world"? | 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" |