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 - 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 - Boyce, Brad L. A1 - Kramer, Sharlotte L. B. A1 - Bosiljevac, T. R. A1 - Corona, Edmundo A1 - Moore, J. A. A1 - Elkhodary, Khalil A1 - Simha, C. Hari Manoj A1 - Williams, Bruce W. A1 - Cerrone, Albert R. A1 - Nonn, Aida A1 - Hochhalter, Jacob D. A1 - Bomarito, Geoffrey F. A1 - Warner, James E. A1 - Carter, Bruce J. A1 - Warner, Derek H. A1 - Ingraffea, Anthony R. A1 - Zhang, T. A1 - Fang, X. A1 - Lua, Jim A1 - Chiaruttini, Vincent A1 - Maziere, Matthieu A1 - Feld-Payet, Sylvia A1 - Yastrebov, Vladislav A. A1 - Besson, Jacques A1 - Chaboche, Jean Louis A1 - Lian, J. A1 - Di, Y. A1 - Wu, Bei A1 - Novokshanov, Denis A1 - Vajragupta, Napat A1 - Kucharczyk, Pawel A1 - Brinnel, Viktoria A1 - Doebereiner, Benedikt A1 - Muenstermann, Sebastian A1 - Neilsen, Michael K. A1 - Dion, Kristin A1 - Karlson, Kyle N. A1 - Foulk, James Wesley A1 - Brown, Arthur A. A1 - Veilleux, Michael G. A1 - Bignell, John L. A1 - Sanborn, Scott E. A1 - Jones, Chris A. A1 - Mattie, Patrick D. A1 - Pack, Keunhwan A1 - Wierzbicki, Tomasz A1 - Chi, Sheng-Wei A1 - Lin, S.-P. A1 - Mahdavi, Ashkan A1 - Predan, Jozef A1 - Zadravec, Janko A1 - Gross, Andrew J. A1 - Ravi-Chandar, KRISHNASWAMY A1 - Xue, Liang T1 - The second Sandia Fracture Challenge: predictions of ductile failure under quasi-static and moderate-rate dynamic loading JF - International journal of fracture N2 - Ductile failure of structural metals is relevant to a wide range of engineering scenarios. Computational methods are employed to anticipate the critical conditions of failure, yet they sometimes provide inaccurate and misleading predictions. Challenge scenarios, such as the one presented in the current work, provide an opportunity to assess the blind, quantitative predictive ability of simulation methods against a previously unseen failure problem. Rather than evaluate the predictions of a single simulation approach, the Sandia Fracture Challenge relies on numerous volunteer teams with expertise in computational mechanics to apply a broad range of computational methods, numerical algorithms, and constitutive models to the challenge. This exercise is intended to evaluate the state of health of technologies available for failure prediction. In the first Sandia Fracture Challenge, a wide range of issues were raised in ductile failure modeling, including a lack of consistency in failure models, the importance of shear calibration data, and difficulties in quantifying the uncertainty of prediction [see Boyce et al. (Int J Fract 186:5-68, 2014) for details of these observations]. This second Sandia Fracture Challenge investigated the ductile rupture of a Ti-6Al-4V sheet under both quasi-static and modest-rate dynamic loading (failure in 0.1 s). Like the previous challenge, the sheet had an unusual arrangement of notches and holes that added geometric complexity and fostered a competition between tensile- and shear-dominated failure modes. The teams were asked to predict the fracture path and quantitative far-field failure metrics such as the peak force and displacement to cause crack initiation. Fourteen teams contributed blind predictions, and the experimental outcomes were quantified in three independent test labs. Additional shortcomings were revealed in this second challenge such as inconsistency in the application of appropriate boundary conditions, need for a thermomechanical treatment of the heat generation in the dynamic loading condition, and further difficulties in model calibration based on limited real-world engineering data. As with the prior challenge, this work not only documents the 'state-of-the-art' in computational failure prediction of ductile tearing scenarios, but also provides a detailed dataset for non-blind assessment of alternative methods. KW - Alloy KW - BEHAVIOR KW - CRACK-PROPAGATION KW - DAMAGE KW - Deformation KW - Fracture KW - HIGH-STRAIN-RATE KW - KERNEL PARTICLE METHODS KW - Metal KW - MODEL KW - Modeling KW - Plasticity KW - POLYCRYSTALLINE AL 6061-T6 KW - PREDICTION KW - ROOM-TEMPERATURE KW - Rupture KW - simulation KW - STRENGTH STEEL SHEETS KW - Tearing Y1 - 2016 U6 - https://doi.org/10.1007/s10704-016-0089-7 IS - 198, 1-2 SP - 5 EP - 100 PB - Springer ER - TY - JOUR A1 - Feld, Sebastian A1 - Roch, Christoph A1 - Gabor, Thomas A1 - Seidel, Christian A1 - Neukart, Florian A1 - Galter, Isabella A1 - Mauerer, Wolfgang A1 - Linnhoff-Popien, Claudia T1 - A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer JF - Frontiers in ICT N2 - he 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. Y1 - 2019 U6 - https://doi.org/10.3389/fict.2019.00013 VL - 6 SP - 1 EP - 13 PB - Frontiers ER - TY - JOUR A1 - Appelhans, Marie-Luise A1 - Kampmann, Matthias A1 - Mottok, Jürgen A1 - Riederer, Michael A1 - Nagl, Klaus A1 - Steffens, Oliver A1 - Dünnweber, Jan A1 - Wildgruber, Markus A1 - Roth, Julius A1 - Stadler, Timo A1 - Palm, Christoph A1 - Weiß, Martin Georg A1 - Rochholz, Sandra A1 - Bierl, Rudolf A1 - Gschossmann, Andreas A1 - Haug, Sonja A1 - Schmidbauer, Simon A1 - Koch, Anna A1 - Westner, Markus A1 - Bary, Benedikt von A1 - Ellermeier, Andreas A1 - Vögele, Daniel A1 - Maiwald, Frederik A1 - Hierl, Stefan A1 - Schlamp, Matthias A1 - Ehrlich, Ingo A1 - Siegl, Marco A1 - Hüntelmann, Sven A1 - Wildfeuer, Matthias A1 - Brückl, Oliver A1 - Sterner, Michael A1 - Hofrichter, Andreas A1 - Eckert, Fabian A1 - Bauer, Franz A1 - Dawoud, Belal A1 - Rabl, Hans-Peter A1 - Gamisch, Bernd A1 - Schmidt, Ottfried A1 - Heberl, Michael A1 - Thema, Martin A1 - Mayer, Ulrike A1 - Eller, Johannes A1 - Sippenauer, Thomas A1 - Adelt, Christian A1 - Haslbeck, Matthias A1 - Vogl, Bettina A1 - Mauerer, Wolfgang A1 - Ramsauer, Ralf A1 - Lohmann, Daniel A1 - Sax, Irmengard A1 - Gabor, Thomas A1 - Feld, Sebastian A1 - Linnhoff-Popien, Claudia A1 - Ławrowski, Robert Damian A1 - Langer, Christoph A1 - Schreiner, Rupert A1 - Sellmair, Josef ED - Baier, Wolfgang T1 - Forschung 2019 BT - Thema: Künstliche Intelligenz N2 - Bericht mit Forschungsprojekten aus verschiedenen Bereichen der OTH Regensburg mit dem Schwerpunktthema "Künstliche Intelligenz" und einem Gespräch zur "Medizin der Zukunft" T3 - Forschungsberichte der OTH Regensburg - 2019 KW - Forschung KW - Forschungsbericht KW - Künstliche Intelligenz Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-7890 SN - 978-3-9818209-7-3 CY - Regensburg ER - TY - JOUR A1 - Safi, Hila A1 - Bandic, Medina A1 - Niedermeier, Christoph A1 - Almudever, Carmen G. A1 - Feld, Sebastian A1 - Mauerer, Wolfgang T1 - Stacking the odds: full-stack quantum system design space exploration JF - EPJ Quantum Technology N2 - Design space exploration (DSE) plays an important role in optimising quantum circuit execution by systematically evaluating different configurations of compilation strategies and hardware settings. In this paper, we conduct a comprehensive investigation into the impact of various layout methods, qubit routing techniques, and optimisation levels, as well as device-specific properties such as different variants and strengths of noise and imperfections, the topological structure of qubits, connectivity densities, and back-end sizes. By spanning through these dimensions, we aim to understand the interplay between compilation choices and hardware characteristics. A key question driving our exploration is whether the optimal selection of device parameters, mapping techniques, comprising of initial layout strategies and routing heuristics can mitigate device induced errors beyond standard error mitigation approaches. Our results show that carefully selecting software strategies (e.g., mapping and routing algorithms) and tailoring hardware characteristics (such as minimising noise and leveraging topology and connectivity density) significantly improve the fidelity of circuit execution outcomes, and thus the expected correctness or success probability of the computational result. We provide estimates based on key metrics such as circuit depth, gate count and expected fidelity. Our results highlight the importance of hardware–software co-design, particularly as quantum systems scale to larger dimensions, and along the way towards fully error corrected quantum systems: Our study is based on computationally noisy simulations, but considers various implementations of quantum error correction (QEC) using the same approach as for other algorithms. The observed sensitivity of circuit fidelity to noise and connectivity suggests that co-design principles will be equally critical when integrating QEC in future systems. Our exploration provides practical guidelines for co-optimising physical mapping, qubit routing, and hardware configurations in realistic quantum computing scenarios. Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-85157 N1 - Corresponding author der OTH Regensburg: Hila Safi VL - 12 PB - Springer CY - Heidelberg ER -