What issues can D wave quantum processor solve ?

[netqwe]

Is D wave 1024 qubit quantum processor can solve a
1024 cities 'travelling salesman problem' ?
And if not what are the abilities of it ?
Thanks in advance

 

[Strilanc]

The D-Wave machine is an adiabatic quantum annealer. Classical simulated annealing tries to minimize a cost function with respect to some variables by varying the variables in a semi-random way based on a "temperature". Quantum adiabatic annealing is based on slowly varying the Hamiltonian of your system so it goes from a simple Hamiltonian with a known ground state to a complicated Hamiltonian that represents your problem.

The specific type of cost function they can represent is something like $a \cdot x_1 + b \cdot x_2 + c \cdot x_3 + d \cdot x_1 \cdot x_2 + e \cdot x_1 \cdot x_3 + f \cdot x_2 \cdot x_3$, where $a$, $b$, ..., $f$ are constants you set to define the problem and the variables for the machine to optimize are the $x_{whatever}$s. In other words you can have scaling constants for the cost of each individual variable, and also for the pairing of variables. Apparently this is called an "Ising spin glass" problem. But note that the D-wave machine is limited in terms of which pairs can have a non-zero constant; it is restricted to coupling variables that are adjacent in a "chimera graph".

The D-Wave machine beats naive algorithms like classical simulated annealing on problem instances designed to show that advantage. But it's not known if the machine will ever be faster in practical cases, or if the obstacles of having to encode your problem into a chimera-graph subset of an ising spin glass problem and the issue that they don't really have any large-scale coherence will outweigh any benefits of small-scale quantum coherence they manage to achieve. My understanding is that, at the moment, there's a classical algorithm (it's called "Selby's algorithm" on Scott Aaronson's blog) that beats the d-wave machine on its own problem (i.e. the classical algorithm also takes the chimera-ising-whatever coupling constants as inputs, instead of a more direct representation of the problem to solve). That's kind of embarassing.

This recent interview from MIT is informative. Basically all the facts in this post are ultimately sourced to the person they're interviewing, but do keep in mind that he has achieved the de-facto title of "chief d-wave skeptic".

 

[f95toli]

In terms of "practical" problems the machine has so far been used for e.g. image recognition (which presumably is the reason why Google is interested) and a bunch of optimization problems. The current architecture is basically optimized for solving optimization problems where you do not necessarily need the to find the global minima, but where finding one or several "deep" local minima is "good enough"; i.e. the solution is not always perfect but still useful. A typical example -used by D-Wave themselves- would be certain optimization problems in finance ("best stock portfolio") where you are working with inexact information anyway and you just want the computer to quickly give you some near-optimal solutions that you can use.