Feel the quantum power!!! September 21, 2007
Posted by Geordie in Published Stuff.trackback
Blinding you… with SCIENCE!!! here.
The effect of local minima on quantum adiabatic optimization
We present a perturbative method to estimate the spectral gap for quantum adiabatic optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that for problems that have exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.
2008 is coming , how is the process? i am watching you.
Sorry bout your acl, that sucks. I half tore mine about 2 years ago, but it was able to mend itself without the graft surgery. Good luck with that.
OK – I’m blinded.
This paper proves that AQC’s aren’t good for solving a class of problems that have “an exponentially large number of local minima close to the global minimum”.
- What kind of problems are these? Ones that have a large number of “nearly right” solutions?
- How widespread are these problems?
- What problems does it leave
- does this seriously reduce the applicabilty of AQCs?
Hi Peter,
Most optimization problems have the feature that the data that defines the instance is subject to error. For example if I want to find an optimal route for a fleet of trucks, and my database contains information used to compute a cost function for those routes (distances, etc.) that are only approximately correct, then the “globally best” solution may not actually be the best route in reality. What this means in practice is that all solutions within some threshold of the optimal solution are more or less equally likely to be the real global optimum.
If a particular optimization problem instance has the feature that an exponential number of solutions all are very close to the global minimum, this means that any of these are acceptable solutions. Therefore these are “extremely easy” optimization problems in practice, and a system such as ours would efficiently return any of the multitude of acceptable solutions.
These problems seem to be very rare. None of the problems we’ve seen from partners have looked anything like this. It doesn’t affect the applicability of the approach much.
There are likely crypto apps where you could use this vulnerability to “hide” answers from a system such as ours, but we’re not interested in crypto problems.
Jonathan: Thanks… I will probably be having the reconstruction late November/early December… I am really looking forward to a year of painful rehab… should be fun.