• search hit 76 of 84
Back to Result List

Approximate approximation on a quantum annealer

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Irmi Sax, Sebastian Feld, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien, Wolfgang MauererORCiDGND
DOI:https://doi.org/10.1145/3387902.3392635
ISBN:9781450379564
Parent Title (English):Proceedings of the 17th ACM International Conference on Computing Frontiers (CF '20): Catania Sicily Italy 11.05.2020 -13.05.2020
Publisher:Association for Computing Machinery
Place of publication:New York, NY, United States
Editor:Maurizio Palesi
Document Type:conference proceeding (article)
Language:English
Year of first Publication:2020
Release Date:2022/04/11
Tag:Approximation, NP-complete problems; Quantum Annealin; Simplifying Qubos; approximation algorithms analysis; quantum computation
First Page:108
Last Page:117
Institutes:Fakultät Informatik und Mathematik
Fakultät Informatik und Mathematik / Labor für Digitalisierung (LFD)
Begutachtungsstatus:peer-reviewed
research focus:Digitalisierung
Licence (German):Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG