Jones Polynom

12

Es gibt viele ziemlich standardmäßige Quantenalgorithmen, die alle in einem sehr ähnlichen Rahmen verstanden werden können, von Deutschs Algorithmus Simons Problem, Grovers Suche, Shors Algorithmus und so weiter.

Ein Algorithmus, der völlig anders zu sein scheint, ist der Algorithmus zur Bewertung des Jones-Polynoms . Darüber hinaus scheint dies ein entscheidender Algorithmus zu sein, um zu verstehen, dass es sich um ein BQP-vollständiges Problem handelt: Es zeigt die volle Leistung eines Quantencomputers. Für eine Variante des Problems ist DQC-1 vollständig , dh es zeigt die volle Leistung eines sauberen Qubits .

Das Jones Polynomial Algorithmus Paper präsentiert den Algorithmus auf eine ganz andere Art und Weise als die anderen Quantenalgorithmen. Gibt es eine ähnlichere / bekanntere Möglichkeit, den Algorithmus zu verstehen (insbesondere das einheitliche in der DQC-1-Variante oder nur die gesamte Schaltung in der BQP-vollständigen Variante)?U

DaftWullie
quelle

Antworten:

5

Diese Antwort ist mehr oder weniger eine Zusammenfassung des von Ihnen verlinkten Aharonov-Jones-Landau-Papiers, wobei jedoch alles, was nicht direkt mit der Definition des Algorithmus zusammenhängt, entfernt wurde. Hoffentlich ist das nützlich.

Der Aharonov-Jones-Landau-Algorithmus approximiert das Jones-Polynom des Plat-Verschlusses eines Geflechts an einer k- ten Wurzel der Einheit, indem er es als (einige Neuskalierung) eines Matrixelements einer bestimmten einheitlichen Matrix U σ , dem Bild von σ, realisiert unter einer bestimmten einheitlichen Darstellung der Geflechtgruppe B 2 n . Bei einer Implementierung von U σ als Quantenschaltung ist die Approximation seiner Matrixelemente mit dem Hadamard-Test unkompliziert . Der nichttriviale Teil approximiert U & sgr; als Quantenschaltung.σkUσσB2nUσUσ

Wenn ein Geflecht eingeschaltet ist 2 n - Stränge mit m Kreuzungen, können wir schreiben σ = σ & egr; 1 a 1 σ & egr; 2 a 2σ & egr; m einen m , wobei a 1 , a 2 , ... , a m{ 1 , 2 , , 2 n - 1 } , ϵ 1 , ϵ 2 ,σ2nmσ=σa1ϵ1σa2ϵ2σamϵma1,a2,,am{1,2,,2n1} und σ i ist der Generator von B 2 n , der dem Überqueren des i- ten Strangs über die ( i + 1 ) st entspricht. Es genügt, U σ i zu beschreiben, da U σ = U ϵ 1 σ a 1U ϵ m σ a m ist .ϵ1,ϵ2,,ϵm{±1}σiB2ni(i+1)UσiUσ=Uσa1ϵ1Uσamϵm

Um zu definieren , geben wir zunächst eine bestimmte Teilmenge der Standardbasis von C 2 2 n an, auf die U σ i nicht trivial einwirkt. Für ψ = | b 1 b 2b 2 n , lassen l i ' ( ψ ) = 1 + Σ i ' j = 1 ( - 1 ) 1 - B j . Nennen wir ψUσiC22nUσiψ=|b1b2b2ni(ψ)=1+j=1i(1)1bjψ zulässig, wenn für alle i { 1 , 2 , , 2 n } ist . (Dies entspricht ψ , das einen Pfad der Länge 2 n in dem im AJL-Papier definierten Graphen G k beschreibt .) Sei λ r = { sin ( π r / k ), wenn  1 r 1i(ψ)k1i{1,2,,2n}ψ2nGkSeiA=ie-πi/2k(dies ist im AJL-Papier falsch geschrieben; beachte auch, dass hier und nur hieri=√ ist

λr={sin(πr/k)if 1rk1,0otherwise.
A=ieπi/2k ist nicht der Indexi). Schreiben Sieψ=| ψibib i + 1, wobeiψidie ersteni-1Bits vonψsind undzi= i - 1 (ψi) sei. Dann ist U σ i ( | ψ i 00 )i=1iψ=|ψibibi+1ψii1ψzi=i1(ψi) Wir definierenU σ i (ψ)=ψfür nicht zulässige Basiselementeψ.
Uσi(|ψi00)=A1|ψi00Uσi(|ψi01)=(Aλzi1λzi+A1)|ψi01+Aλzi+1λzi1λzi|ψi10Uσi(|ψi10)=Aλzi+1λzi1λzi|ψi01+(Aλzi+1λzi+A1)|ψi10Uσi(|ψi11)=A1|ψi11
Uσi(ψ)=ψψ

UσinkUσii1zizikUσiUσi1zik1

Um es noch einmal zusammenzufassen:

  1. σB2nm
  2. σ=σa1ϵ1σa2ϵ2σamϵm
  3. i{1,2,,m}Uσaiϵi=1
  4. Uσ
  5. |101010
  6. σe2πi/k
Evan Jenkins
quelle
2

Sie haben fünf Artikel in der Frage erwähnt, aber ein Artikel, der nicht erwähnt wird, ist die experimentelle Implementierung im Jahr 2009 . Hier finden Sie die tatsächliche Schaltung, die zur Auswertung eines Jones-Polynoms verwendet wurde:

Geben Sie hier die Bildbeschreibung ein

Dies könnte der "vertrautere" Darstellung des Algorithmus am nächsten kommen, da das Interesse am Jones-Polynom und an DQC-1 seit 2009 etwas zurückgegangen ist.

Weitere Details zu diesem Experiment finden Sie in Gina Passantes These .

user1271772
quelle
1
Un
Bitte. Ja, dies war eine 4-seitige PRL mit Details, die nicht so ausführlich erklärt wurden, wie ich es gerne hätte - vielleicht gibt es auf der Webseite des Journals ein "ergänzendes Material", das das U besser erklärt. Das Jones-Polynom und DQC-1 waren zwischen 2008 und 2009 beliebt, aber ich habe seitdem aufgehört, davon zu hören.
user1271772