@article{SaxFeldZielinskietal., author = {Sax, Irmi and Feld, Sebastian and Zielinski, Sebastian and Gabor, Thomas and Linnhoff-Popien, Claudia and Mauerer, Wolfgang}, title = {Towards Understanding Approximation Complexity on a Quantum Annealer}, series = {Digitale Welt}, volume = {4}, journal = {Digitale Welt}, number = {1}, publisher = {DIGITALE WELT Academy c/o Ludwig-Maximilians-Universit{\"a}t M{\"u}nchen}, address = {M{\"u}nchen}, doi = {10.1007/s42354-019-0244-1}, pages = {104}, abstract = {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.}, language = {en} } @inproceedings{SaxFeldZielinskietal., author = {Sax, Irmi and Feld, Sebastian and Zielinski, Sebastian and Gabor, Thomas and Linnhoff-Popien, Claudia and Mauerer, Wolfgang}, title = {Approximate approximation on a quantum annealer}, series = {Proceedings of the 17th ACM International Conference on Computing Frontiers (CF '20): Catania Sicily Italy 11.05.2020 -13.05.2020}, booktitle = {Proceedings of the 17th ACM International Conference on Computing Frontiers (CF '20): Catania Sicily Italy 11.05.2020 -13.05.2020}, editor = {Palesi, Maurizio}, publisher = {Association for Computing Machinery}, address = {New York, NY, United States}, isbn = {9781450379564}, doi = {10.1145/3387902.3392635}, pages = {108 -- 117}, abstract = {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.}, language = {en} } @inproceedings{GaborZielinskiFeldetal., author = {Gabor, Thomas and Zielinski, Sebastian and Feld, Sebastian and Roch, Christoph and Seidel, Christian and Neukart, Florian and Galter, Isabella and Mauerer, Wolfgang and Linnhoff-Popien, Claudia}, title = {Assessing Solution Quality of 3SAT on a Quantum Annealing Platform}, series = {Quantum Technology and Optimization Problems : First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings}, volume = {11413}, booktitle = {Quantum Technology and Optimization Problems : First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings}, editor = {Feld, Sebastian and Linnhoff-Popien, Claudia}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-14081-6}, doi = {10.1007/978-3-030-14082-3_3}, pages = {23 -- 35}, language = {en} } @article{BoyceKramerBosiljevacetal., author = {Boyce, Brad L. and Kramer, Sharlotte L. B. and Bosiljevac, T. R. and Corona, Edmundo and Moore, J. A. and Elkhodary, Khalil and Simha, C. Hari Manoj and Williams, Bruce W. and Cerrone, Albert R. and Nonn, Aida and Hochhalter, Jacob D. and Bomarito, Geoffrey F. and Warner, James E. and Carter, Bruce J. and Warner, Derek H. and Ingraffea, Anthony R. and Zhang, T. and Fang, X. and Lua, Jim and Chiaruttini, Vincent and Maziere, Matthieu and Feld-Payet, Sylvia and Yastrebov, Vladislav A. and Besson, Jacques and Chaboche, Jean Louis and Lian, J. and Di, Y. and Wu, Bei and Novokshanov, Denis and Vajragupta, Napat and Kucharczyk, Pawel and Brinnel, Viktoria and Doebereiner, Benedikt and Muenstermann, Sebastian and Neilsen, Michael K. and Dion, Kristin and Karlson, Kyle N. and Foulk, James Wesley and Brown, Arthur A. and Veilleux, Michael G. and Bignell, John L. and Sanborn, Scott E. and Jones, Chris A. and Mattie, Patrick D. and Pack, Keunhwan and Wierzbicki, Tomasz and Chi, Sheng-Wei and Lin, S.-P. and Mahdavi, Ashkan and Predan, Jozef and Zadravec, Janko and Gross, Andrew J. and Ravi-Chandar, KRISHNASWAMY and Xue, Liang}, title = {The second Sandia Fracture Challenge: predictions of ductile failure under quasi-static and moderate-rate dynamic loading}, series = {International journal of fracture}, journal = {International journal of fracture}, number = {198, 1-2}, publisher = {Springer}, doi = {10.1007/s10704-016-0089-7}, pages = {5 -- 100}, abstract = {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.}, language = {en} } @article{FeldRochGaboretal., author = {Feld, Sebastian and Roch, Christoph and Gabor, Thomas and Seidel, Christian and Neukart, Florian and Galter, Isabella and Mauerer, Wolfgang and Linnhoff-Popien, Claudia}, title = {A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer}, series = {Frontiers in ICT}, volume = {6}, journal = {Frontiers in ICT}, publisher = {Frontiers}, doi = {10.3389/fict.2019.00013}, pages = {1 -- 13}, abstract = {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.}, language = {en} } @misc{AppelhansKampmannMottoketal., author = {Appelhans, Marie-Luise and Kampmann, Matthias and Mottok, J{\"u}rgen and Riederer, Michael and Nagl, Klaus and Steffens, Oliver and D{\"u}nnweber, Jan and Wildgruber, Markus and Roth, Julius and Stadler, Timo and Palm, Christoph and Weiß, Martin Georg and Rochholz, Sandra and Bierl, Rudolf and Gschossmann, Andreas and Haug, Sonja and Schmidbauer, Simon and Koch, Anna and Westner, Markus and Bary, Benedikt von and Ellermeier, Andreas and V{\"o}gele, Daniel and Maiwald, Frederik and Hierl, Stefan and Schlamp, Matthias and Ehrlich, Ingo and Siegl, Marco and H{\"u}ntelmann, Sven and Wildfeuer, Matthias and Br{\"u}ckl, Oliver and Sterner, Michael and Hofrichter, Andreas and Eckert, Fabian and Bauer, Franz and Dawoud, Belal and Rabl, Hans-Peter and Gamisch, Bernd and Schmidt, Ottfried and Heberl, Michael and Thema, Martin and Mayer, Ulrike and Eller, Johannes and Sippenauer, Thomas and Adelt, Christian and Haslbeck, Matthias and Vogl, Bettina and Mauerer, Wolfgang and Ramsauer, Ralf and Lohmann, Daniel and Sax, Irmengard and Gabor, Thomas and Feld, Sebastian and Linnhoff-Popien, Claudia and Ławrowski, Robert Damian and Langer, Christoph and Schreiner, Rupert and Sellmair, Josef}, title = {Forschung 2019}, editor = {Baier, Wolfgang}, address = {Regensburg}, organization = {Ostbayerische Technische Hochschule Regensburg}, isbn = {978-3-9818209-7-3}, doi = {10.35096/othr/pub-789}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:898-opus4-7890}, pages = {72}, abstract = {Bericht mit Forschungsprojekten aus verschiedenen Bereichen der OTH Regensburg mit dem Schwerpunktthema "K{\"u}nstliche Intelligenz" und einem Gespr{\"a}ch zur "Medizin der Zukunft"}, subject = {Forschung}, language = {de} } @article{SafiBandicNiedermeieretal., author = {Safi, Hila and Bandic, Medina and Niedermeier, Christoph and Almudever, Carmen G. and Feld, Sebastian and Mauerer, Wolfgang}, title = {Stacking the odds: full-stack quantum system design space exploration}, series = {EPJ Quantum Technology}, volume = {12}, journal = {EPJ Quantum Technology}, publisher = {Springer}, address = {Heidelberg}, doi = {10.1140/epjqt/s40507-025-00413-7}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:898-opus4-85157}, pages = {31}, abstract = {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.}, language = {en} }