Entscheidbarkeit / Algorithmus zur Überprüfung der Universalität eines Quantengattersatzes

Ist es bei einer endlichen Menge von Quantentoren (im Sinne) entscheidbar, ob eine universelle ist ? Einerseits sind "fast alle" Torsätze universell, andererseits sind nicht universelle Torsätze immer noch nicht gut verstanden (insbesondere ist natürlich nicht bekannt, ob jeder nicht universelle Torsatz klassisch simulierbar ist). Daher stelle ich mir vor, dass es nicht trivial sein könnte, einen expliziten Algorithmus zur Überprüfung der Universalität anzugeben. $\mathcal{G} = \{G_1, \dots, G_n\}$ $\mathcal{G}$

quantum-computing Marcin Kotowski
quelle

Können Sie die Frage klären? In Joes Antwort wird davon ausgegangen, dass Sie eine feste Anzahl von Qubits haben und alle Gates auf diese einwirken. Aus Gründen der Universalität gehen wir jedoch häufig davon aus, dass Gates auf jede Teilmenge von Qubits einwirken können. Beispielsweise sind CNOT + alle Ein-Qubit-Gatter nicht universell, wenn die Ein-Qubit-Gatter nur auf das erste Qubit einwirken können, und CNOT nur von Qubit 1 zu Qubit 2. Im letzteren Fall möchten wir möglicherweise auf viele Qubits extrapolieren Universalität zu bekommen. In diesem Fall denke ich, dass die Antwort unbekannt sein kann.

@ DanielGottesman: Ich stimme den Einschränkungen meiner Antwort zu. In der Tat glaube ich, dass es im letzteren Fall wie folgt unentscheidbar ist: Nehmen Sie ein zellulares Automaten auf einem unendlichen Gitter von Qubits und verwenden Sie es, um das Stoppproblem zu codieren (nennen Sie dieses Update einheitliches ). Nehmen Sie dann ein zweites Gitter mit einem universellen QCA (mit Update Unitary ). Wir können eine neue einheitliche , wobei der Index ein Qubit bezeichnet, das auf iff der ersten Zelle gesetzt ist Automaten werden angehalten.

U_{1}

$U_1$

U_{2}

$U_2$

C U_{2} = | 0 ⟩ ⟨ 0 |_{H} \otimes I + | 1 ⟩ ⟨ 1 | \otimes U_{2}

$CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$

H

$H$

| 1 ⟩

$|1\rangle$

Joe Fitzsimons

Somit ist das Gate genau dann universell, wenn die erste Turing-Maschine anhält, und ist daher unentscheidbar.

C U_{2} \times U_{1}

$CU_2 \times U_1$

Joe Fitzsimons

Antworten:

Für den Fall der Hamiltonianer lautet die Antwort trivial ja: Sie zählen einfach die unabhängigen Elemente der Lie-Algebra auf. Da die Lie-Algebra ein Vektorraum ist, wird der Lie-Bracket-Operator hinzugefügt. Da der Raum endlich ist, hat er eine endliche Basis, und die leicht überprüft werden kann, ob er unter der Operation der Lie-Klammer geschlossen oder offen ist. Das einfache Überprüfen der Lie-Klammer aller Paare orthogonaler Operatoren kann zeitpolynomisch in der Dimensionalität des Raums erfolgen, und eine geeignete Operatorbasis kann durch die Gram-Schmidt-Methode gefunden werden.

Bei Gates haben Sie nicht wirklich die gleiche Möglichkeit, sofort auf Infinitesimale zurückzugreifen, und müssen Gates mit irrationalen Eigenwerten erstellen, damit Sie die erforderlichen Infinitesimalgeneratoren beliebig gut approximieren können. Ich denke, dass es einen relativ einfachen Weg gibt, dies zu tun, aber es ist mir nicht sofort klar.

In jedem Fall würde es ein einfaches notwendiges, aber nicht ausreichendes Kriterium für die Universalität darstellen, das Protokoll der Tore zu nehmen, um eine Reihe von Operatoren zu erhalten, die sie beim Potenzieren erzeugen, und zu prüfen, ob diese die vollständige Lie-Algebra erzeugen.

Joe Fitzsimons
quelle

Warum sollten wir nur Paare prüfen?

Alex 'Qubeat'

@AlexV: Weil die Lie-Klammer an 2 Eingängen arbeitet. Jedes Mal, wenn Sie einen neuen linear unabhängigen Operator erstellen, erstellen Sie einen orthogonalen und wiederholen diesen Vorgang, bis Sie den Abschluss erhalten.

Joe Fitzsimons

Ich meinte, Sie sollten , aber nicht nur Paare, z. B. siehe mein eigenes Papier arxiv.org/abs/quant-ph/0010071

[\dots [H_{k}, H_{j}], H_{l}], \dots]

$[\ldots[H_k,H_j],H_l],\ldots]$

Alex 'qubeat'

@AlexV: Das musst du nicht. Da es sich um einen Vektorraum handelt, ist ein Vektor genau dann orthogonal zu einem bestimmten Unterraum, wenn er zu einer beliebigen Basis für diesen Unterraum orthogonal ist.

Joe Fitzsimons

Wahrscheinlich sprechen wir über verschiedene Dinge - über welchen Vektorraum sprechen Sie? Sie kennen die von Ihren Toren erzeugte Subalgebra nicht von Anfang an - Sie müssen sie aus gegebenen Hamiltonianern konstruieren, um zu überprüfen, ob es sich um die gesamte Lie-Algebra handelt.

Alex 'Qubeat'