D-Wave Systems
IBM Quantum Computing

Quantum computing has been hyped for a long time, and the first usable quantum computers have gone on the market in the last few years.

Quantum computers use quantum bits or qubits, and use quantum-mechanical effects for fast computation. The D-wave machines implement qubits with superconducting loops. The amount of magnetic flux (magnetic field integrated over area) going through each loop is quantized, thus having amounts that are some multiple of a quantum of magnetic flux. Qubit loops that are near each other can interact, thus making quantum-mechanical entanglement and mixed states.

A big difficulty with both the D-wave and the IBM sites is that they are not very explicit about their model of computation. I did a lot of searching in their sites and it was hard to find anything. The D-wave machine apparently uses a "binary quadratic" model.

Minimize D(x,a,b) = (sum over i of ai*xi) + (sum over i,j of bi,j*xi*xj)

Here, the x's are the qubit values, 0 or 1, and the a's and b's real numbers.

So if one can turn one's problem into a binary-quadratic problem, one has got it made.

For n qubits, the total number of possible values of D is 2n, and quantum effects make possible much faster searching than a classical-limit-computing full search. Such fast solution of exponential-time or factorial-time problems is a major reason for interest in quantum computing. Classical-limit computing has several relatively fast algorithms for approximate solution of such problems, but this speed has a price. These algorithms that will discover some local minimum with no guarantee that it will be a global minimum.