Paper-QO-EN

a:3:{s:6:"locale";s:5:"en_US";s:3:"rtl";i:0;s:9:"flag_code";s:2:"us";}
A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer

A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer

S. Feld, C. Roch, T. Gabor, C. Seidel, F. Neukart, I. Galter, W. Mauerer, and C. Linnhoff-Popien

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave’s quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implementation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.

Frontiers in ICT, 2019, pp. 1-13

PDF Download

Quantum Technology and Optimization Problems: First International Workshop

Quantum Technology and Optimization Problems:
First International Workshop

S. Feld and C. Linnhoff-Popien

Preface

Over the past decade, a wide variety of experimental quantum computing hardware has been invented and used for fundamental demonstrations in laboratories. Initial results confirm the feasibility of such hardware in real-world applications. Recently, one can observe upcoming research in areas like traffic flow optimization, mobile sensor placement, machine learning, and many more. The development of quantum computing hardware, be it in the quantum gate model or adiabatic quantum computation (quantum annealing), has made huge progress in the past few years. This started to transfer know-how from quantum technology-based research to algorithms and applications. This development is offering numerous opportunities to contribute within research, theory, applied technologies, and engineering. The First International Workshop on Quantum Technology and Optimization Problems (QTOP 2019) was held in conjunction with the International Conference on Networked Systems (NetSys 2019) in Munich, Germany, on March 18, 2019. The aim of this workshop was to connect people from academia and industry to discuss theory, technology, and applications and to exchange ideas in order to move efficiently forward in engineering and development in the exciting area of quantum technology and optimization problems. This book comprises a section containing a keynote and four sections with scientific papers. The sessions deal with the following topics that are crucial to the development of future improvements in quantum technology and optimization problems:

• Analysis of optimization problems
• Quantum gate algorithms
• Applications of quantum annealing
• Foundations of quantum technology

The international call for papers resulted in the selection of the papers in these proceedings. The selection of the papers followed a rigorous review process involving an international expert group. Each paper was reviewed by at least three reviewers. We express our gratitude to all members of the Program Committee for their valuable work. We also want to thank the members of the Mobile and Distributed Systems Group, and especially the Quantum Applications and Research Laboratory (QAR-Lab) who were responsible for the organization of the conference.

QTOP 2019, Munich, Germany, March 18, 2019, Proceedings, Springer, 2019, vol. 11413

PDF Download

Assessing Solution Quality of 3SAT on a Quantum Annealing Platform

Assessing Solution Quality of 3SAT on a Quantum Annealing Platform

T. Gabor, S. Zielinski, S. Feld, C. Roch, C. Seidel, F. Neukart, I. Galter, W. Mauerer, and C. Linnhoff-Popien

Abstract

When solving propositional logic satisfiability (specifically 3SAT) using quantum annealing, we analyze the effect the difficulty of different instances of the problem has on the quality of the answer returned by the quantum annealer. A high-quality response from the annealer in this case is defined by a high percentage of correct solutions among the returned answers. We show that the phase transition regarding the computational complexity of the problem, which is well-known to occur for 3SAT on classical machines (where it causes a detrimental increase in runtime), persists in some form (but possibly to a lesser extent) for quantum annealing.

1st International Workshop on Quantum Technology and Optimization Problems (QTOP 2019), 2019, pp. 23-35

PDF Download

Page 3 of 3