EITC/QI/QIF Quanteninformationsgrundlagen

Die Geschichte der Quanteninformation begann um die Jahrhundertwende, als die klassische Physik zur Quantenphysik revolutioniert wurde. Die Theorien der klassischen Physik sagten Absurditäten wie die ultraviolette Katastrophe oder die Spirale von Elektronen in den Kern voraus. Zunächst wurden diese Probleme beiseite gewischt, indem Ad-hoc-Hypothesen zur klassischen Physik hinzugefügt wurden. Bald wurde klar, dass eine neue Theorie geschaffen werden musste, um diese Absurditäten zu verstehen, und die Theorie der Quantenmechanik war geboren.

Die Quantenmechanik wurde von Schrödinger mit der Wellenmechanik und von Heisenberg mit der Matrixmechanik formuliert. Die Gleichwertigkeit dieser Methoden wurde später bewiesen. Ihre Formulierungen beschrieben die Dynamik mikroskopischer Systeme, hatten jedoch einige unbefriedigende Aspekte bei der Beschreibung von Messprozessen. Von Neumann formulierte die Quantentheorie mithilfe der Operatoralgebra so, dass sie sowohl die Messung als auch die Dynamik beschrieb. Diese Studien betonten eher die philosophischen Aspekte der Messung als einen quantitativen Ansatz zur Extraktion von Informationen durch Messungen.

In den 1960er Jahren schlugen Stratonovich, Helstrom und Gordon eine Formulierung der optischen Kommunikation unter Verwendung der Quantenmechanik vor. Dies war das erste historische Erscheinen der Quanteninformationstheorie. Sie untersuchten hauptsächlich Fehlerwahrscheinlichkeiten und Kanalkapazitäten für die Kommunikation. Später erreichte Holevo eine obere Grenze der Kommunikationsgeschwindigkeit bei der Übertragung einer klassischen Nachricht über einen Quantenkanal.

In den 1970er Jahren wurden Techniken zur Manipulation von Einzelatom-Quantenzuständen entwickelt, wie die Atomfalle und das Rastertunnelmikroskop, die es ermöglichen, einzelne Atome zu isolieren und in Arrays anzuordnen. Vor diesen Entwicklungen war eine genaue Kontrolle über einzelne Quantensysteme nicht möglich, und Experimente nutzten eine gröbere, gleichzeitige Kontrolle über eine große Anzahl von Quantensystemen. Die Entwicklung praktikabler Single-State-Manipulationstechniken führte zu einem verstärkten Interesse im Bereich der Quanteninformation und -berechnung.

In den 1980er Jahren kam das Interesse auf, ob es möglich sein könnte, Einsteins Relativitätstheorie mithilfe von Quanteneffekten zu widerlegen. Wenn es möglich wäre, einen unbekannten Quantenzustand zu klonen, wäre es möglich, verschränkte Quantenzustände zu verwenden, um Informationen schneller als Lichtgeschwindigkeit zu übertragen, was Einsteins Theorie widerlegt. Das No-Cloning-Theorem zeigte jedoch, dass ein solches Klonen unmöglich ist. Das Theorem war eines der frühesten Ergebnisse der Quanteninformationstheorie.

Entwicklung aus der Kryptographie

Trotz aller Aufregung und des Interesses, isolierte Quantensysteme zu studieren und einen Weg zu finden, die Relativitätstheorie zu umgehen, stagnierte die Forschung auf dem Gebiet der Quanteninformationstheorie in den 1980er Jahren. Ungefähr zur gleichen Zeit begann jedoch ein anderer Weg, sich mit Quanteninformationen und Berechnungen zu beschäftigen: Kryptographie. Im Allgemeinen ist Kryptographie das Problem der Kommunikation oder Berechnung, an dem zwei oder mehr Parteien beteiligt sind, die einander möglicherweise nicht vertrauen.

Bennett und Brassard haben einen Kommunikationskanal entwickelt, bei dem es unmöglich ist, unbemerkt abzuhören, eine Möglichkeit, heimlich über große Entfernungen mit dem quantenkryptografischen Protokoll BB84 zu kommunizieren. Die Schlüsselidee war die Verwendung des Grundprinzips der Quantenmechanik, dass Beobachtung das Beobachtete stört, und die Einführung eines Lauschers in eine sichere Kommunikationsleitung wird die beiden Parteien, die versuchen zu kommunizieren, sofort über die Anwesenheit des Lauschers informieren.

Entwicklung aus Informatik und Mathematik

Mit dem Aufkommen von Alan Turings revolutionären Ideen eines programmierbaren Computers oder einer Turing-Maschine zeigte er, dass jede reale Berechnung in eine äquivalente Berechnung mit einer Turing-Maschine übersetzt werden kann. Dies ist als Church-Turing-These bekannt.

Schon bald wurden die ersten Computer hergestellt und die Computerhardware wuchs so schnell, dass das Wachstum durch Erfahrung in der Produktion in einer empirischen Beziehung namens Moores Gesetz kodifiziert wurde. Dieses „Gesetz“ ist ein projektiver Trend, der besagt, dass sich die Anzahl der Transistoren in einem integrierten Schaltkreis alle zwei Jahre verdoppelt. Als Transistoren immer kleiner wurden, um mehr Leistung pro Oberfläche zu packen, traten in der Elektronik Quanteneffekte auf, die zu unbeabsichtigten Interferenzen führten. Dies führte zum Aufkommen des Quantencomputings, das die Quantenmechanik nutzte, um Algorithmen zu entwickeln.

