$10 Million will buy a Quantum Computer?

Levi Pearson levipearson at gmail.com
Fri Jun 21 22:54:08 MDT 2013


On Fri, Jun 21, 2013 at 4:28 PM, Todd Millecam <tyggna at gmail.com> wrote:

> Basically, what it can do is take the hash space of a crypto algorithm in
> terms of 2^x, and it changes it to 2^(x-q)  where q is the number of qubits
> that the quantum computer is built off of.  Highest qubit count that I've
> seen to date was some isreali researchers could get 13 entangled pairs, so
> that'd make breaking sha256 a take the time of going through 2^51 hashes
> over 2^64,  which means that this particular computer could crack a sha256
> password in about 600 days, over a regular cpu machine which would take 4.9
> million days (not a GPU-accelerated or supercomputing cluster, mind you)

Sorry, no.

A universal quantum computer could do that.  The D-Wave is not a
universal quantum computer.  It follows a single algorithm, a quantum
adiabatic algorithm based on the Ising model known as "quantum
annealing".  There are two different ways to model quantum adiabatic
algorithms; one uses "stoquastic" Hamiltonians, the other does not.
Adiabatic quantum computing with non-"stoquastic" Hamiltonians has
been shown to be equivalent in computational power to the quantum
circuit model, but using "stoquastic" ones is (probably) less
powerful, and it's only an unproved possibility that it's more
powerful theoretically than classical computing.

The D-Wave does use the "stoquastic" Hamiltonians, which means the
"Hamiltonian obeys conditions of the Perron-Frobenius theorem: all
off-diagonal matrix elements in the standard basis are real and
non-positive."  (quoted from http://arxiv.org/abs/quant-ph/0606140).
Such Hamiltonians are apparently common in nature.  It also turns out
that they can be efficiently simulated on a classical computer via the
Quantum Monte Carlo algorithm, because the "stoquastic" property means
that the ground state can be completely characterized by a classical
probability distribution.

The D-Wave computer basically follows one general algorithm, which
happens to be a pretty useful one, but it's theoretically unclear
whether it does so in a manner that is more powerful than a classical
computer.  To add insult to injury, a paper was very recently
published where a researcher implemented a QMC implementation of the
very same problem encoding that the D-Wave solves.  Running on a
laptop, it found solutions *faster* than the $10 million D-Wave, and
the distributions of the runtimes were highly correlated to the
D-Wave's runtimes.  On the bright side, this suggests that D-Wave *is*
actually achieving high levels of quantum coherence (because the
D-Wave runtime distribution is distinctive, and looks more like the
distribution of QMC than Simulated Annealing, which is a classical
process).

> The protein folding that it can accomplish is helpful for scientific
> purposes, and the $10 million makes sense in that context, but it's again,
> research, so not necessarily practical application.

Here's an article from Nature regarding its not-so-stellar performance
at solving protein folding problems (which are indeed an optimization
problem, so well-suited to the quantum annealing algorithm N-Wave
uses):  http://blogs.nature.com/news/2012/08/d-wave-quantum-computer-solves-protein-folding-problem.html

So, they were able to solve an extremely simplified minimization
problem correctly 13 out of 10,000 times.  Whee!  Sign me up!

> The downside is that this machine is liquid-nitrogen cooled because it uses
> superconductors--so the $10 million is hardly representative of operating
> costs.  A single machine like this would probably cost more than $100k/day
> to operate at max load.

Classical computers get pretty expensive to operate when you scale
them up, too, when you factor in power for both the machines and the
air conditioners needed to keep them cool.  But considering you only
need a laptop and a reasonable implementation of the QMC algorithm to
beat the D-Wave at its own game, it's fair to say that anyone who has
bought one of these has overpaid just a bit.  I imagine that they did
so primarily to fund D-Wave's research efforts, as they *are* doing
cool research.  There's just no real practical fruit yet.

TL/DR:
----------
  * D-Wave probably is taking advantage of large-scale quantum
coherence.  This is cool!
  * D-Wave does not do crypto problems. It does optimization problems.
Think 'regression analysis'.
  * The single algorithm it follows can be simulated faster on a
laptop than it runs on the D-Wave.
  * It is an open question whether the quantum algorithm it follows
scales better for any problems than classical computation could
achieve, but at this point it seems unlikely.

        --Levi


More information about the PLUG mailing list