Wie kann man Universalität für eine Reihe von Toren beweisen / widerlegen?

Ein universeller Satz von Toren kann den Betrieb jedes anderen Tortyps nachahmen, vorausgesetzt, es sind genügend Tore vorhanden. Ein universeller Satz von Quantentoren sind beispielsweise der Hadamard (   ), die Phasenverschiebung (  T  ) und das \ mathrm {CNOT} -Tor . Wie kann man die Universalität einer Reihe von Toren wie \ {H, T \} , \ {\ mathrm {CNOT}, T \} oder \ {\ mathrm {CNOT}, H \} widerlegen oder beweisen ?$H$$\pi/8$$T$$\mathrm{CNOT}$$\{H,T\}$$\{\mathrm{CNOT},T\}$$\{\mathrm{CNOT}, H\}$

Universalität kann eine sehr subtile Sache sein, die nur schwer zu beweisen ist. Es gibt normalerweise zwei Möglichkeiten, dies zu beweisen:

• Zeigen Sie direkt mit den von Ihnen gewählten Toren, wie Sie beliebige Einheiten beliebiger Größe konstruieren können (es gibt keine Einschränkung für die Größe der Konstruktion, nur, dass dies möglich ist), und zwar mit beliebiger Genauigkeit (für einige nicht-triviale Teilräume des gesamten Hilbert-Raums) Raum).

• Zeigen Sie, wie die von Ihnen ausgewählte Gruppe von Toren verwendet werden kann, um eine vorhandene universelle Gruppe (mit willkürlicher Genauigkeit) wiederherzustellen.

Umgekehrt, wenn Sie es widerlegen möchten, zeigen Sie, dass der Effekt Ihrer Tormenge immer durch ein (angenommenes) geringeres Berechnungsmodell simuliert werden kann, in der Regel durch klassische Berechnungen.

Es gibt einige Heuristiken, die Sie zur Orientierung verwenden können:

• Sie müssen ein Multi-Qubit-Gate in Ihrem Set haben. Wenn Sie nur Single-Qubit-Gatter haben, können Sie jedes Qubit auf einem klassischen Computer unabhängig simulieren. Wenn wir also glauben, dass Quantencomputer leistungsfähiger sind als klassische, sind einzelne Qubit-Gatter allein für die Quantenberechnung nicht universell. Dies schließt {H, T} aus.

• Sie müssen ein Tor haben, das Überlagerungen erzeugt. Dies schließt {CNOT, T} aus. Auch dies ist eine klassische Berechnung mit der Hinzufügung einer irrelevanten globalen Phase.

Dies sind natürlich keine ausreichenden Bedingungen: Die Menge {H, S, CNOT} kann ebenfalls effizient simuliert werden (siehe Gottesman-Knill-Theorem). Dies muss auch für {H, CNOT} zutreffen, da es sich um eine Teilmenge handelt und die Operationen, die sie erstellen können, nicht mehr als die der ursprünglichen Menge sind.

Eine der universellen Mengen, die ich am interessantesten finde, ist {Toffoli, H} . Es ist für mich immer wieder überraschend, dass dies ausreicht (besonders im Vergleich zum vorherigen Set). Beachten Sie, dass es sich nicht um komplexe Zahlen handelt.

Es ist auch möglich, Universalität von einem einzelnen Zwei-Qubit-Gatter wie

$$\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)$$

Nielsen und Chuang, S. 191 der Jubiläumsausgabe:

Wir haben gerade gezeigt, dass eine beliebige unitäre Matrix auf einem dimensionalen Hilbert-Raum als Produkt zweistufiger unitäre Matrizen geschrieben werden kann. Wir zeigen nun, dass einzelne Qubit- und CNOT-Gatter zusammen verwendet werden können, um eine willkürliche Zwei-Ebenen-Einheitsoperation auf dem Zustandsraum von Qubits zu implementieren . Wenn wir diese Ergebnisse kombinieren, sehen wir, dass einzelne Qubit- und CNOT-Gatter verwendet werden können, um eine willkürliche einheitliche Operation mit Qubits zu implementieren, und daher für die Quantenberechnung universell sind.$d$$n$$n$

Der erste Satz dort ist ein akzeptiertes Ergebnis, so dass Sie einfach zeigen müssen, dass die Kombination Ihres Gate-Sets "eine willkürliche Einheitsoperation mit zwei Ebenen" implementieren kann. So zitieren Sie Wikipedia:

Technisch ist dies unmöglich, da die Anzahl der möglichen Quantentore unzählbar ist, während die Anzahl der endlichen Folgen aus einer endlichen Menge zählbar ist. Um dieses Problem zu lösen, brauchen wir nur, dass eine Quantenoperation durch eine Folge von Gattern aus dieser endlichen Menge approximiert werden kann.

Siehe auch dieses Papier .