Re: quantum problem suggestions?

David Honig (honig@sprynet.com)
Sat, 15 Aug 1998 11:55:29 -0700

• Next message: Bill Stewart: "Re: Request for information on cryptanalysis"
• Previous message: Trei, Peter: "Cleansing the NT swap file."
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"

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.

• Next message: Bill Stewart: "Re: Request for information on cryptanalysis"
• Previous message: Trei, Peter: "Cleansing the NT swap file."
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"