An diesem Punkt zeigten Quantencomputer das Versprechen, bei bestimmten spezifischen Problemen viel schneller zu sein als klassische Computer. Ein solches Beispielproblem wurde von David Deutsch und Richard Jozsa entwickelt, bekannt als Deutsch-Jozsa-Algorithmus. Dieses Problem hatte jedoch wenig bis keine praktische Anwendung. 1994 stellte Peter Shor ein sehr wichtiges und praktisches Problem, nämlich die Primfaktoren einer ganzen Zahl zu finden. Das Diskrete-Logarithmus-Problem, wie es genannt wurde, konnte auf einem Quantencomputer effizient gelöst werden, aber nicht auf einem klassischen Computer, was zeigt, dass Quantencomputer leistungsfähiger sind als Turing-Maschinen.

Entwicklung aus der Informationstheorie

Etwa zu der Zeit machte die Informatik eine Revolution, ebenso die Informationstheorie und die Kommunikation durch Claude Shannon. Shannon hat zwei grundlegende Theoreme der Informationstheorie entwickelt: das Noiseless Channel Coding Theorem und das Noisy Channel Coding Theorem. Er zeigte auch, dass Fehlerkorrekturcodes verwendet werden können, um die gesendeten Informationen zu schützen.

Auch die Quanteninformationstheorie verfolgte einen ähnlichen Weg, Ben Schumacher machte 1995 mit Hilfe des Qubits ein Analogon zu Shannons geräuschlosem Codierungstheorem. Außerdem wurde eine Theorie der Fehlerkorrektur entwickelt, die es Quantencomputern ermöglicht, unabhängig von Rauschen effiziente Berechnungen durchzuführen und eine zuverlässige Kommunikation über verrauschte Quantenkanäle zu ermöglichen.

Qubits und Informationstheorie

Quanteninformationen unterscheiden sich in vielerlei auffälligen und ungewohnten Weisen stark von klassischen Informationen, die durch das Bit verkörpert werden. Während die grundlegende Einheit der klassischen Information das Bit ist, ist die grundlegendste Einheit der Quanteninformation das Qubit. Klassische Informationen werden mit der Shannon-Entropie gemessen, während das quantenmechanische Analogon die Von-Neumann-Entropie ist. Ein statistisches Ensemble quantenmechanischer Systeme wird durch die Dichtematrix charakterisiert. Viele Entropiemaße der klassischen Informationstheorie lassen sich auch auf den Quantenfall verallgemeinern, wie die Holevo-Entropie und die bedingte Quantenentropie.

Im Gegensatz zu klassischen digitalen Zuständen (die diskret sind) hat ein Qubit einen stetigen Wert, der durch eine Richtung auf der Bloch-Kugel beschrieben werden kann. Trotz dieser kontinuierlichen Bewertung ist ein Qubit die kleinstmögliche Einheit der Quanteninformation, und obwohl der Qubit-Zustand kontinuierlich bewertet ist, ist es unmöglich, den Wert genau zu messen. Fünf berühmte Theoreme beschreiben die Grenzen der Manipulation von Quanteninformationen:

• Theorem ohne Teleportation, der besagt, dass ein Qubit nicht (ganz) in klassische Bits umgewandelt werden kann; das heißt, es kann nicht vollständig „gelesen“ werden.
• No-Cloning-Theorem, das verhindert, dass ein beliebiges Qubit kopiert wird,
• No-Deleting-Theorem, das verhindert, dass ein beliebiges Qubit gelöscht wird,
• No-Broadcasting-Theorem, das verhindert, dass ein beliebiges Qubit an mehrere Empfänger geliefert wird, obwohl es von Ort zu Ort transportiert werden kann (zB über Quantenteleportation),
• No-Hiding-Theorem, das die Erhaltung von Quanteninformation demonstriert,Diese Theoreme beweisen, dass Quanteninformation im Universum erhalten bleibt und sie eröffnen einzigartige Möglichkeiten in der Quanteninformationsverarbeitung.

Quanteninformationsverarbeitung

Der Zustand eines Qubits enthält alle seine Informationen. Dieser Zustand wird häufig als Vektor auf der Bloch-Kugel ausgedrückt. Dieser Zustand kann durch Anwendung linearer Transformationen oder Quantengatter geändert werden. Diese einheitlichen Transformationen werden als Rotationen auf der Bloch-Kugel bezeichnet. Während klassische Gatter den bekannten Operationen der Booleschen Logik entsprechen, sind Quantengatter physikalische unitäre Operatoren.

Aufgrund der Flüchtigkeit von Quantensystemen und der Unmöglichkeit, Zustände zu kopieren, ist die Speicherung von Quanteninformationen viel schwieriger als die Speicherung klassischer Informationen. Trotzdem können mit der Quantenfehlerkorrektur Quanteninformationen im Prinzip immer noch zuverlässig gespeichert werden. Die Existenz von Quantenfehlerkorrekturcodes hat auch zur Möglichkeit einer fehlertoleranten Quantenberechnung geführt.
Klassische Bits können mithilfe von Quantengattern in Konfigurationen von Qubits kodiert und anschließend daraus wiedergewonnen werden. Ein einzelnes Qubit allein kann nicht mehr als ein Bit zugänglicher klassischer Informationen über seine Herstellung vermitteln. Dies ist der Satz von Holevo. Bei der superdichten Codierung kann ein Sender jedoch, indem er auf eines von zwei verschränkten Qubits einwirkt, zwei Bits zugänglicher Informationen über ihren gemeinsamen Zustand an einen Empfänger übermitteln.
Quanteninformationen können in einem Quantenkanal analog zum Konzept eines klassischen Kommunikationskanals bewegt werden. Quantennachrichten haben eine endliche Größe, gemessen in Qubits; Quantenkanäle haben eine endliche Kanalkapazität, gemessen in Qubits pro Sekunde.
Quanteninformation und Veränderungen der Quanteninformation können quantitativ gemessen werden, indem man ein Analogon der Shannon-Entropie, die sogenannte von-Neumann-Entropie, verwendet.
In einigen Fällen können Quantenalgorithmen verwendet werden, um Berechnungen schneller durchzuführen als mit jedem bekannten klassischen Algorithmus. Das bekannteste Beispiel dafür ist der Shor-Algorithmus, der Zahlen in polynomieller Zeit faktorisieren kann, im Vergleich zu den besten klassischen Algorithmen, die subexponentielle Zeit benötigen. Da die Faktorisierung ein wichtiger Teil der Sicherheit der RSA-Verschlüsselung ist, hat Shors Algorithmus das neue Feld der Post-Quanten-Kryptographie eröffnet, das versucht, Verschlüsselungsschemata zu finden, die auch dann sicher bleiben, wenn Quantencomputer im Einsatz sind. Andere Beispiele für Algorithmen, die die Quantenüberlegenheit demonstrieren, umfassen den Suchalgorithmus von Grover, bei dem der Quantenalgorithmus eine quadratische Beschleunigung gegenüber dem bestmöglichen klassischen Algorithmus bietet. Die Komplexitätsklasse von Problemen, die von einem Quantencomputer effizient lösbar sind, wird als BQP bezeichnet.
Die Quantenschlüsselverteilung (QKD) ermöglicht eine bedingungslos sichere Übertragung klassischer Informationen, im Gegensatz zur klassischen Verschlüsselung, die prinzipiell immer, wenn nicht praktisch gebrochen werden kann. Beachten Sie, dass bestimmte subtile Punkte in Bezug auf die Sicherheit von QKD immer noch heiß diskutiert werden.
Das Studium aller oben genannten Themen und Unterschiede umfasst die Quanteninformationstheorie.

