Paper Info
Title
First Results Solving Arbitrarily Structured Maximum Independent Set Problems Using Quantum Annealing
Abstract
Commercial quantum processing units (QPUs) such as those made by D-Wave Systems are being increasingly used for solving complex combinatorial optimization problems. In this paper, we review a canonical NP-hard problem, the Maximum Independent Set (MIS) problem. We show how to map MIS problems to quadratic unconstrained binary optimization (QUBO) problems, and use a D-Wave 2000Q QPU to solve them. We compare the results from the D-Wave system to classical algorithms such as simulated thermal annealing and the graphical networks package NetworkX. To our knowledge, these are the first results of experiments involving arbitrarily-structured MIS inputs using a D-Wave QPU. We find that the QPU can be used as a heuristic optimizer for randomly generated inputs, but due to physical control errors, can be outperformed by simulated thermal annealing.
Year
DOI
Venue
2018
10.1109/CEC.2018.8477865
2018 IEEE Congress on Evolutionary Computation (CEC)
Keywords
Field
DocType
quantum annealing,complex combinatorial optimization problems,canonical NP-hard problem,quadratic unconstrained binary optimization problems,simulated thermal annealing,graphical networks package NetworkX,D-Wave QPU,heuristic optimizer,quantum processing units,D-wave systems,arbitrarily structured maximum independent set problems,MIS problems,QUBO,arbitrarily-structured MIS inputs,randomly generated inputs,physical control errors
Mathematical optimization,Heuristic,Combinatorial optimization problem,Quadratic unconstrained binary optimization,Computer science,Quantum annealing,Schedule,Software,Independent set,Quantum information science
Conference
ISBN
Citations 
PageRank 
978-1-5090-6018-4
1
0.34
References 
Authors
4
3
Name
Order
Citations
PageRank
Sheir Yarkoni1212.01
Aske Plaat252472.18
Thomas Bäck3132.32