On Fri, Jun 21, 2013 at 4:28 PM, Todd Millecam <[email protected]> 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 /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
