a:3:{s:6:"locale";s:5:"en_US";s:3:"rtl";i:0;s:9:"flag_code";s:2:"us";}

Christoph Roch, Thomy Phan, Sebastian Feld, Robert Müller, Thomas Gabor, Carsten Hahn, Claudia Linnhoff-Popien

We introduce Q-Nash, a quantum annealing algorithm for the NP-complete problem of finding pure Nash equilibria in graphical games. The algorithm consists of two phases. The first phase determines all combinations of best response strategies for each player using classical computation. The second phase finds pure Nash equilibria using a quantum annealing device by mapping the computed combinations to a quadratic unconstrained binary optimization formulation based on the Set Cover problem. We empirically evaluate Q-Nash on D-Wave’s Quantum Annealer 2000Q using different graphical game topologies. The results with respect to solution quality and computing time are compared to a Brute Force algorithm and the Iterated Best Response heuristic.

Published in 20th International Conference on Computational Science (ICCS 2020), 2020, p. 12. doi:10.1007/978-3-030-50433-5_38

S. Feld, C. Roch, K. Geirhos, and T. Gabor

Archetypes are those extreme values of a data set that can jointly represent all other data points. They often have descriptive meanings and can thus contribute to the understanding of the data. Such archetypes are identified using archetypal analysis and all data points are represented as convex combinations thereof. In this work, archetypal analysis is linked with quantum annealing. For both steps, i.e. the determination of archetypes and the assignment of data points, we derive a QUBO formulation which is solved on D-Wave’s 2000Q Quantum Annealer. For selected data sets, called toy and iris, our quantum annealing-based approach can achieve similar results to the original R-package archetypes.

*28th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2020)*

M. Friedrich, C. Roch, S. Feld, C. Hahn, and P. Fayolle

CSG trees are an intuitive, yet powerful technique for the representation of geometry using a combination of Boolean set-operations and geometric primitives. In general, there exists an infinite number of trees all describing the same 3D solid. However, some trees are optimal regarding the number of used operations, their shape or other attributes, like their suitability for intuitive, human-controlled editing. In this paper, we present a systematic comparison of newly developed and existing tree optimization methods and propose a flexible processing pipeline with a focus on tree editability. The pipeline uses a redundancy removal and decomposition stage for complexity reduction and different (meta-)heuristics for remaining tree optimization. We also introduce a new quantitative measure for CSG tree editability and show how it can be used as a constraint in the optimization process.

*28th International Conference on Computer Graphics, Visualization and Computer Vision (WSCG)*

S. Feld, C. Roch, T. Gabor, M. To, and C. Linnhoff-Popien

Dynamic Time Warping (DTW) is a representative of a distance measure that is able to calculate the distance between two time series. It is often used for the recognition of handwriting or spoken language. The metaheuristic Quantum Annealing (QA) can be used to solve combinatorial optimization problems. Similar to Simulated Annealing it seeks to find a global minimum of a target function. In order to use specialized QA hardware, the problem to be optimized needs to be translated into a Quadratic Unconstrained Binary Optimization (QUBO) problem. With this paper we investigate whether it is possible to transfer the DTW distance measure into a QUBO formulation. The motivation behind is the hope on an accelerated execution once the QA hardware scales up and the aspiration of gaining benefits due to quantum effects that are not given in the classical calculation. In principle, we find that it is possible to transform DTW into a QUBO formulation suitable for executing on QA hardware. Also, the algorithm returns not only the minimum total distance between two sequences, but also the corresponding warping path. However, there are several difficulties that make a manual intervention necessary.

*IEEE 5th International Conference on Computer and Communication Systems (ICCCS 2020)*

Irmengard Sax, Sebastian Feld, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien, Wolfgang Mauerer

Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems. While first implementations of QA have become commercially available, their practical benefits are far from fully explored. To the best of our knowledge, approximation techniques have not yet received substantial attention. In this paper, we explore how problems’ approximate versions of varying degree can be systematically constructed for quantum annealer programs, and how this influences result quality or the handling of larger problem instances on given set of qubits. We illustrate various approximation techniques on both, simulations and real QA hardware, on different seminal problems, and interpret the results to contribute towards a better understanding of the realworld power and limitations of current-state and future quantum computing.

*Published in ,. ACM, New York, NY, USA, 9 pages*

S. Feld, M. Friedrich, and C. Linnhoff-Popien

The compression of geometry data is an important aspect of bandwidth-efficient data transfer for distributed 3d computer vision applications. We propose a quantum-enabled lossy 3d point cloud compression pipeline based on the constructive solid geometry (CSG) model representation. Key parts of the pipeline are mapped to NP-complete problems for which an efficient Ising formulation suitable for the execution on a Quantum Annealer exists. We describe existing Ising formulations for the maximum clique search problem and the smallest exact cover problem, both of which are important building blocks of the proposed compression pipeline. Additionally, we discuss the properties of the overall pipeline regarding result optimality and described Ising formulations.

