From: David Honig <honig@sprynet.com>
Date: Sat, 15 Aug 1998 12:08:52 -0700 (PDT)
To: coderpunks@toad.com
Subject: Re: quantum problem suggestions?
In-Reply-To: <35CF84B2.72A@accessdata.com>
Message-ID: <3.0.5.32.19980815115529.007dfce0@m7.sprynet.com>
MIME-Version: 1.0
Content-Type: text/plain


At 05:39 PM 8/10/98 -0600, Mike Stay wrote:
>I'm looking for a problem in cryptogrpahy that might be solvable (or at
>least, done faster) on a quantum computer that hasn't been treated yet. 
>Any suggestions?
>-- 
>Mike Stay


No, but you may be interested in: 
_Science_ Vol 281 7 Aug 98 p 793
"Abrams et al. have shown that if there was 
even the slightest amount of nonlinearity in
quantum mechanics, no matter what, it would be possible to modify the
amplitude amplification scheme of quantum search to obtain an efficient
algorithm for NP-complete problems"

The Abrams ref is D. Abrams et al, quant-ph/9801041
	
The article ends with perhaps the understatement of the millenia:
"It is possible that one of these might result in an algorithm that could
solve NP complete problems.  Such a solution would greatly increase the
interest in building a quantum computer."


**
"Why is my computer not faster?" asked the gardener.
"Turn the spigot" said the engineer, pointing to the valve
at the far end of the hose which the gardener held.
The gardener did so, and shortly thereafter felt the hose stiffen.
With that, the gardener was enlightened.