New algorithm optimizes quantum computing problem-solving

New algorithm optimizes quantum computing problem-solving
Embedding on a special graph of the D-Wave 2000Q by solving a problem like a puzzle in our technique. Credit: Tohoku University

Tohoku University researchers have developed an algorithm that enhances the ability of a Canadian-designed quantum computer to more efficiently find the best solution for complicated problems, according to a study published in the journal Scientific Reports.

Quantum computing takes advantage of the ability of subatomic particles to exist in more than one state at the same time. It is expected to take modern-day computing to the next level by enabling the processing of more information in less time.

The D-Wave annealer, developed by a Canadian company that claims it sells the world's first commercially available quantum computers, employs the concepts of quantum physics to solve 'combinatorial optimization .' A typical example of this sort of problem asks the question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each and returns to the original city?" Businesses and industries face a large range of similarly complex problems in which they want to find the optimal solution among many possible ones using the least amount of resources.

Ph. D candidate Shuntaro Okada and information scientist Masayuki Ohzeki of Japan's Tohoku University collaborated with global automotive components manufacturer Denso Corporation and other colleagues to develop an algorithm that improves the D-Wave quantum annealer's ability to solve combinatorial optimization problems.

The algorithm works by partitioning an originally large problem into a group of subproblems. The D-Wave annealer then iteratively optimizes each subproblem to eventually solve the original larger one. The Tohoku University algorithm improves on another algorithm using the same concept by allowing the use of larger subproblems, ultimately leading to the arrival at more optimal solutions more efficiently.

"The proposed algorithm is also applicable to the future version of the D-Wave quantum annealer, which contains many more qubits," says Ohzeki. Qubits, or quantum bits, form the basic unit in . "As the number of qubits mounted in the D-Wave quantum annealer increases, we will be able to obtain even better solutions," he says.

The team next aims to assess the utility of their for various optimization problems.

Explore further

Simon's algorithm run on quantum computer for the first time—faster than on standard computer

More information: Shuntaro Okada et al. Improving solutions by embedding larger subproblems in a D-Wave quantum annealer, Scientific Reports (2019). DOI: 10.1038/s41598-018-38388-4
Journal information: Scientific Reports

Provided by Tohoku University
Citation: New algorithm optimizes quantum computing problem-solving (2019, April 10) retrieved 22 August 2019 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors

User comments

Apr 11, 2019
Splitting a problem like the traveling salesman into smaller problems is not an accurate representation of the original problem.

Any problem which can be optimized by splitting it into smaller problems does not benefit from a quantum speedup since it can also be split into smaller problems on a classical computer.

The headline "New algorithm optimizes quantum computing problem-solving" is misleading and inaccurate.

eg. If you split 500 cities into 10 x 50 cities and optimize each chunk of cities the solution is not guaranteed to be the optimal solution since movements from a chunk of cities would not be allowed until all cities in a chunk of cities has been visited.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more