<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>3638</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>104</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>4</volume>
    <type>article</type>
    <publisherName>DIGITALE WELT Academy c/o Ludwig-Maximilians-Universität München</publisherName>
    <publisherPlace>München</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Towards Understanding Approximation Complexity on a Quantum Annealer</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Digitale Welt</parentTitle>
    <identifier type="doi">10.1007/s42354-019-0244-1</identifier>
    <enrichment key="opus.import.date">2022-04-28T11:07:17+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <enrichment key="ConferenceStatement">First International Symposium On Applied Artificial Intelligence (ISAAI’19)</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Irmi Sax</author>
    <author>Sebastian Feld</author>
    <author>Sebastian Zielinski</author>
    <author>Thomas Gabor</author>
    <author>Claudia Linnhoff-Popien</author>
    <author>Wolfgang Mauerer</author>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othforschungsschwerpunkt" number="16311">Digitalisierung</collection>
    <collection role="institutes" number="">Labor für Digitalisierung (LFD)</collection>
  </doc>
  <doc>
    <id>3458</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>108</pageFirst>
    <pageLast>117</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Association for Computing Machinery</publisherName>
    <publisherPlace>New York, NY, United States</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximate approximation on a quantum annealer</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Proceedings of the 17th ACM International Conference on Computing Frontiers (CF '20): Catania Sicily Italy 11.05.2020 -13.05.2020</parentTitle>
    <identifier type="isbn">9781450379564</identifier>
    <identifier type="doi">10.1145/3387902.3392635</identifier>
    <enrichment key="opus.import.date">2022-04-10T09:34:41+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Irmi Sax</author>
    <author>Sebastian Feld</author>
    <author>Sebastian Zielinski</author>
    <author>Thomas Gabor</author>
    <author>Claudia Linnhoff-Popien</author>
    <author>Wolfgang Mauerer</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>approximation algorithms analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Approximation, NP-complete problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Quantum Annealin</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>quantum computation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Simplifying Qubos</value>
    </subject>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othforschungsschwerpunkt" number="16311">Digitalisierung</collection>
    <collection role="institutes" number="">Labor für Digitalisierung (LFD)</collection>
  </doc>
  <doc>
    <id>3459</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>23</pageFirst>
    <pageLast>35</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>11413</volume>
    <type>conferenceobject</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace>Cham</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Assessing Solution Quality of 3SAT on a Quantum Annealing Platform</title>
    <parentTitle language="eng">Quantum Technology and Optimization Problems : First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings</parentTitle>
    <identifier type="isbn">978-3-030-14081-6</identifier>
    <identifier type="doi">10.1007/978-3-030-14082-3_3</identifier>
    <enrichment key="opus.import.date">2022-04-10T09:34:41+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="OtherSeries">Lecture Notes in Computer Science ; 11413</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Thomas Gabor</author>
    <author>Sebastian Zielinski</author>
    <author>Sebastian Feld</author>
    <author>Christoph Roch</author>
    <author>Christian Seidel</author>
    <author>Florian Neukart</author>
    <author>Isabella Galter</author>
    <author>Wolfgang Mauerer</author>
    <author>Claudia Linnhoff-Popien</author>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othforschungsschwerpunkt" number="16311">Digitalisierung</collection>
    <collection role="institutes" number="">Labor für Digitalisierung (LFD)</collection>
  </doc>
  <doc>
    <id>2642</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>13</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>6</volume>
    <type>article</type>
    <publisherName>Frontiers</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Frontiers in ICT</parentTitle>
    <identifier type="doi">10.3389/fict.2019.00013</identifier>
    <enrichment key="opus.import.date">2022-01-28T13:58:12+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Sebastian Feld</author>
    <author>Christoph Roch</author>
    <author>Thomas Gabor</author>
    <author>Christian Seidel</author>
    <author>Florian Neukart</author>
    <author>Isabella Galter</author>
    <author>Wolfgang Mauerer</author>
    <author>Claudia Linnhoff-Popien</author>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="oaweg" number="">Gold Open Access- Erstveröffentlichung in einem/als Open-Access-Medium</collection>
    <collection role="othforschungsschwerpunkt" number="16311">Digitalisierung</collection>
    <collection role="institutes" number="">Labor für Digitalisierung (LFD)</collection>
  </doc>
  <doc>
    <id>789</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>72</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>periodicalpart</type>
    <publisherName/>
    <publisherPlace>Regensburg</publisherPlace>
    <creatingCorporation>Ostbayerische Technische Hochschule Regensburg</creatingCorporation>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-06-30</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Forschung 2019</title>
    <abstract language="deu">Bericht mit Forschungsprojekten aus verschiedenen Bereichen der OTH Regensburg mit dem Schwerpunktthema "Künstliche Intelligenz" und einem Gespräch zur "Medizin der Zukunft"</abstract>
    <subTitle language="deu">Thema: Künstliche Intelligenz</subTitle>
    <identifier type="isbn">978-3-9818209-7-3</identifier>
    <identifier type="urn">urn:nbn:de:bvb:898-opus4-7890</identifier>
    <identifier type="doi">10.35096/othr/pub-789</identifier>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Marie-Luise Appelhans</author>
    <author>Matthias Kampmann</author>
    <author>Jürgen Mottok</author>
    <author>Michael Riederer</author>
    <author>Klaus Nagl</author>
    <author>Oliver Steffens</author>
    <author>Jan Dünnweber</author>
    <author>Markus Wildgruber</author>
    <author>Julius Roth</author>
    <author>Timo Stadler</author>
    <author>Christoph Palm</author>
    <author>Martin Georg Weiß</author>
    <author>Sandra Rochholz</author>
    <author>Rudolf Bierl</author>
    <author>Andreas Gschossmann</author>
    <author>Sonja Haug</author>
    <author>Simon Schmidbauer</author>
    <author>Anna Koch</author>
    <author>Markus Westner</author>
    <author>Benedikt von Bary</author>
    <author>Andreas Ellermeier</author>
    <author>Daniel Vögele</author>
    <author>Frederik Maiwald</author>
    <author>Stefan Hierl</author>
    <author>Matthias Schlamp</author>
    <author>Ingo Ehrlich</author>
    <author>Marco Siegl</author>
    <author>Sven Hüntelmann</author>
    <author>Matthias Wildfeuer</author>
    <author>Oliver Brückl</author>
    <author>Michael Sterner</author>
    <author>Andreas Hofrichter</author>
    <author>Fabian Eckert</author>
    <author>Franz Bauer</author>
    <author>Belal Dawoud</author>
    <author>Hans-Peter Rabl</author>
    <author>Bernd Gamisch</author>
    <author>Ottfried Schmidt</author>
    <author>Michael Heberl</author>
    <author>Martin Thema</author>
    <author>Ulrike Mayer</author>
    <author>Johannes Eller</author>
    <author>Thomas Sippenauer</author>
    <author>Christian Adelt</author>
    <author>Matthias Haslbeck</author>
    <author>Bettina Vogl</author>
    <author>Wolfgang Mauerer</author>
    <author>Ralf Ramsauer</author>
    <author>Daniel Lohmann</author>
    <author>Irmengard Sax</author>
    <author>Thomas Gabor</author>
    <author>Sebastian Feld</author>
    <author>Claudia Linnhoff-Popien</author>
    <author>Robert Damian Ławrowski</author>
    <author>Christoph Langer</author>
    <author>Rupert Schreiner</author>
    <author>Josef Sellmair</author>
    <series>
      <title>Forschungsberichte der OTH Regensburg</title>
      <number>2019</number>
    </series>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Forschung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Forschungsbericht</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Künstliche Intelligenz</value>
    </subject>
    <collection role="ddc" number="0">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="HL">Hochschulleitung/Hochschulverwaltung</collection>
    <collection role="othpublikationsherkunft" number="">Von der OTH Regensburg herausgegeben</collection>
    <collection role="institutes" number="IAFW">Zentrum für Forschung und Transfer (ZFT ab 2024; vorher: IAFW)</collection>
    <collection role="persons" number="sternerfenes">Sterner, Michael (Prof. Dr.) - FENES / Forschungsgruppe Energiespeicher</collection>
    <collection role="persons" number="bruecklfenes">Brückl, Oliver (Prof. Dr.) - FENES / Forschungsgruppe Energienetze</collection>
    <thesisPublisher>Ostbayerische Technische Hochschule Regensburg</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-oth-regensburg/files/789/Forschungsbericht_2019.pdf</file>
  </doc>
</export-example>