Bezug zur Quantenmechanik

Quantenmechanik ist die Untersuchung, wie sich mikroskopische physikalische Systeme in der Natur dynamisch verändern. Auf dem Gebiet der Quanteninformationstheorie werden die untersuchten Quantensysteme von jedem realen Gegenstück abstrahiert. Ein Qubit könnte zum Beispiel physikalisch ein Photon in einem linearen optischen Quantencomputer sein, ein Ion in einem Quantencomputer mit gefangenen Ionen oder es könnte eine große Ansammlung von Atomen wie in einem supraleitenden Quantencomputer sein. Unabhängig von der physikalischen Implementierung gelten die Grenzen und Eigenschaften von Qubits, die von der Quanteninformationstheorie impliziert werden, da alle diese Systeme mathematisch durch dieselbe Vorrichtung von Dichtematrizen über den komplexen Zahlen beschrieben werden. Ein weiterer wichtiger Unterschied zur Quantenmechanik besteht darin, dass, während die Quantenmechanik oft unendlichdimensionale Systeme wie einen harmonischen Oszillator untersucht, sich die Quanteninformationstheorie sowohl auf kontinuierlich veränderliche Systeme als auch auf endlichdimensionale Systeme bezieht.

Quantenberechnung

Quantencomputing ist eine Art von Berechnung, die die kollektiven Eigenschaften von Quantenzuständen wie Superposition, Interferenz und Verschränkung nutzt, um Berechnungen durchzuführen. Die Geräte, die Quantenberechnungen durchführen, werden als Quantencomputer bezeichnet.: I-5 Obwohl aktuelle Quantencomputer zu klein sind, um herkömmliche (klassische) Computer für praktische Anwendungen zu übertreffen, wird angenommen, dass sie in der Lage sind, bestimmte Rechenprobleme zu lösen, wie z (der RSA-Verschlüsselung zugrunde liegt), wesentlich schneller als klassische Computer. Das Studium des Quantencomputings ist ein Teilgebiet der Quanteninformationswissenschaft.

Quantencomputing begann 1980, als der Physiker Paul Benioff ein quantenmechanisches Modell der Turing-Maschine vorschlug. Richard Feynman und Yuri Manin schlugen später vor, dass ein Quantencomputer das Potenzial habe, Dinge zu simulieren, die ein klassischer Computer nicht tun könnte. 1994 entwickelte Peter Shor einen Quantenalgorithmus zum Faktorisieren von ganzen Zahlen mit dem Potenzial, RSA-verschlüsselte Kommunikation zu entschlüsseln. 1998 entwickelten Isaac Chuang, Neil Gershenfeld und Mark Kubinec den ersten Zwei-Qubit-Quantencomputer, der Berechnungen durchführen konnte. Trotz anhaltender experimenteller Fortschritte seit Ende der 1990er Jahre glauben die meisten Forscher, dass „fehlertolerantes Quantencomputing noch ein ziemlich ferner Traum ist“. In den letzten Jahren sind die Investitionen in die Quantencomputing-Forschung im öffentlichen und privaten Sektor gestiegen. Am 23. Oktober 2019 behauptete Google AI in Zusammenarbeit mit der US-amerikanischen National Aeronautics and Space Administration (NASA), eine Quantenberechnung durchgeführt zu haben, die auf keinem klassischen Computer durchführbar war, aber ob diese Behauptung gültig war oder noch gültig ist, ist ein Thema von aktive Forschung.

Es gibt verschiedene Arten von Quantencomputern (auch bekannt als Quantencomputersysteme), einschließlich des Quantenschaltungsmodells, der Quanten-Turing-Maschine, des adiabatischen Quantencomputers, des Einweg-Quantencomputers und verschiedener zellulärer Quantenautomaten. Das am weitesten verbreitete Modell ist der Quantenschaltkreis, der auf dem Quantenbit oder „Qubit“ basiert, das dem Bit in der klassischen Berechnung ähnlich ist. Ein Qubit kann sich in einem 1- oder 0-Quantenzustand oder in einer Überlagerung der 1- und 0-Zustände befinden. Bei der Messung ist es jedoch immer 0 oder 1; die Wahrscheinlichkeit eines der beiden Ergebnisse hängt vom Quantenzustand des Qubits unmittelbar vor der Messung ab.

