1998-08-15 - Re: quantum problem suggestions?

Header Data

From: David Honig <honig@sprynet.com>
To: coderpunks@toad.com
Message Hash: 9a83c44c71ad3b82f91b06fd7962852c5fd3b74db61f33e7e81194b5857d555b
Message ID: <>
Reply To: <35CF84B2.72A@accessdata.com>
UTC Datetime: 1998-08-15 19:08:52 UTC
Raw Date: Sat, 15 Aug 1998 12:08:52 -0700 (PDT)

Raw message

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: <>
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.