Seit der Entdeckung von effizienten Quantenalgorithmen für das Faktorisieren von ganzen Zahlen und für die Berechnung von diskreten Logarithmen durch Shor in 1994 wuchs das Interesse an Quantenalgorithmen innerhalb der theoretischen Informatik- und der Physik-Gemeinde. Überraschenderweise ist die Anzahl der Quantenalgorithmen, die bisher entdeckt wurden, vergleichsweise gering, obwohl die Anzahl der Forscher, welche an diesem Gebiet arbeiten, stark angestiegen ist. Die Aufgabe, neue Quantenalgorithmen zu entwerfen, hat sich in der Tat als extrem schwierig herausgestellt. Wir geben einen kurzen Überblick über eine Auswahl von Problemen, für welche effiziente Quantenalgorithmen bekannt sind, und beschreiben kurz die zu Grunde liegenden Ideen. Ein großes Gebiet, bei dem ein Quantenrechner allen klassischen Rechnern überlegen zu sein scheint, sind die verborgenen Untergruppenprobleme. Wir erklären deren Relevanz und geben Motivation für diese abstrakte Problemklasse.
Seit der Entdeckung von effizienten Quantenalgorithmen für das Faktorisieren von ganzen Zahlen und für die Berechnung von diskreten Logarithmen durch Shor in 1994 wuchs das Interesse an Quantenalgorithmen innerhalb der theoretischen Informatik- und der Physik-Gemeinde. Überraschenderweise ist die Anzahl der Quantenalgorithmen, die bisher entdeckt wurden, vergleichsweise gering, obwohl die Anzahl der Forscher, welche an diesem Gebiet arbeiten, stark angestiegen ist. Die Aufgabe, neue Quantenalgorithmen zu entwerfen, hat sich in der Tat als extrem schwierig herausgestellt. Wir geben einen kurzen Überblick über eine Auswahl von Problemen, für welche effiziente Quantenalgorithmen bekannt sind, und beschreiben kurz die zu Grunde liegenden Ideen. Ein großes Gebiet, bei dem ein Quantenrechner allen klassischen Rechnern überlegen zu sein scheint, sind die verborgenen Untergruppenprobleme. Wir erklären deren Relevanz und geben Motivation für diese abstrakte Problemklasse.
Shor’s Algorithmen für die Primfaktorzerlegung und für das Problem des diskreten Logarithmus zählen zu den bahnbrechendsten Entwicklungen im Bereich der Quanteninformatik. Sie lösen Probleme in polynomieller Zeit mithilfe eines Quantencomputers, für welche keine effizienten klassischen Algorithmen bekannt sind. Diese Tatsache unterstreicht den Nutzen von Quantencomputern im Allgemeinen. Heutzutage existieren Bibliotheken und Simulatoren, die es ermöglichen, Quantenalgorithmen zu implementieren und zu analysieren. Eine dieser Bibliotheken, welche außerdem noch die Möglichkeit bietet, die Algorithmen auf echten Maschinen auszuführen, ist Qiskit. Qiskit beinhaltet zurzeit jedoch keine Referenzimplementierung für Shor’s Algorithmus für den diskreten Logarithmus. Für eine Implementierung müssen zusätzlich zur allgemeinen Beschreibung des Algorithmus noch Prozeduren für modulare Arithmetik bereitgestellt werden. Für diese Berechnungen gibt es viele unterschiedliche Algorithmen, wobei manche sehr klassischen Prozeduren ähneln und andere wiederum die Eigenheiten von Quantencomputern ausnutzen. Diese Arbeit liefert eine Referenzimplementierung von Shor’s Algorithmus für das Problem des diskreten Logarithmus. Dabei werden drei verschiedene Versionen der benötigten Routinen für modulare Arithmetik verwendet. Da aktuelle Quantencomputer immer noch relativ wenige Quantenbits, oder Qubits, für die Berechnung zur Verfügung stellen, liegt der Hauptfokus der Arbeit auf Möglichkeiten der Implementierung, die eine minimale Anzahl an Qubits benötigen. Mithilfe der Simulationsfunktionen von Qiskit wird zusätzlich zum Vergleich der Implementierungen bezüglich der asymptotischen Zeitkomplexität ein Vergleich der verschiedenen Versionen anhand der konkreten Anzahl an elementaren Operationen für kleine Probleminstanzen vorgenommen. Außerdem wird diese Analyse um eine genaue Untersuchung der Erfolgswahrscheinlichkeit ergänzt, da diese für die Laufzeit insgesamt ausschlaggebend ist.
Quantenoptimierung hat sich als vielversprechende Anwendung der Quanteninformatik herausgestellt, stößt jedoch in Bezug auf Modellierung, Skalierbarkeit und Implementierung auf erhebliche Einschränkungen. Diese Arbeit behandelt diese Herausforderungen, indem neue Ansätze vorgestellt werden, die die praktische Anwendbarkeit der Quantenoptimierung verbessern. Im Bereich der Modellierung analysieren wir die Formulierung des quadratischen unbeschränkten binären Optimierungsproblems (QUBO). Obwohl weit verbreitet, erfordert QUBO die Umsetzung von Nebenbedingungen durch Strafterme, die einen zusätzlichen Variablenaufwand verursachen und sich insbesondere für Ungleichungen nur schwer verallgemeinern lassen. Wir schlagen maßgeschneiderte Strafterme für spezifische Probleme vor, wie das Ride-Pooling-Problem, und führen das neue Konzept der Anreizterme“ als Alternative zu Straftermen ein. Diese Strategien reduzieren die ” Anzahl der Wechselwirkungen und Variablen, wodurch die Formulierung effizienter wird, ohne die Durchsetzbarkeit der Nebenbedingungen zu verlieren. Zur Bewältigung der Skalierungsprobleme von Quantenalgorithmen entwickeln wir ein Parallelisierungsframework für Variations-Quantenalgorithmen (VQAs). Die Methode zerlegt Schaltkreise in kleinere Teilschaltkreise, die parallel optimiert werden, dabei jedoch weiterhin durch die Zielfunktion des Problems gesteuert bleiben. Im Gegensatz zur klassischen Zerlegung bewahrt dieser Ansatz die Probleminformation und ermöglicht die Optimierung größerer Probleme auf Quantenhardware. Wir haben dies experimentell getestet und gezeigt, dass das Framework einen praktikablen Weg zur skalierbaren Quantenoptimierung bietet. Auf Hardwareebene untersuchen wir das Problem des Minor Embedding in supralei- tenden Quanten-Annealing-Systemen. Das Einbetten verändert die Geometrie und Physik des Problems und führt zu Redundanz durch Qubit-Ketten, die die Berechnung fehleranfälliger machen. Zur Abmilderung dieser Probleme schlagen wir eine neue Einbettungsmethode vor, die von der Lechner–Hauke–Zoller (LHZ)-Architektur inspiriert ist und höherwertige Wechselwirkungen in eine modulare Struktur mit 2- Körper-Kopplungen übersetzt. Die resultierende Einbettung gewährleistet konstante Kettenlängen, kurze Wechselwirkungen und Skalierbarkeit, während sie weitgehend die spektralen Eigenschaften des ursprünglichen Hamiltonians erhält. Obwohl der Qubit-Overhead weiterhin quadratisch bleibt, stellt der Ansatz einen konkreten Schritt in Richtung praktikabler Annealing-Implementierungen dar. Zusammen zeigen diese Beiträge, dass die Quantenoptimierung derzeit noch nicht mit modernen klassischen Algorithmen konkurrieren kann – vor allem aufgrund von Hardwareeinschränkungen, begrenzter Skalierbarkeit und des engen Fokus auf Ising-basierte Formulierungen. Dennoch weisen die vorgeschlagenen Methoden – maßgeschneiderte QUBO-Formulierungen, skalierbare VQA-Parallelisierung und verbesserte Annealer- Einbettungen – neue Wege auf, um diese Barrieren zu überwinden. Der Fortschritt in der Quantenoptimierung wird sowohl von Hardwareverbesserungen als auch von neuen algorithmischen Rahmenwerken abhängen, einschließlich alternativer Modelle, maßgeschneiderter Heuristiken und verteilter Quantenansätze. Diese Ergebnisse tragen zur Grundlage für die Entwicklung von Quantenoptimierungsmethoden bei, die langfristig einen praktischen Vorteil erreichen könnten.
Eine der größten Herausforderungen der angewandten Quanteninformatik ist die Suche nach einem praxisrelevanten Quantenvorteil auf aktueller, rauschbehafteter Quantenhardware. Obwohl es sowohl empirische als auch theoretische Nachweise für bis zu exponentielle Quantenbeschleunigungen gibt, sind die betrachteten Probleme überwiegend akademischer Natur und hängen von spezifischen mathematischen Eigenschaften ab. Dies erschwert die praktische Anwendbarkeit erheblich, da bei realen Anwendungsfällen im Allgemeinen nicht davon ausgegangen werden kann, dass diese komplexe mathematische Voraussetzungen erfüllen. Vor diesem Hintergrund untersucht diese Arbeit, wie etablierte Quantenvorteile auf praxisrelevante Probleme in den Bereichen KI und Optimierung ausgeweitet werden können. Für die zwei praxisrelevanten Optimierungsprobleme des Turbinenauswuchtens und der Community-Erkennung zeigen wir, wie sich Quantenoptimierungsalgorithmen mithilfe neuartiger, speichereffizienter Lösungskodierungen effizient einsetzen lassen. Weiter zeigen wir für die KI-Anwendungen der Betrugserkennung, der Designraumexploration und der Stimmungserkennung, dass Quantenalgorithmen in einigen Fällen bessere Ergebnisse als ihre klassischen Gegenstücke erzielen können. Darüber hinaus stellen wir verschiedene Verbesserungen der praktischen Anwendbarkeit häufig eingesetzter Quantenoptimierungs- und Quanten-Machine-Learning-Algorithmen mit Fokus auf rauschbehaftete Hardware vor. Zunächst präsentieren wir eine polynomielle Problemformulierung für kontinuierliche Optimierungsprobleme hohen Grades, die die vollen Möglichkeiten des weit verbreiteten Quantum Approximate Optimization Algorithm (QAOA) ausschöpft. Anschließend stellen wir ein problemagnostisches Designkonzept für parametrisierte Quantenschaltkreise vor, das besonders parametereffizient ist und dadurch Beschleunigungen beim Parametertraining ermöglicht. Für nicht-lokale Problemstellungen führen wir eine effiziente Trainingsmethode für entsprechend parametrisierte Quantenalgorithmen ein, die Informationen über die Verlustfunktion ausnutzt. Abschließend präsentieren wir eine NISQ-optimierte Implementierung der weitreichend eingesetzten Umwandlung von digitaler in analoge Quantenkodierung, sowie einen sehr effizienten GPU-basierten QAOA Simulator, der großskalige Benchmarks in Bezug auf einen Quantenvorteil ermöglicht. Zusammenfassend treibt die Vielzahl und Tiefe der in dieser Arbeit vorgestellten Ansätze zahlreiche Wege hin zu einem praxisrelevanten Quantenvorteil für Optimierung und Künstliche Intelligenz signifikant voran.
Quantencomputer besitzen das Potenzial, um in naher Zukunft Probleme, die mit herkömmlichen Computern und Supercomputern nicht bewältigbar sind, zu lösen. Bisher ist die Umsetzung dieser Technologie in der Industrie noch in der Anfangsphase, wodurch der Einsatz von Quantencomputern bisher nur für Forschungsprojekte möglich ist. Dennoch ermöglichen es große IT-Unternehmen, interessierten Personen einen indirekten Zugang zu Quantencomputern über deren Services. Da die Technologien und Konzepte, auf denen Quantencomputern basieren, sehr umfangreich und komplex sind, ist es für interessierte Personen, die sich in diese neue Materie vertiefen wollen, oft schwierig, die Hauptkonzepte, die benötigt werden, um Quantencomputern zu verstehen, zu identifizieren und somit ein Grundverständnis von Quantencomputern zu erlangen. Aus diesem Grund besteht der Hauptzweck dieser Arbeit darin, die benötigten Grundkonzepte und Themen auf denen Quantencomputer aufbauen, zu identifizieren und auszuarbeiten. Hierfür werden die Konzepte von bekannten Lehrbüchern im Bereich Quantencomputer herangezogen und systematisch nach deren Wichtigkeit für das Verständnis von Quantencomputern gegliedert, aufgelistet und ausgearbeitet. Für den praktischen Teil der Arbeit werden zwei Quantenbeispiele anhand des zuvor erarbeiteten Wissens beschrieben und erweitert. Die zuvor identifizierten und beschriebenen Grundkonzepte werden anschließend grafisch mittels einer Concept-Map dargestellt, diese bietet einen systematischen Überblick über die einzelnen Konzepte und deren Abhängigkeiten zueinander. Der Vorteil in der Darstellung von Wissen mittels einer Concept-Map besteht darin, dass die Visualisierung der Verbindungen zwischen den einzelnen Konzepten hervorgehoben wird. Zusätzlich wird auf Basis des erarbeiteten Wissens ein Beispiel-Curriculum für eine Lehrveranstaltung, die das Ziel hat, die Grundkonzepte von Quantencomputern zu vermitteln, erstellt. Das Ergebnis dieser Arbeit zeigt, dass die Konzepte, auf denen Quantencomputer aufbauen, in drei Grundkompetenzen unterteilt werden können. Zum einen die Kompetenz der linearen Algebra, in dem die meisten Konzepte und Themen bereits in einem vorangegangenen Studium behandelt wurden. Zum anderen die der Informatik-Konzepte, wobei hier wie bei der linearen Algebra das Verständnis im Bereich der Programmierung angenommen werden kann. Die Kompetenz der Quantenmechanik stützt sich auf die Konzepte, die von Quantencomputern genutzt wird und auf die Kompetenzen und das Wissen der beiden anderen Kompetenzen. Zusammenfassend zeigt diese Arbeit, dass für das reine Verständnis von Quantencomputern und dem Replizieren von bereits erstellten Quantenalgorithmen eine große Anzahl an unterschiedlichen Konzepten benötigt wird. Für die Fähigkeit der Entwicklung von eigenen Quantenalgorithmen reicht das erarbeitet Wissen nicht aus, sondern wird als Grundwissen angesehen.
Die Quantentheorie und die Theorie der quantenmechanischen Messung ermoglichen es, Aussagen uber quantenphysikalische Systeme (Atome, Kerne, Elementarteilchen) zu machen, die an diesen Systemen experimentell nachgepruft werden konnen.Beispiele fur solche Aussagen sind z.B. ,,das Elektron hat den Impuls p" oder ,,der Atomkern hat einen Drehimpuls J".Wie fur die Aussagen aller Wissensgebiete wird man zunachst auch fur diese Aussagen erwarten, daR sie den Regeln der Logik gehorchen.Tatsachlich ist das aber nicht der Fall.Es hat sich namlich gezeigt, daB von den Regeln der Aussagenlogik, die zuerst von den Stoikern aufgestellt wurden, spater im Mittelalter und in der modernen mathematischen Logik wieder aufgegriffen wurden, nur noch ein Teil fur Aussagen uber Quantenphanomene richtig bleibtl).2)3 9, 4).Einige dieser Regeln verlieren ihre Gultigkeit.Derjenige Teil der logischen Regeln, der auch noch in der Quantenphysik gilt, wird gewohnlich als Quantenlogik bezeichnet.Es handelt sich also bei der Quantenlogik nicht um eine ,,neue" Logik, die im Bereich des Atomaren gilt, sondern um eine restriktive Logik, die weniger enthalt als die uns bekannte klassische Aussagenlogik.Der heutige Physiker ist im allgemeinen leicht geneigt zu glauben, daR irgendeine Disziplin, die in der Philosophie vergangener Jahrhunderte fur wahr gehalten wurde, durch die moderne Physik widerlegt sei.Das kommt einerseits daher, daR viele Physiker empiristisch denken, d. h. in diesem Falle, daB sie geneigt sind zu glauben, man konne alle auf die Erfahrung bezogenen Behauptungen auch durch Erfahrungen -z.B. der Atomphysikwiderlegen. Anderseits sprechen fur eine solche Einstellung die schlechten Erfahrungen, die die Physik mit Begriffen und Satzen gemacht hat, die in der philosophischen Tradition uberliefert wurden.Die Verknupfung von Raum und Zeit in der Relativitatstheorie oder das Versagen des Kausalgesetzes in der Quantentheorie gehoren zu diesem Problemkreis.Man wird deshalb versucht sein, auch eine Restriktion der Aussagenlogik in der modernen Atomphysik einfach als eine neue Erfahrung hinzunehmen.Dies ist jedoch nicht ohne weiteres moglich.Die groRte Schwierigkeit, die sich einer solchen Einstellung entgegenstellt, ist die Tatsache, daB die klassische Aussagenlogik wahr ist.Und zwar ist die Aussagenlogik keineswegs in einem empirischen Sinne wahr, sondern sie ist wahr durch das unmittelbare Einleuchten (die Evidenz) ihrer Satze, deren Gultigkeit somit auf keinen bestimmten Gegenstandsbereich eingeschrankt ist.Wie das im Einzelnen 2x1 verstehen ist, sol1 im ersten Teil auseinandergesetzt werden.Nehmen wir zunachst einmal die Evidenz der klassischen Logik als gegeben an, so entsteht die Frage, wie es moglich sein kann, daR fur die Aussagen der Quantenphysik nur eine restriktive Logik, die Quantenlogik, gilt.
Quantencomputer versprechen eine revolutionäre Leistungssteigerung und könnten damit einige aktuelle Paradigmen der Informatik obsolet werden lassen. Diese Technologie ist für Interessierte ohne Vorkenntnisse aus dem Bereich der Quantenphysik jedoch schwer nachzuvollziehen. Die vorliegende Arbeit basiert auf einer Literaturrecherche und wurde verfasst, um die Thematik der Quantencomputer verständlich darzulegen. Zu diesem Zweck wird zuerst eine Beschreibung von relevanten Grundprinzipien der Quantenmechanik gegeben. Neben der Anführung von bestimmten Quantenzahlen und deren Zuständen werden dabei die Konzepte der Superposition und der Verschränkung dieser Zustände erläutert. Danach wird die Funktionsweise eines auf Quantengattern basierenden Computers mathematisch und grafisch nachvollziehbar beschrieben. Operationen, welche durch Transformation von Quantenzuständen ausgeführt werden, und Anwendungen für diese Art von Berechnungen werden vorgestellt. Potenziale und Einschränkungen sind durch das Verständnis der Arbeitsweise eines Quantencomputers eingängig. Der Aufbau eines Quantencomputers, sowie eine Analyse des Fortschritts bei der Realisierung von voll skalierbaren Quantencomputern werden weiters dargelegt. Dabei wird auf die wesentlichen Bestandteile eines Quantenchips näher eingegangen. Für geeignet gehaltene Quantenzustände für die Nutzung als Qubits, sowie Verfahren zur Speicherung und Manipulation von Informationen durch Quantencomputer werden beschrieben. Vor allem die Fehlerrate von Qubits stellt Forscher und Entwickler derzeit noch vor große Herausforderungen. Diese Arbeit gibt deshalb einen Ausblick, welche weiteren Schritte nötig sind, um die Vision von kommerziell einsetzbaren Quantencomputern zu verwirklichen.