Die Bemühungen zum Bau eines physikalischen Quantencomputers konzentrieren sich auf Technologien wie Transmons, Ionenfallen und topologische Quantencomputer, die darauf abzielen, qualitativ hochwertige Qubits zu erzeugen.: 2–13 Diese Qubits können je nach Rechenmodell des vollständigen Quantencomputers unterschiedlich gestaltet sein. ob Quantenlogikgatter, Quantenausheilung oder adiabatische Quantenberechnung. Derzeit gibt es eine Reihe erheblicher Hindernisse für den Bau nützlicher Quantencomputer. Es ist besonders schwierig, die Quantenzustände von Qubits aufrechtzuerhalten, da sie unter Quantendekohärenz und Zustandstreue leiden. Quantencomputer benötigen daher eine Fehlerkorrektur.

Jedes Rechenproblem, das von einem klassischen Computer gelöst werden kann, kann auch von einem Quantencomputer gelöst werden. Umgekehrt kann jedes Problem, das von einem Quantencomputer gelöst werden kann, auch von einem klassischen Computer gelöst werden, zumindest im Prinzip mit genügend Zeit. Mit anderen Worten, Quantencomputer gehorchen der Church-Turing-These. Dies bedeutet, dass Quantencomputer zwar keine zusätzlichen Vorteile gegenüber klassischen Computern in Bezug auf die Berechenbarkeit bieten, Quantenalgorithmen für bestimmte Probleme jedoch deutlich geringere Zeitkomplexitäten aufweisen als entsprechende bekannte klassische Algorithmen. Insbesondere wird angenommen, dass Quantencomputer in der Lage sind, bestimmte Probleme schnell zu lösen, die kein klassischer Computer in machbarer Zeit lösen könnte – eine Leistung, die als „Quantenüberlegenheit“ bekannt ist. Die Untersuchung der Rechenkomplexität von Problemen in Bezug auf Quantencomputer ist als Quantenkomplexitätstheorie bekannt.

Das vorherrschende Modell der Quantenberechnung beschreibt die Berechnung in Form eines Netzwerks von Quantenlogikgattern. Dieses Modell kann man sich als abstrakte linear-algebraische Verallgemeinerung einer klassischen Schaltung vorstellen. Da dieses Schaltungsmodell der Quantenmechanik gehorcht, wird angenommen, dass ein Quantencomputer, der diese Schaltungen effizient betreiben kann, physikalisch realisierbar ist.

Ein aus n Informationsbits bestehender Speicher hat 2^n mögliche Zustände. Ein Vektor, der alle Speicherzustände repräsentiert, hat somit 2^n Einträge (einen für jeden Zustand). Dieser Vektor wird als Wahrscheinlichkeitsvektor angesehen und repräsentiert die Tatsache, dass sich der Speicher in einem bestimmten Zustand befindet.

In der klassischen Ansicht hätte ein Eintrag den Wert 1 (dh eine 100-prozentige Wahrscheinlichkeit, sich in diesem Zustand zu befinden) und alle anderen Einträge wären null.

In der Quantenmechanik können Wahrscheinlichkeitsvektoren auf Dichteoperatoren verallgemeinert werden. Der Quantenzustandsvektorformalismus wird normalerweise zuerst eingeführt, weil er konzeptionell einfacher ist und weil er anstelle des Dichtematrixformalismus für reine Zustände verwendet werden kann, bei denen das gesamte Quantensystem bekannt ist.

eine Quantenberechnung kann als ein Netzwerk von quantenlogischen Gattern und Messungen beschrieben werden. Jede Messung kann jedoch bis zum Ende der Quantenberechnung verschoben werden, obwohl diese Verschiebung mit Rechenkosten verbunden sein kann, sodass die meisten Quantenschaltungen ein Netzwerk darstellen, das nur aus Quantenlogikgattern und keinen Messungen besteht.

Jede Quantenberechnung (die im obigen Formalismus jede unitäre Matrix über n Qubits ist) kann als ein Netzwerk von Quantenlogikgattern aus einer ziemlich kleinen Familie von Gattern dargestellt werden. Eine Auswahl an Gate-Familien, die diese Konstruktion ermöglicht, wird als universeller Gate-Satz bezeichnet, da ein Computer, der solche Schaltungen ausführen kann, ein universeller Quantencomputer ist. Ein gemeinsamer Satz umfasst alle Single-Qubit-Gates sowie das CNOT-Gate von oben. Dies bedeutet, dass jede Quantenberechnung durchgeführt werden kann, indem eine Sequenz von Single-Qubit-Gates zusammen mit CNOT-Gates ausgeführt wird. Obwohl diese Gattermenge unendlich ist, kann sie durch eine endliche Gattermenge ersetzt werden, indem man auf den Satz von Solovay-Kitaev zurückgreift.

Quantenalgorithmen

Der Fortschritt bei der Suche nach Quantenalgorithmen konzentriert sich normalerweise auf dieses Quantenschaltungsmodell, obwohl es Ausnahmen wie den quantenadiabatischen Algorithmus gibt. Quantenalgorithmen können grob nach der Art der Beschleunigung kategorisiert werden, die gegenüber entsprechenden klassischen Algorithmen erreicht wird.

Quantenalgorithmen, die mehr als eine polynomielle Beschleunigung gegenüber dem bekanntesten klassischen Algorithmus bieten, umfassen den Shor-Algorithmus zum Faktorisieren und die verwandten Quantenalgorithmen zum Berechnen diskreter Logarithmen, zum Lösen der Pell-Gleichung und allgemeiner zum Lösen des versteckten Untergruppenproblems für abelsche endliche Gruppen. Diese Algorithmen hängen vom Grundelement der Quanten-Fourier-Transformation ab. Es wurde kein mathematischer Beweis gefunden, der zeigt, dass ein ebenso schneller klassischer Algorithmus nicht entdeckt werden kann, obwohl dies als unwahrscheinlich gilt befindet sich im Quantenabfragemodell, bei dem es sich um ein eingeschränktes Modell handelt, bei dem untere Schranken viel einfacher zu beweisen sind und nicht unbedingt zu einer Beschleunigung für praktische Probleme führen.

