TY - CHAP A1 - Gabor, Thomas A1 - Zielinski, Sebastian A1 - Feld, Sebastian A1 - Roch, Christoph A1 - Seidel, Christian A1 - Neukart, Florian A1 - Galter, Isabella A1 - Mauerer, Wolfgang A1 - Linnhoff-Popien, Claudia ED - Feld, Sebastian ED - Linnhoff-Popien, Claudia T1 - Assessing Solution Quality of 3SAT on a Quantum Annealing Platform T2 - Quantum Technology and Optimization Problems : First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings Y1 - 2019 SN - 978-3-030-14081-6 U6 - https://doi.org/10.1007/978-3-030-14082-3_3 VL - 11413 SP - 23 EP - 35 PB - Springer International Publishing CY - Cham ER - TY - JOUR A1 - Sax, Irmi A1 - Feld, Sebastian A1 - Zielinski, Sebastian A1 - Gabor, Thomas A1 - Linnhoff-Popien, Claudia A1 - Mauerer, Wolfgang T1 - Towards Understanding Approximation Complexity on a Quantum Annealer JF - Digitale Welt N2 - 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 \subseteq PTAS \subseteq APX \subseteq 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. Y1 - 2020 U6 - https://doi.org/10.1007/s42354-019-0244-1 VL - 4 IS - 1 SP - 104 PB - DIGITALE WELT Academy c/o Ludwig-Maximilians-Universität München CY - München ER - TY - CHAP A1 - Sax, Irmi A1 - Feld, Sebastian A1 - Zielinski, Sebastian A1 - Gabor, Thomas A1 - Linnhoff-Popien, Claudia A1 - Mauerer, Wolfgang ED - Palesi, Maurizio T1 - Approximate approximation on a quantum annealer T2 - Proceedings of the 17th ACM International Conference on Computing Frontiers (CF '20): Catania Sicily Italy 11.05.2020 -13.05.2020 N2 - 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 real-world power and limitations of current-state and future quantum computing. KW - approximation algorithms analysis KW - Approximation, NP-complete problems KW - Quantum Annealin KW - quantum computation KW - Simplifying Qubos Y1 - 2020 SN - 9781450379564 U6 - https://doi.org/10.1145/3387902.3392635 SP - 108 EP - 117 PB - Association for Computing Machinery CY - New York, NY, United States ER -