SIAM Conference on Parallel Processing for Scientific Computing (PP20)
Combinatorial Optimization on Quantum Computers
Date, Time, and Location
Yuri Alexeev, Argonne National Laboratory, U.S.
Ilya Safro, Clemson University, U.S.
Ruslan Shaydulin, Clemson University, U.S.
Quantum computing has potential to efficiently solve combinatorial optimization problems. Recent advances in both hardware and algorithm development have made it possible to solve small problems on modern quantum computers. Combinatorial optimization problems (especially NP-hard problems) are of particular interest, since for many of these problems efficient classical algorithms are not known. One such problem is MaxCut on graphs. In this minitutorial, we will introduce the MaxCut problem and explain how it can be solved on IBM quantum computers available on the cloud today using the Qiskit framework. Our presentation will assume little to no prior knowledge of quantum computation. Moreover, we will provide examples of how more complicated problems can be solved using the QAOA (Quantum Approximate Optimization Algorithm). The tutorial will be interactive and will use Jupyter notebooks to explain step by step how to formulate and implement algorithms in the Ising Hamiltonian form.
Participants are encouraged to bring their own laptops.