Andere Probleme, darunter die Simulation quantenphysikalischer Prozesse aus der Chemie und Festkörperphysik, die Approximation bestimmter Jones-Polynome und der Quantenalgorithmus für lineare Gleichungssysteme, haben Quantenalgorithmen scheinbar superpolynomische Beschleunigungen und sind BQP-vollständig. Da diese Probleme BQP-vollständig sind, würde ein ebenso schneller klassischer Algorithmus für sie implizieren, dass kein Quantenalgorithmus eine superpolynomielle Beschleunigung liefert, was als unwahrscheinlich erachtet wird.

Einige Quantenalgorithmen, wie der Grover-Algorithmus und die Amplitudenverstärkung, liefern polynomielle Beschleunigungen gegenüber entsprechenden klassischen Algorithmen. Obwohl diese Algorithmen eine vergleichsweise bescheidene quadratische Beschleunigung ergeben, sind sie weit verbreitet und bieten daher Beschleunigungen für eine Vielzahl von Problemen. Viele Beispiele für nachweisbare Quantenbeschleunigungen für Abfrageprobleme beziehen sich auf Grovers Algorithmus, darunter den Algorithmus von Brassard, Høyer und Tapp zum Auffinden von Kollisionen in Zwei-zu-Eins-Funktionen, der den Algorithmus von Grover verwendet, und den Algorithmus von Farhi, Goldstone und Gutmann zur Bewertung von NAND Bäume, die eine Variante des Suchproblems ist.

Kryptografische Anwendungen

Eine bemerkenswerte Anwendung der Quantenberechnung sind Angriffe auf derzeit verwendete kryptografische Systeme. Es wird angenommen, dass die Faktorisierung ganzer Zahlen, die die Sicherheit von kryptografischen Systemen mit öffentlichem Schlüssel untermauert, mit einem gewöhnlichen Computer für große ganze Zahlen rechnerisch nicht durchführbar ist, wenn sie das Produkt von wenigen Primzahlen (zB Produkte von zwei 300-stelligen Primzahlen) sind. Im Vergleich dazu könnte ein Quantencomputer dieses Problem effizient lösen, indem er den Algorithmus von Shor verwendet, um seine Faktoren zu finden. Diese Fähigkeit würde es einem Quantencomputer ermöglichen, viele der heute verwendeten kryptografischen Systeme in dem Sinne zu zerstören, dass es einen polynomiellen Zeitalgorithmus (in der Anzahl der Stellen der ganzen Zahl) zur Lösung des Problems geben würde. Insbesondere basieren die meisten der populären Verschlüsselungen mit öffentlichen Schlüsseln auf der Schwierigkeit, ganze Zahlen zu faktorisieren, oder auf dem Problem des diskreten Logarithmus, die beide durch den Shor-Algorithmus gelöst werden können. Insbesondere könnten die RSA-, Diffie-Hellman- und elliptischen Diffie-Hellman-Algorithmen durchbrochen werden. Diese werden verwendet, um sichere Webseiten, verschlüsselte E-Mails und viele andere Arten von Daten zu schützen. Diese zu durchbrechen hätte erhebliche Auswirkungen auf die elektronische Privatsphäre und Sicherheit.

Die Identifizierung kryptografischer Systeme, die möglicherweise gegen Quantenalgorithmen sicher sind, ist ein aktiv erforschtes Thema im Bereich der Post-Quanten-Kryptografie. Einige Algorithmen mit öffentlichem Schlüssel basieren auf anderen Problemen als der ganzzahligen Faktorisierung und diskreten Logarithmus-Problemen, auf die der Algorithmus von Shor angewendet wird, wie das McEliece-Kryptosystem, das auf einem Problem der Codierungstheorie basiert. Es ist auch nicht bekannt, dass gitterbasierte Kryptosysteme von Quantencomputern gebrochen werden, und es ist ein gut untersuchtes offenes Problem, einen Polynomialzeitalgorithmus zur Lösung des Diederproblems mit versteckten Untergruppen zu finden, das viele gitterbasierte Kryptosysteme brechen würde. Es wurde bewiesen, dass die Anwendung des Grover-Algorithmus zum Brechen eines symmetrischen Algorithmus (geheimer Schlüssel) durch Brute-Force eine Zeit benötigt, die ungefähr 2n/2 Aufrufen des zugrunde liegenden kryptografischen Algorithmus entspricht, verglichen mit ungefähr 2n im klassischen Fall, was bedeutet, dass symmetrische Schlüssellängen effektiv halbiert: AES-256 hätte dieselbe Sicherheit gegen einen Angriff mit dem Grover-Algorithmus wie AES-128 gegen die klassische Brute-Force-Suche (siehe Schlüsselgröße).

Die Quantenkryptographie könnte möglicherweise einige der Funktionen der Public-Key-Kryptographie erfüllen. Quantenbasierte kryptografische Systeme könnten daher sicherer gegen Quantenhacking sein als herkömmliche Systeme.

Suchprobleme

Das bekannteste Beispiel für ein Problem, das eine polynomielle Quantenbeschleunigung zulässt, ist die unstrukturierte Suche, bei der ein markiertes Element aus einer Liste von n Elementen in einer Datenbank gefunden wird. Dies kann durch den Grover-Algorithmus gelöst werden, der O(sqrt(n))-Abfragen an die Datenbank verwendet, quadratisch weniger als die Omega(n)-Abfragen, die für klassische Algorithmen erforderlich sind. In diesem Fall ist der Vorteil nicht nur beweisbar, sondern auch optimal: Es hat sich gezeigt, dass der Grover-Algorithmus die maximal mögliche Wahrscheinlichkeit angibt, das gewünschte Element für beliebig viele Orakelsuchen zu finden.

