Google Claims Quantum Annealing Beats Simulated Annealing

[Mike Duvos]

"We found that for problem instances involving nearly 1000 binary
variables, quantum annealing significantly outperforms its classical
counterpart, simulated annealing. It is more than 10^8 times faster than
simulated annealing running on a single core."

http://googleresearch.blogspot.ca/2015/12/when-can-quantum-annealing-win.html

1. Is this actually good for anything other than writing papers?

2. Since the qubits in the D-Wave machine only interact pairwise, this
is unlikely to solve hard instances of anything.

3. This has no implications for crypto.

--
Mike Duvos
m...@wolf359.net

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[William Unruh]

On 2015-12-09, Mike Duvos <m...@wolf359.net> wrote:
> "We found that for problem instances involving nearly 1000 binary
> variables, quantum annealing significantly outperforms its classical
> counterpart, simulated annealing. It is more than 10^8 times faster than
> simulated annealing running on a single core."
>
> http://googleresearch.blogspot.ca/2015/12/when-can-quantum-annealing-win.html
>
> 1. Is this actually good for anything other than writing papers?

Many problems can be cast into minimisation/satisfiability type
problems. Including crypto

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

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

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.


>

[Mike Duvos]

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.

[William Unruh]

On 2015-12-09, Mike Duvos <m...@wolf359.net> wrote:

...

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

I tend to agree with you.

[Jan Panteltje]

On a sunny day (Wed, 9 Dec 2015 01:05:07 +0000 (UTC)) it happened "Mike Duvos"
<m...@wolf359.net> wrote in <n47uo2$1812$1...@adenine.netfront.net>:

>"We found that for problem instances involving nearly 1000 binary
>variables, quantum annealing significantly outperforms its classical
>counterpart, simulated annealing. It is more than 10^8 times faster than
>simulated annealing running on a single core."
>
>http://googleresearch.blogspot.ca/2015/12/when-can-quantum-annealing-win.html
>
>1. Is this actually good for anything other than writing papers?
>
>2. Since the qubits in the D-Wave machine only interact pairwise, this
>is unlikely to solve hard instances of anything.
>
>3. This has no implications for crypto.

I find the original paper hard to digest, but as I have this idea of what they do,
they also are cheating:
<quote from 1512.02206v1.pdf>:
We note that for instances with more qubits, more
quantum hardware resources are brought to bear and
therefore a fair comparison needs to take this into ac-
count [12, 15]. As an extreme example, one could con-
^^^^^^^^^^^^^
template building special purpose classical hardware that
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
would update as many spins in parallel as possible at

state-of-the-art clock rates. The sets of spins that could
be updated in parallel depends on the connectivity graph.
Though such considerations are reasonable, we do not ex-
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
plore this possibility here as we believe that future quan-
^^^^^^^^^^^^^^^^^^^^^^^^^^^
tum annealers will have higher connectivity which will
severely limit the usefulness of such parallelism.

<end quote>

So, make it look better by comparing to a simulation and not to a real hardware solution.

I understand they need to sell and justify their kwantuum spook,
but I am not buying.

Always the keywords:
'believe' 'future' 'quantum' in every f*cking paper on physics these days.
In my NSHO quantum computer is just an analog computer with all its noise problems at that (as limit).
QM theory is wrong, the right theory presented at Copenhagen conference was the Broglie's pilot wave theory,
and that does not suffer from the mysticism created surrounding 'quantum' whatever.

:-)
Just wanted to say that :-)