Mapping graph coloring to quantum annealing
- PDF / 2,371,524 Bytes
- 19 Pages / 595.224 x 790.955 pts Page_size
- 72 Downloads / 264 Views
RESEARCH ARTICLE
Mapping graph coloring to quantum annealing Carla Silva1
ˆ Dutra4 · Ana Aguiar2 · Priscila M. V. Lima3 · Ines
Received: 11 June 2020 / Accepted: 7 October 2020 © Springer Nature Switzerland AG 2020
Abstract Quantum annealing provides a method to solve combinatorial optimization problems in complex energy landscapes by exploiting thermal fluctuations that exist in a physical system. This work introduces the mapping of a graph coloring problem based on pseudo-Boolean constraints to a working graph of the D-Wave Systems Inc. We start from the problem formulated as a set of constraints represented in propositional logic. We use the SATyrus approach to transform this set of constraints to an energy minimization problem. We convert the formulation to a quadratic unconstrained binary optimization problem (QUBO), applying polynomial reduction when needed, and solve the problem using different approaches: (a) classical QUBO using simulated annealing in a von Neumann machine; (b) QUBO in a simulated quantum environment; (c) actual quantum 1, QUBO using the D-Wave quantum machine and reducing polynomial degree using a D-Wave library; and (d) actual quantum 2, QUBO using the D-Wave quantum machine and reducing polynomial degree using our own implementation. We study how the implementations using these approaches vary in terms of the impact on the number of solutions found (a) when varying the penalties associated with the constraints and (b) when varying the annealing approach, simulated (SA) versus quantum (QA). Results show that both SA and QA produce good heuristics for this specific problem, although we found more solutions through the QA approach. Keywords Adiabatic quantum computation · Quadratic unconstrained binary optimization · Constraint and logic programming · Symbolic calculus algorithms · Pseudo-Boolean optimization
1 Introduction Carla Silva
[email protected] Ana Aguiar [email protected] Priscila M. V. Lima [email protected]; [email protected] Inˆes Dutra [email protected] 1
Department of Computer Science, Faculty of Sciences, University of Porto, Porto, Portugal
2
Faculty of Engineering, Instituto de Telecomunicac¸o˜ es and Department of Electrical and Computer Engineering, Porto, Portugal
3
PESC/COPPE/CT and Tercio Pacitti Institute/CCMN and Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
4
CINTESIS and Department of Computer Science, Faculty of Sciences, University of Porto, Porto, Portugal
Quantum computing is an emerging field where science seeks to solve NP-hard problems more efficiently than classical algorithms, taking advantage of quantum phenomena such as entanglement and tunneling (Nielsen and Chuang 2010; Ladd et al. 2010). Current technology has allowed the building of different quantum devices that can actually solve small problems. Practical experiments have been performed in these devices in order to better study their behavior and reliability. Some of these devices make use of the concept of quantum annealing (QA) (Fujii 2018), hav
Data Loading...