Probleme, die mit dem Grover-Algorithmus angegangen werden können, haben die folgenden Eigenschaften:

• Es gibt keine durchsuchbare Struktur in der Sammlung möglicher Antworten,
• Die Anzahl der zu prüfenden möglichen Antworten entspricht der Anzahl der Eingaben in den Algorithmus, und
• Es gibt eine boolesche Funktion, die jede Eingabe auswertet und bestimmt, ob es die richtige Antwort ist

Bei Problemen mit all diesen Eigenschaften skaliert die Laufzeit von Grovers Algorithmus auf einem Quantencomputer im Gegensatz zur linearen Skalierung klassischer Algorithmen als Quadratwurzel der Anzahl der Eingaben (oder Elemente in der Datenbank). Eine allgemeine Klasse von Problemen, auf die der Grover-Algorithmus angewendet werden kann, ist das Boolesche Erfüllbarkeitsproblem, bei dem die Datenbank, durch die der Algorithmus iteriert, die aller möglichen Antworten ist. Ein Beispiel und (mögliche) Anwendung hierfür ist ein Passwort-Cracker, der versucht, ein Passwort zu erraten. Symmetrische Verschlüsselungen wie Triple DES und AES sind für diese Art von Angriffen besonders anfällig.

Simulation von Quantensystemen

Da Chemie und Nanotechnologie auf das Verständnis von Quantensystemen angewiesen sind und solche Systeme klassisch nicht effizient simuliert werden können, glauben viele, dass die Quantensimulation eine der wichtigsten Anwendungen des Quantencomputings sein wird. Die Quantensimulation könnte auch verwendet werden, um das Verhalten von Atomen und Teilchen unter ungewöhnlichen Bedingungen wie den Reaktionen in einem Collider zu simulieren. Quantensimulationen könnten verwendet werden, um zukünftige Bahnen von Partikeln und Protonen unter Überlagerung im Doppelspaltexperiment vorherzusagen. Etwa 2% des jährlichen globalen Energieoutputs werden für die Stickstofffixierung verwendet, um Ammoniak für den Haber-Prozess in der Landwirtschaft zu produzieren Düngemittelindustrie, während natürlich vorkommende Organismen auch Ammoniak produzieren. Quantensimulationen könnten verwendet werden, um diesen Prozess zu verstehen, der die Produktion erhöht.

Quantum Annealing und adiabatische Optimierung
Quantum Annealing oder adiabatische Quantenberechnung beruht auf dem adiabatischen Theorem, um Berechnungen durchzuführen. Ein System wird in den Grundzustand für einen einfachen Hamilton-Operator versetzt, der sich langsam zu einem komplizierteren Hamilton-Operator entwickelt, dessen Grundzustand die Lösung des fraglichen Problems darstellt. Das adiabatische Theorem besagt, dass das System, wenn die Evolution langsam genug ist, während des gesamten Prozesses in seinem Grundzustand bleibt.

Maschinelles Lernen

Da Quantencomputer Ausgaben erzeugen können, die klassische Computer nicht effizient produzieren können, und da Quantencomputer im Wesentlichen linear algebraisch sind, äußern einige die Hoffnung, Quantenalgorithmen zu entwickeln, die Aufgaben des maschinellen Lernens beschleunigen können. So soll beispielsweise der Quantenalgorithmus für lineare Gleichungssysteme oder „HHL-Algorithmus“, benannt nach seinen Entdeckern Harrow, Hassidim und Lloyd, gegenüber klassischen Gegenstücken Beschleunigung bieten. Einige Forschungsgruppen haben kürzlich den Einsatz von Quanten-Annealing-Hardware zum Trainieren von Boltzmann-Maschinen und tiefen neuronalen Netzen untersucht.

Computational Biology

Im Bereich der Computerbiologie hat Quantencomputing eine große Rolle bei der Lösung vieler biologischer Probleme gespielt. Ein bekanntes Beispiel wäre die Computergenomik und wie Computer die Zeit für die Sequenzierung eines menschlichen Genoms drastisch verkürzt haben. Angesichts der Art und Weise, wie die Computerbiologie generische Datenmodellierung und -speicherung verwendet, wird erwartet, dass auch ihre Anwendungen auf die Computerbiologie entstehen.

Computergestütztes Wirkstoffdesign und generative Chemie

Modelle der tiefgreifenden generativen Chemie stellen sich als leistungsstarke Werkzeuge heraus, um die Wirkstoffforschung zu beschleunigen. Die immense Größe und Komplexität des Strukturraums aller möglichen wirkstoffähnlichen Moleküle stellen jedoch erhebliche Hindernisse dar, die in Zukunft von Quantencomputern überwunden werden könnten. Quantencomputer eignen sich von Natur aus gut zum Lösen komplexer Quanten-Vielteilchenprobleme und können daher bei Anwendungen der Quantenchemie hilfreich sein. Daher ist zu erwarten, dass quantenverstärkte generative Modelle, einschließlich Quanten-GANs, schließlich zu ultimativen generativen Chemiealgorithmen weiterentwickelt werden können. Hybridarchitekturen, die Quantencomputer mit tiefen klassischen Netzwerken kombinieren, wie beispielsweise Quantum Variational Autoencoders, können bereits auf kommerziell erhältlichen Annealern trainiert und verwendet werden, um neue arzneimittelähnliche molekulare Strukturen zu generieren.

Entwicklung von physikalischen Quantencomputern
Die Herausforderungen
Beim Bau eines großen Quantencomputers gibt es eine Reihe von technischen Herausforderungen. Der Physiker David DiVincenzo hat diese Anforderungen an einen praktischen Quantencomputer aufgelistet:

