Kann eine Turing-Maschine einen Quantencomputer simulieren?

62

Ich weiß, dass eine Turing-Maschine 1 theoretisch "alles" simulieren kann, aber ich weiß nicht, ob sie etwas simulieren kann, das sich grundlegend von einem quantenbasierten Computer unterscheidet. Gibt es irgendwelche Versuche, dies zu tun, oder hat jemand bewiesen, dass es möglich / nicht möglich ist?

Ich habe herumgegoogelt, bin aber kein Experte für dieses Thema, daher weiß ich nicht, wo ich suchen soll. Ich habe den Wikipedia-Artikel über Quantenturing-Maschinen gefunden , bin mir aber nicht sicher, wie genau er sich von einem klassischen TM unterscheidet. Ich habe auch die Universal Quantum Turing Machine des Papiers Deutsch von W. Fouché et al. Gefunden , aber es ist ziemlich schwer für mich zu verstehen.

1. Falls es nicht klar ist, meine ich mit Turing-Maschine das theoretische Konzept, nicht eine physikalische Maschine (dh eine Implementierung des theoretischen Konzepts).

simulation quantum-turing-machine computability-theory Riker
quelle

Antworten:

43

Ja , ein Quantencomputer könnte von einer Turing-Maschine simuliert werden.Dies sollte jedoch nicht bedeuten, dass reale Quantencomputer keinen Quantenvorteil genießen können , dh einen signifikanten Implementierungsvorteil gegenüber realen klassischen Computern.

Als Faustregel gilt: Wenn ein Mensch manuell beschreiben oder sich vorstellen kann, wie etwas funktionieren soll, kann diese Vorstellung auf einer Turing-Maschine implementiert werden. Quantencomputer fallen in diese Kategorie.

(1)|ψ⟩=α|0⟩+β|1⟩,

Bei diesen Vorteilen geht es jedoch um Effizienz. In einigen Fällen geht diese Effizienz über das Astronomische hinaus und ermöglicht Dinge, die mit klassischer Hardware nicht praktikabel gewesen wären. Dies führt dazu, dass Quantencomputer wichtige Anwendungen in der Kryptographie und dergleichen haben.

Quantum Computing ist jedoch derzeit nicht von dem Wunsch nach Dingen motiviert, die wir vorher grundsätzlich nicht konnten. Wenn ein Quantencomputer eine Operation ausführen kann, kann eine klassische Turing-Maschine eine Simulation eines Quantencomputers ausführen, der diese Operation ausführt.

Zufälligkeit ist kein Problem. Ich denke zwei große Gründe:

  1. Zufälligkeit kann ohnehin mit Verteilungsmathematik genauer erfasst werden.

  2. Zufälligkeit ist anfangs kein echtes " Ding ". es ist nur Unwissenheit. Und wir können immer Unwissenheit erzeugen.

Nat
quelle
7

Um den Zusammenbruch der Wellenfunktion zu simulieren, benötigen Sie eine Zufallsquelle. Sie brauchen also eine probabilistische Turing-Maschine .

Bjørn Kjos-Hanssen
quelle
6
Klassische Geräte können typische Zufallszahlengeneratoren verwenden oder was auch immer für ihre Zwecke geeignet ist. Zufälligkeit ist keine fundamentale Eigenschaft, die aus der Quantenmechanik abgeleitet werden muss (was ein ziemlich großes Missverständnis darstellt , das die Kopenhagener Interpretation oft mit sich bringt und das vielleicht am besten als vereinfachende Annäherung verstanden wird).
Nat
3
Im Allgemeinen können Sie, wenn Sie sich nicht für Effizienz interessieren, einfach jedes Element eines Raums ausprobieren, anstatt es abzutasten, um die Notwendigkeit von Zufälligkeiten zu vermeiden.
Tavian Barnes
2
Wenn Sie wirklich alle relevanten Quanteneffekte erzeugen möchten, müssen Sie in der Lage sein, die Bell-Ungleichung zu verletzen, und daher ist eine wahrscheinlichkeitstheoretische Turing-Maschine nicht ausreichend. Wenn Sie nur die Rechenleistung der Quanten-Turing-Maschine anpassen möchten, können Sie eine Turing-Maschine ohne Zufallsprinzip verwenden. In jedem Fall wird eine probabilistische Turing-Maschine nicht nützlich sein.
Diskrete Eidechse
4

Um das zu vervollständigen, was andere gesagt haben: Soweit wir wissen, kann eine (klassische) Turing-Maschine Quantenkorrelationen nicht wirklich simulieren . Dies wird explizit im Abschnitt Eigenschaften des universellen Quantencomputers durch die wegweisende Arbeit von David Deutsch Quantentheorie, das Church-Turing-Prinzip und den universellen Quantencomputer (Proceedings of the Royal Society of London A 400, S. 97-117 (1985) beansprucht )).

Details hängen von der Implementierung oder Ihren genauen Definitionen für Turing-Maschine, von Quantencomputer und insbesondere von Simulieren ab (wenn Sie großzügig genug sind, was Simulieren bedeutet, kann alles alles simulieren). Im Allgemeinen ist es möglich, einen Quantencomputer zu entwerfen, der, wenn er wiederholt ausgehend von dem exakt gleichen Startzustand (oder den Eingabebits) in jeder Operation betrieben wird, zufällige Ausgabebits erzeugt, die bestimmte Quantenkorrelationen miteinander aufweisen.

Soweit ich weiß, kann eine Turing-Maschine das nicht.

agaitaarino
quelle
1
Es könnte sich lohnen, hinzuzufügen (es ist vielleicht eher eine Umformulierung, aber eine, die ich für nützlich halte), dass das Hinzufügen von 'Zufallszahlengenerierung' zu einer Turing-Maschine (z. B. als Orakel) bei der Simulation des Quantenturing nicht hilft Maschine, da es keine Bits simulieren kann, die die Bellsche Ungleichung verletzen, während es eine Quantenturing-Maschine kann (wie in der Arbeit von Deutsch angegeben, wenn ich es richtig lese).
Diskrete Eidechse