A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers
Research Challenge
In recent years, quantum devices have become available that enable researchers — for the first time — to use real quantum hardware to solve problems. However, the number and quality of qubits (the basic unit of quantum information) for universal quantum computers are expected to remain limited, making it difficult to use these machines for practical applications. Concerns about qubit connectivity, high noise levels, the effort required to correct errors, and the scalability of quantum hardware have also limited researchers’ ability to deliver the speed that future quantum computing promises. A hybrid quantum and classical approach may be the answer to tackling this problem with existing quantum hardware.
Approach
A team of researchers at Argonne National Laboratory, Los Alamos National Laboratory, Clemson University, and Fujitsu Laboratories of America developed hybrid algorithms that employ the best features and capabilities of both classical and quantum computers to address quantum computer limitations. For example, classical computers have large memories capable of storing huge datasets — a challenge for quantum devices that have only a small number of qubits. On the other hand, quantum algorithms perform better for certain problems than classical algorithms.
The team demonstrated the hybrid algorithms for practical applications using IBM and D-Wave quantum computers. Argonne is part of the IBM Q hub network (see box at right).
To distinguish between the types of computation performed on two completely different types of hardware, the team referred to the stages of hybrid algorithms as central processing units (CPUs) for classical computers and quantum processing units (QPUs) for quantum computers.
The team seized on graph partitioning and clustering as examples of practical and important optimization problems that can already be solved using quantum computers: a small graph problem can be solved directly on a QPU, while larger graph problems require hybrid quantum-classical approaches.
As a problem becomes me too large to run directly on quantum computers, the researchers use decomposition methods to break the problem down into smaller pieces that the QPU can manage — an idea they borrowed from high-performance computing and classical numerical methods. All the pieces are then assembled into a final solution on the CPU.
Results
The CPU not only found better parameters, but also identified the best sub-problem size to solve on a quantum computer. The team’s work is presented in an article entitled “A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers” (doi.org/10.1109/MC.2019.2908942), featured in the June 2019 special issue of the Institute of Electrical and Electronics Engineers (IEEE) Computer Magazine. Another paper on the same subject was recently accepted in the Journal ofAdvanced Quantum Technologies(doi.org/10.1002/qute.201900029).