*IEEE Workshop on Quantum Communications and Information Technology 2018 (IEEE QCIT 2018), 2018, pp. 1-6*

I. Sax, S. Feld, S. Zielinski, T. Gabor, C. Linnhoff-Popien, and W. Mauerer

Many industrially relevant problems can be deterministically solved by computers in principle, but are intractable in practice, as the seminal P/NP dichotomy of complexity theory and Cobham’s thesis testify. For the many NP-complete problems, industry needs to resort to using heuristics or approximation algorithms. For approximation algorithms, there is a more refined classification in complexity classes that goes beyond the simple P/NP dichotomy. As it is well known, approximation classes form a hierarchy, that is, FPTAS PTAS APX NPO. This classification gives a more realistic notion of complexity but—unless unexpected breakthroughs happen for fundamental problems like P = NP or related questions— there is no known efficient algorithm that can solve such problems exactly on a realistic computer. Therefore, new ways of computations are sought. Recently, considerable hope was placed on the possible computational powers of quantum computers and quantum annealing (QA) in particular. However, the precise benefits of such a drastic shift in hardware are still unchartered territory to a good extent. Firstly, the exact relations between classical and quantum complexity classes pose many open questions, and secondly, technical details of formulating and implementing quantum algorithms play a crucial role in real-world applications. Guided by the hierarchy of classical optimisation complexity classes, we discuss how to map problems of each class to a quantum annealer. Those problems are the Minimum Multiprocessor Scheduling (MMS) problem, the Minimum Vertex Cover (MVC) problem and the Maximum Independent Set (MIS) problem. We experimentally investigate if and how the degree of approximability influences implementation and run-time performance. Our experiments indicate a discrepancy between classical approximation complexity and QA behaviour: Problems MIS and MVC, members of APX respectively PTAS, exhibit better solution quality on a QA than MMS, which is in FPTAS, even despite the use of preprocessing the for latter. This leads to the hypothesis that traditional classifications do not immediately extend to the quantum annealing domain, at least when the properties of real-world devices are taken into account. A structural reason, why FPTAS problems do not show good solution quality, might be the use of an inequlity in the problem description of the FPTAS problems. Formulating those inequalities on a quantum hardware (mostly done by formulating a Quadratic Unconstrained Binary optimisation (QUBO) problem in form of a matrix) requires a lot of hardware space which makes finding an optimal solution more difficult. Reducing the density of a QUBO is possible by appropriately pruning QUBO matrices. For the problems considered in our evaluation, we find that the achievable solution quality on a real-world machine is unexpectedly robust against pruning, often up to ratios as high as 50% or more. Since quantum annealers are probabilistic machines by design, the loss in solution quality is only of subordinate relevance, especially considering that the pruning of QUBO matrices allows for solving larger problem instances on hardware of a given capacity. We quantitatively discuss the interplay between these factors.

*1st International Symposium on Applied Artificial Intelligence (ISAAI’19)*

Christoph Roch, Alexander Impertro, Thomy Phan, Thomas Gabor, Sebastian Feld, Claudia Linnhoff-Popien

Hybrid quantum-classical algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. The solution quality of QAOA depends to a high degree on the parameters chosen by the classical optimizer at each iteration. However, the solution landscape of those parameters is highly multi-dimensional and contains many low-quality local optima. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical optimizer to find better parameter more easily and hence results in an improved performance. We empirically demonstrate that this approach can reach a significant better solution quality for the Knapsack Problem.

Accepted for publication, arXiv preprint arXiv:2003.05292 (2020)

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

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*

First International Workshop

S. Feld and C. Linnhoff-Popien

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*

12

Page 1 of 2

Cookie-Zustimmung verwalten

Wir verwenden Cookies, um unsere Website und unseren Service zu optimieren.

Die technische Speicherung oder der Zugang ist unbedingt erforderlich für den rechtmäßigen Zweck, die Nutzung eines bestimmten Dienstes zu ermöglichen, der vom Teilnehmer oder Nutzer ausdrücklich gewünscht wird, oder für den alleinigen Zweck, die Übertragung einer Nachricht über ein elektronisches Kommunikationsnetz durchzuführen.

The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.

Die technische Speicherung oder der Zugriff, der ausschließlich zu statistischen Zwecken erfolgt.
The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.

Die technische Speicherung oder der Zugriff ist erforderlich, um Nutzerprofile zu erstellen, um Werbung zu versenden oder um den Nutzer auf einer Website oder über mehrere Websites hinweg zu ähnlichen Marketingzwecken zu verfolgen.