Quantum annealing of the quadratic assignment problem

Authors: Mengyu Guo*, Department of Geography and Geographic Information Science, University of Illinois at Champaign and Urbana, Shaowen Wang, Department of Geography and Geographic Information Science, University of Illinois at Champaign and Urbana
Topics: Spatial Analysis & Modeling, Location Theory
Keywords: Quantum computing, quantum annealing, quadratic assignment problem, path-integral Monte Carlo
Session Type: Paper
Day: 4/11/2018
Start / End Time: 10:00 AM / 11:40 AM
Room: Astor Ballroom I, Astor, 2nd Floor
Presentation File: No File Uploaded

Quantum annealing has emerged as a promising quantum computing approach to solving hard combinatorial optimization problems. It bears some resemblance to classical simulated annealing in terms of mimicking physical processes whereby an object is cooled in a controlled manner so that it freezes just as the object attains its minimum energy. The intuition behind quantum annealing is that it explores energy landscape with means not open to classical methods, such as quantum superposition and tunneling. By far, both theoretical and numerical results suggest that quantum annealing can dramatically improve computational performance of solutions to a number of hard optimization problems (e.g. traveling salesman problem, Ising spin glass) where state-of-the-art classical approaches fail. In this research, we apply quantum annealing to the quadratic assignment problem, a well-known spatial optimization problem. Specifically, we propose a novel formulation of the quadratic assignment problem in quantum annealing through re-expressing the classical optimization problem as a quantum system subjected to annealing. To simulate the quantum annealing process, we adopt a path-integral Monte Carlo scheme instead of an actual Schrödinger evolution of the quantum system proposed—due to significant computational intensity. Numerical experiments are conducted on small-scale instances to validate the feasibility and computational efficiency of quantum annealing of the quadratic assignment problem, as compared with classical simulated annealing. Our preliminary results are promising to lead to generic guidelines for formulating spatial problems and tuning parameters in quantum annealing.

Abstract Information

This abstract is already part of a session. View the session here.

To access contact information login