• Physikalisch skalierbar, um die Anzahl der Qubits zu erhöhen,
• Qubits, die auf beliebige Werte initialisiert werden können,
• Quantentore, die schneller sind als die Dekohärenzzeit,
• Universelles Torset,
• Leicht lesbare Qubits.

Auch die Beschaffung von Teilen für Quantencomputer ist sehr schwierig. Viele Quantencomputer, wie die von Google und IBM konstruierten, benötigen Helium-3, ein Nebenprodukt der Kernforschung, und spezielle supraleitende Kabel, die nur von der japanischen Firma Coax Co. hergestellt werden.

Die Steuerung von Multi-Qubit-Systemen erfordert die Erzeugung und Koordination einer großen Anzahl elektrischer Signale mit enger und deterministischer zeitlicher Auflösung. Dies hat zur Entwicklung von Quantencontrollern geführt, die eine Schnittstelle zu den Qubits ermöglichen. Diese Systeme zu skalieren, um eine wachsende Zahl von Qubits zu unterstützen, ist eine zusätzliche Herausforderung.

Quantendekohärenz

Eine der größten Herausforderungen beim Bau von Quantencomputern ist die Kontrolle oder Beseitigung der Quantendekohärenz. Dies bedeutet normalerweise, das System von seiner Umgebung zu isolieren, da Interaktionen mit der Außenwelt das System zur Dekohärenz führen. Es gibt jedoch auch andere Quellen der Dekohärenz. Beispiele sind die Quantengatter und die Gitterschwingungen und der thermonukleare Hintergrundspin des physikalischen Systems, das verwendet wird, um die Qubits zu implementieren. Dekohärenz ist irreversibel, da sie effektiv nicht einheitlich ist und normalerweise stark kontrolliert, wenn nicht vermieden werden sollte. Insbesondere die Dekohärenzzeiten für Kandidatensysteme, die transversale Relaxationszeit T2 (für die NMR- und MRI-Technologie auch Dephasierungszeit genannt), liegen bei niedriger Temperatur typischerweise zwischen Nanosekunden und Sekunden. Derzeit erfordern einige Quantencomputer, dass ihre Qubits auf 20 Millikelvin gekühlt werden (normalerweise mit einem Verdünnungskühlschrank), um eine signifikante Dekohärenz zu verhindern. Eine Studie aus dem Jahr 2020 argumentiert, dass ionisierende Strahlung wie die kosmische Strahlung dennoch dazu führen kann, dass bestimmte Systeme innerhalb von Millisekunden entkohären.

Infolgedessen können zeitaufwändige Aufgaben einige Quantenalgorithmen funktionsunfähig machen, da das Aufrechterhalten des Zustands von Qubits über einen ausreichend langen Zeitraum die Überlagerungen schließlich verfälscht.

Diese Probleme sind für optische Ansätze schwieriger, da die Zeitskalen um Größenordnungen kürzer sind und ein oft zitierter Ansatz zu ihrer Überwindung die optische Pulsformung ist. Fehlerraten sind typischerweise proportional zum Verhältnis von Betriebszeit zu Dekohärenzzeit, daher muss jede Operation viel schneller als die Dekohärenzzeit abgeschlossen werden.

Wenn die Fehlerrate klein genug ist, wird, wie im Quantenschwellenwertsatz beschrieben, angenommen, dass es möglich ist, eine Quantenfehlerkorrektur zu verwenden, um Fehler und Dekohärenz zu unterdrücken. Dies ermöglicht, dass die Gesamtberechnungszeit länger ist als die Dekohärenzzeit, wenn das Fehlerkorrekturschema Fehler schneller korrigieren kann, als die Dekohärenz sie einführt. Ein oft zitierter Wert für die erforderliche Fehlerrate in jedem Gatter für fehlertolerante Berechnungen ist 10–3, vorausgesetzt, das Rauschen ist depolarisierend.

Die Erfüllung dieser Skalierbarkeitsbedingung ist für eine Vielzahl von Systemen möglich. Die Verwendung der Fehlerkorrektur bringt jedoch die Kosten einer stark erhöhten Anzahl von benötigten Qubits mit sich. Die Zahl, die erforderlich ist, um ganze Zahlen unter Verwendung des Shor-Algorithmus zu faktorisieren, ist immer noch polynomiell und wird als zwischen L und L2 angesehen, wobei L die Anzahl der Stellen in der zu faktorisierenden Zahl ist; Fehlerkorrekturalgorithmen würden diese Zahl um einen zusätzlichen Faktor von L aufblähen. Für eine 1000-Bit-Zahl bedeutet dies, dass etwa 104 Bit ohne Fehlerkorrektur benötigt werden. Mit Fehlerkorrektur würde die Zahl auf etwa 107 Bit ansteigen. Die Rechenzeit beträgt etwa L2 oder etwa 107 Schritte und bei 1 MHz etwa 10 Sekunden.

Ein ganz anderer Ansatz für das Stabilitäts-Dekohärenz-Problem besteht darin, einen topologischen Quantencomputer mit Anyons zu schaffen, Quasiteilchen, die als Threads verwendet werden und sich auf die Geflechttheorie verlassen, um stabile Logikgatter zu bilden.

Quantenüberlegenheit

Quantenüberlegenheit ist ein von John Preskill geprägter Begriff, der sich auf die technische Meisterleistung bezieht, zu zeigen, dass ein programmierbares Quantengerät ein Problem lösen kann, das über die Fähigkeiten moderner klassischer Computer hinausgeht. Das Problem muss nicht nützlich sein, daher betrachten einige den Quantenüberlegenheitstest nur als möglichen zukünftigen Maßstab.

