Tohoku University researchers and scientists from automotive components manufacturer Denso report developing an algorithm that improves the ability of D-Wave Systems to handle complicated problems. The algorithm works by partitioning an original large problem into a group of subproblems. The D-Wave annealer then iteratively optimizes each subproblem to eventually solve the original larger one. An account of the work is posted on the Tohoku website.
Problem size is a major challenge for all approaches to quantum computing. The small number of cubits available, limited qubit interconnectivity, and short coherence times all combine to limit the size and complexity of problems that can realistically be tackled. D-Wave’s quantum annealing (QA) approach, which is not a gate-based computing paradigm, skirts many problems of gate-based models, and has allowed D-Wave to build 2000-qubit systems, by far the largest in terms of number of qubits.
That said QA machines operate very differently. In a real sense, the physical hardware topology is specifically designed to tackle ‘combinatorial optimization problems’. What this means is computational problems must be efficiently mapped to the hardware. This recent work helps by breaking down the size of problems into sizes more convenient for the D-Wave machine. Here is a brief description from a recent Nature paper (Improving solutions by embedding larger subproblems in a D-Wave quantum annealer)” by author Shuntaro Okada (Ph.D. candidate, Tohoku University) and colleagues.
“Limited connectivity between the qubits is a restriction to employing the D-Wave quantum annealer for real-world applications. Before solving an optimization problem, it is necessary to map a problem graph onto a subgraph of the hardware graph. This process is called minor embedding. The problem graph is defined as a graph in which the vertices and edges represent the logical variables and interactions between them, respectively. The hardware graph is defined as a graph for which the vertices and edges represent the qubits and interactions between them, respectively. It is known to be NP-hard to find minor embeddings if both of the problem graph and hardware graph are the part of input, and polynomial time if the problem graph or hardware graph is fixed.”
As is usually the case in quantum computing research, the paper is best read in full.
“The proposed algorithm is also applicable to the future version of the D-Wave quantum annealer, which contains many more qubits,” said Masayuki Ohzeki, another author on the paper from Tohoku. “As the number of qubits mounted in the D-Wave quantum annealer increases, we will be able to obtain even better solutions.”
Link to Tohoku University article: http://www.tohoku.ac.jp/en/press/algorithm_quantum_computing.html
Link to Nature paper: https://www.nature.com/articles/s41598-018-38388-4
Figure Source: Nature Paper.