Quantencomputermodelle

Quantenberechnungen ersetzen klassische Bits durch Quantenzustände, die überlagert und verschränkt werden können, wodurch Modelle wie der Quantenschaltkreis und die Komplexitätsklasse BQP definiert werden, die einige Probleme offenbar schneller lösen als jede klassische Methode.

Definition

Ein Quantenmodell der Berechnung verarbeitet Informationen, die in Qubits gespeichert sind, deren Zustände Einheitsvektoren in einem komplexen Raum sind; die Berechnung wendet reversible Quantengatter an, um Superposition und Verschränkung zu erzeugen, und eine abschließende Messung liefert ein klassisches Ergebnis mit Wahrscheinlichkeiten, die durch den Quantenzustand festgelegt werden.

Scope

Dieses Thema behandelt Qubits und Quantengatter, das Quantenschaltkreismodell und seine Äquivalenz zur Quanten-Turing-Maschine, die Komplexitätsklasse BQP der effizienten Quantenberechnung und ihre Beziehung zu klassischen Klassen, grundlegende Algorithmen wie Shors Faktorisierungsalgorithmus und Grovers Suchalgorithmus sowie die Rolle von Messung und Dekohärenz bei der Definition des Modells.

Core questions

• Wie verändern Superposition und Verschränkung die Möglichkeiten einer Berechnung?
• Welche Beziehung besteht zwischen der effizienten Quantenklasse BQP und klassischen Klassen?
• Für welche Probleme bieten Quantenalgorithmen eine nachweisbare oder offensichtliche Beschleunigung?
• Wie schränken Messung und das No-Cloning-Prinzip die Quantenberechnung ein?

Key theories

Quantenschaltkreismodell und BQP

Effiziente Quantenberechnung wird durch Quantenschaltkreise polynomialer Größe über einem universellen Gattersatz erfasst, die die Klasse BQP definieren, welche P enthält und diese vermutlich erweitert, während sie immer noch innerhalb von PSPACE liegt.

Quantenbeschleunigungen

Shors Algorithmus faktorisiert ganze Zahlen in polynomialer Zeit und Grovers Algorithmus durchsucht einen unstrukturierten Raum mit einer quadratischen Beschleunigung, was konkrete Vorteile des Quantenmodells für spezifische Aufgaben demonstriert.

Clinical relevance

Quantenmodelle leiten das Design von Quantenhardware und -algorithmen; Shors Faktorisierungsalgorithmus bedroht Public-Key-Kryptosysteme, deren Sicherheit auf der Schwierigkeit der Faktorisierung beruht, was die Entwicklung der Post-Quanten-Kryptographie motiviert, während die Quantensimulation Fortschritte in Chemie und Materialwissenschaft verspricht.

History

Feynman schlug 1982 vor, Quantensysteme zur Simulation von Physik zu verwenden, und Deutsch formalisierte 1985 die Quanten-Turing-Maschine. Shors Faktorisierungsalgorithmus von 1994 und Grovers Suchalgorithmus von 1996 zeigten konkrete Beschleunigungen und machten die Quantenberechnung zu einem wichtigen Zweig der Komplexitätstheorie und einem Motor experimenteller Bemühungen.

Debates

Wie groß ist der Quantenvorteil, und ist er in großem Maßstab physikalisch realisierbar?

Quantencomputer berechnen dieselben Funktionen wie klassische Computer, die Frage ist also die Effizienz. Die genaue Beziehung zwischen BQP und klassischen Klassen ist ungelöst, und ob große fehlertolerante Quantencomputer trotz Dekohärenz gebaut werden können, bleibt eine offene wissenschaftliche und technische Frage.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

Können Quantencomputer Dinge berechnen, die klassische Computer nicht können?

Nein. Quantencomputer lösen genau dieselbe Klasse von Problemen wie klassische Computer; der Unterschied liegt in der Geschwindigkeit. Für bestimmte Probleme, wie die Faktorisierung großer Zahlen, scheint das Quantenmodell dramatisch schneller zu sein, aber es erweitert nicht die Grenze dessen, was prinzipiell berechenbar ist.

Warum ist Quantencomputing für die Kryptographie wichtig?

Shors Algorithmus würde es einem großen Quantencomputer ermöglichen, große ganze Zahlen zu faktorisieren und diskrete Logarithmen effizient zu berechnen, wodurch die Public-Key-Systeme, die einen Großteil der heutigen Kommunikation sichern, gebrochen würden. Diese Aussicht hat die Suche nach Post-Quanten-Schemata vorangetrieben, die auf Problemen basieren, die selbst für Quantenmaschinen als schwierig gelten.