Pages

February 09, 2011

Latest Theoretical work by Dwave Systems shows progress to solutions of NP-Hard problems and causes one critic of their quantum computer work to partially recant

A Dwave systems, adiabatic quantum computer, critic (Chris Lee at Ars Technica) has retracted statement that Dwave was borderline fraudulent.

Geordie and friends, I am sorry. I don't know if you have a working device, but the theoretical work produced by D-Wave is sharp and a great indication that you are honestly pursuing your stated goals.

Physical Review Letters - Does Adiabatic Quantum Optimization Fail for NP-Complete Problems ?

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.



Arxiv- Does Adiabatic Quantum Optimization Fail for NP-Complete Problems ? (4 pages)
It is important to note that we are not trying to prove that all level crossings between a global minimum and local minima can be eliminated in polynomial time. Neither are we claiming that if they are eliminated, the MIS problem can be solved in polynomial time. Even if all level crossings are eliminated, the scaling of the minimum gap in the rest of the spectrum is still unknown. What we are stating here is that there always exist paths along which no crossing occurs, at least up to second order perturbation. Since MIS is NP-hard, any NP problem can be polynomially mapped onto it. Therefore, a valid proof that any NP-complete problem cannot be solved using AQO because of level crossings must prove that for the problem mapped onto MIS, it is impossible to find an assignment of parameters for which there is no level crossing. Further, due to the NP-hardness of approximating solutions to MIS, even if there are multiple crossings, AQO may produce sufficient solutions to solve NP-complete problems.

In conclusion, using perturbation expansion, we have shown that for the NP-hard problem of MIS, it is always possible to write down a Hamiltonian for which during the adiabatic evolution no crossing occurs between a global minimum and any of the local minima. If there is no degeneracy in the local minima, or if there are degenerate local minima but no pair of them is exactly 2 bit flips apart, such a Hamiltonian can be trivially obtained by increasing the coupling coefficient between the qubits linearly with the size of the problem. In cases with local minima exactly 2 bit flips away from each other, one can use the freedom of choosing the initial Hamiltonian to avoid level crossings. In the latter case, finding an assignment for tunneling amplitudes [Triangle sub i] may or may not be nontrivial. However, we have shown that such an assignment always exists. In general, there are infinite ways of defining the Hamiltonian, including those where many approximate solutions suffice, therefore it seems infeasible to prove that no successful Hamiltonian can be obtained in polynomial time.

One of the arguments used against adiabatic quantum computing is almost certainly wrong. This doesn't show that the approach will work or that it will be faster than any other sort of computer, but it tells us that D-Wave may yet produce something useful.

To begin with, let's clarify a few things. D-Wave refers to its device as a quantum optimizer, and I refer to it as an adiabatic quantum computer. The two are not quite identical: an adiabatic quantum computer uses the idea that mathematical problems can be restated in terms of a Hamiltonian—the mathematical term for the energy of the forces that push a bunch of particles about. The desired solution to the problem then turns out to be the lowest energy state, called the ground state, of the particles being pushed about by the Hamiltonian. In a quantum system, the Hamiltonian describes quantum particles and their quantum states.

Unfortunately, getting everything into the ground state is as hard as solving the original problem, so you might think that we haven't gotten anywhere. You would be wrong. What we do instead is set the Hamiltonian to something easy to solve and put our particles in the ground state of that Hamiltonian. Now, we carefully prod at the Hamiltonian until it has the shape of the problem we want to solve. If we have done that carefully enough, the particles will have remained in the ground state and, once we read out their state, we have the solution to the original problem. Going from one Hamiltonian to another while keeping all the particles in the ground state is called an adiabatic passage, hence the name adiabatic quantum computing.

The key is remaining in the ground state. Our ability to make a truly adiabatic passage in a system with lots and lots of particles has been questionable. The general approach to get around this has been to do the adiabatic trick multiple times and never end up in the ground state, but remain near it. What you are doing is generating a group of approximate solutions to the problem. With that in hand, you can use classical computing to go the remaining distance and get the exact solution. This is what D-wave does, and hence, D-Wave refers to its device as a quantum optimizer, not a quantum computer.

For this to work, you still need to remain near the ground state, and it would really help if there was actually a set of changes to the Hamiltonian that would reliably take you to the ground state—even if you have to spend a bit of time in trial and error searching to find such a path.

This is where the controversy over D-Wave's claims has lain. Several researchers have argued that once the number of particles got large enough to be interesting, there would be no path from a starting Hamiltonian to a final Hamiltonian that didn't involve some of the particles jumping into an excited state.

In answer to their critics, Dickson and Amin from D-Wave Systems have published a paper that seeks to show that such a path does exist. They looked at a specific problem, called the Maximum Independent Set problem, which falls into a set of problems called NP-hard—these are problems that scale in a very unfortunate way on classical computers. They chose this problem because, once you show something can be done for one NP-hard problem, you have shown that it works for all problems in the NP set.

Using this problem as a basis for the mathematics, they showed that it is always possible to choose a starting Hamiltonian such that they could avoid local minima and arrive at a global minimum: the solution to the problem in this case. There are some restrictions, though: the local minima had to be a certain amount more energetic than the ground state for this to be true.

What does this mean? Well, first, it doesn't mean that a quantum optimizer is going to get to the solution any faster than a classical computer, because the speed at which you tweak the system depends on the distance between the ground state and the first excited state: the closer they are, the slower you have to go. So, there is no guarantee of any additional speed here. Indeed, given that one of the seminal works on Adiabatic quantum computing was simply to prove that it was functionally identical to logic-gate-based quantum computers, it would be a major breakthrough to show such a speed up.

What this new paper really is, then, is a proof that places the basic functionality of adiabatic quantum computing—no matter how it is actually implemented—on much firmer theoretical ground.

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
blog comments powered by Disqus