William Unruh <
un...@invalid.ca> wrote:
> On 2015-12-09, Mike Duvos <
m...@wolf359.net> wrote:
>> 1. Is this actually good for anything other than writing papers?
> Many problems can be cast into minimisation/satisfiability type
> problems. Including crypto
Of course, but quantum/simulated annealing only finds "pretty good"
solutions to problems. This is useful for things like Travelling
Salesman, where an answer that is a smidge longer than the exact
solution is still useful. It is, however, useless for large unique
satisfiability problems derived from crypto, where "almost" doesn't
count.
>> 2. Since the qubits in the D-Wave machine only interact pairwise, this
>> is unlikely to solve hard instances of anything.
> The bits in any computer only interact pairwise. And/Or are pairwise
> operations. No computer can ever solve hard problems. They are always
> finite-- finite memory, finite time. "hard problems" are defined
> assymptotically. Thus, being able to solve the travelling salesman
> problem for number of cities fewer than 10^10^10 in linear time, but
> thereafter in exponential time, would not be solution of a "hard"
> problem. But it sure would be useful.
Of course it suffices for the logical operations of the computer to be
2-input gates, whether the computer is quantum or classical. However,
in this case, "pairwise" refers to the number of qubits the
superposition encompasses, and having all the qubits participate is
essential if quantum computing is ever going to solve hard problems such
as crypto quickly.
>> 3. This has no implications for crypto.
> ???? You know this how?
> IF you could break say 56 bit DES 10^8 times faster than now, it would
> be extremely significant. It would make it completely useless.
DES is already completely useless.
It has no implications for crypto, because annealing can't solve crypto.
Annealing is a combination of things which are solutions in local
regions, not a solution to the global problem. It's like when a metal
cools, and forms not a single crystal, but a bunch of crystals.
We can't break DES with annealing, for the same reason we can't break
DES by dipping a wire frame into soap bubbles and looking for a minimal
surface, or by constructing an electrical circuit with only one stable
state that is the solution and hooking a battery up to it.
> My comments are not to imply that I actually believe the Google claims.
> I do not understand them well enough, but if they are true, they are
> significant.
I can't wait to see what Scott Aaronson, who has been the primary D-Wave
debunker, has to say about all of this.
We've known all along that the D-Wave machine can't find global
solutions to hard instances. Prior to this, we believed that optimal
solvers on an ordinary PC could "anneal" faster than D-Wave could.
I'm surprised by this result, but also expect experts who analyze it to
point out some reason it isn't as shocking as it seems.