Im Oktober 2019 behauptete Google AI Quantum mit Hilfe der NASA als erster, die Quantenüberlegenheit erreicht zu haben, indem sie Berechnungen auf dem Sycamore-Quantencomputer mehr als 3,000,000 Mal schneller durchführte als auf dem Summit, der allgemein als der schnellste der Welt gilt Computer. Diese Behauptung wurde später in Frage gestellt: IBM hat erklärt, dass Summit Samples viel schneller durchführen kann als behauptet, und Forscher haben seitdem bessere Algorithmen für das Sampling-Problem entwickelt, das verwendet wird, um die Quantenüberlegenheit zu beanspruchen, wodurch die Lücke zwischen Sycamore und klassische Supercomputer.

Im Dezember 2020 implementierte eine Gruppe am USTC eine Art Boson-Sampling an 76 Photonen mit einem photonischen Quantencomputer Jiuzhang, um die Quantenüberlegenheit zu demonstrieren. Die Autoren behaupten, dass ein klassischer zeitgenössischer Supercomputer eine Rechenzeit von 600 Millionen Jahren benötigen würde, um die Anzahl von Samples zu erzeugen, die sein Quantenprozessor in 20 Sekunden erzeugen kann. Am 16. November 2021 präsentierte IBM auf dem Quantencomputing-Gipfel einen 127-Qubit-Mikroprozessor namens IBM Eagle.

Physische Implementierungen

Für die physikalische Umsetzung eines Quantencomputers werden viele verschiedene Kandidaten verfolgt, darunter (unterscheidbar durch das physikalische System, mit dem die Qubits realisiert werden):

• Supraleitendes Quantencomputing (Qubit implementiert durch den Zustand kleiner supraleitender Schaltkreise, Josephson-Übergänge)
• Quantencomputer mit gefangenen Ionen (Qubit, das durch den inneren Zustand der gefangenen Ionen implementiert wird)
• Neutrale Atome in optischen Gittern (Qubit implementiert durch interne Zustände neutraler Atome, die in einem optischen Gitter gefangen sind)
• Quantenpunktcomputer, spinbasiert (zB der Loss-DiVincenzo Quantencomputer) (Qubit gegeben durch die Spinzustände der gefangenen Elektronen)
• Quantenpunktcomputer, raumbezogen (Qubit gegeben durch Elektronenposition im Doppelquantenpunkt)
• Quantencomputing mit konstruierten Quantenquellen, die im Prinzip den Bau von Quantencomputern ermöglichen könnten, die bei Raumtemperatur arbeiten
• Gekoppelter Quantendraht (Qubit implementiert durch ein Paar von Quantendrähten, die durch einen Quantenpunktkontakt gekoppelt sind)
• Kernspinresonanz-Quantencomputer (NMRQC) implementiert mit der Kernspinresonanz von Molekülen in Lösung, wobei Qubits durch Kernspins innerhalb des gelösten Moleküls bereitgestellt und mit Radiowellen untersucht werden
• Festkörper-NMR Kane-Quantencomputer (Qubit realisiert durch den Kernspinzustand von Phosphordonatoren in Silizium)
• Elektronen-auf-Helium-Quantencomputer (Qubit ist der Elektronenspin)
• Hohlraumquantenelektrodynamik (CQED) (Qubit, bereitgestellt durch den inneren Zustand von eingefangenen Atomen, die an Hohlräume mit hoher Finesse gekoppelt sind)
• Molekularer Magnet (Qubit durch Spinzustände gegeben)
• Fulleren-basierter ESR-Quantencomputer (Qubit basierend auf dem elektronischen Spin von Atomen oder Molekülen, die in Fullerene eingeschlossen sind)
• Nichtlinearer optischer Quantencomputer (Qubits, die durch die Verarbeitung von Zuständen verschiedener Lichtmodi durch lineare und nichtlineare Elemente realisiert werden)
• Linearer optischer Quantencomputer (Qubits, die durch die Verarbeitung von Zuständen verschiedener Lichtmodi durch lineare Elemente wie Spiegel, Strahlteiler und Phasenschieber realisiert werden)
• Diamantbasierter Quantencomputer (Qubit, realisiert durch den Elektronen- oder Kernspin von Stickstoff-Leerstellenzentren in Diamant)
• Bose-Einstein-Kondensat-basierter Quantencomputer
• Quantencomputer auf Transistorbasis – String-Quantencomputer mit Mitreißen positiver Löcher mithilfe einer elektrostatischen Falle
• Quantencomputer auf der Basis von Seltenerdmetallionen-dotierten anorganischen Kristallen (Qubit, realisiert durch den internen elektronischen Zustand von Dotierstoffen in Glasfasern)
• Quantencomputer auf Basis von metallähnlichen Kohlenstoff-Nanosphären
• Die große Zahl der Kandidaten zeigt, dass Quantencomputing trotz rasanter Fortschritte noch in den Kinderschuhen steckt.

Es gibt eine Reihe von Quantencomputermodellen, die sich durch die Grundelemente unterscheiden, in die die Berechnung zerlegt wird. Für praktische Implementierungen sind die vier relevanten Berechnungsmodelle:

• Quantum Gate Array (Berechnung zerlegt in eine Folge von Quantengattern mit wenigen Qubits)
• Einweg-Quantencomputer (Berechnung zerlegt in eine Folge von Ein-Qubit-Messungen, angewendet auf einen stark verschränkten Anfangszustand oder Clusterzustand)
• Adiabatischer Quantencomputer, basierend auf Quanten-Annealing (Berechnung zerlegt in eine langsame kontinuierliche Transformation eines anfänglichen Hamilton-Operators in einen finalen Hamilton-Operator, dessen Grundzustände die Lösung enthalten)
• Topologischer Quantencomputer (Berechnung zerlegt in das Geflecht von Anyons in einem 2D-Gitter)

Die Quanten-Turing-Maschine ist theoretisch wichtig, aber die physikalische Umsetzung dieses Modells ist nicht machbar. Alle vier Berechnungsmodelle haben sich als gleichwertig erwiesen; jeder kann den anderen mit nicht mehr als polynomialem Overhead simulieren.