Jones Polynom

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$

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.$\sigma$$k$$U_\sigma$$\sigma$$B_{2n}$$U_\sigma$$U_\sigma$

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$\sigma$$2n$$m$$\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$$a_1, a_2, \ldots, a_m \in \{1, 2, \ldots, 2n - 1\}$ 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 1 ⋯ U ϵ m σ a m ist .$\epsilon_1, \epsilon_2, \ldots, \epsilon_m \in \{\pm 1\}$$\sigma_i$$B_{2n}$$i$$(i + 1)$$U_{\sigma_i}$$U_\sigma = U_{\sigma_{a_1}}^{\epsilon_1} \cdots U_{\sigma_{a_m}}^{\epsilon_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 2 ⋯ b 2 n ⟩ , lassen l i ' ( ψ ) = 1 + Σ i ' j = 1 ( - 1 ) 1 - B j . Nennen wir $U_{\sigma_i}$$\mathbb{C}^{2^{2n}}$$U_{\sigma_i}$$\psi = \lvert b_1 b_2 \cdots b_{2n} \rangle$$\ell_{i'}(\psi) = 1 + \sum_{j = 1}^{i'} (-1)^{1-b_j}$$\psi$ 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 $1 \leq \ell_{i'}(\psi) \leq k - 1$$i' \in \{1, 2, \ldots, 2n\}$$\psi$$2n$$G_k$SeiA=ie-πi/2k(dies ist im AJL-Papier falsch geschrieben; beachte auch, dass hier und nur hieri=

$$\lambda_r = \begin{cases}\sin(\pi r / k) & \textrm{if $1 \leq r \leq k - 1$},\\ 0 & \textrm{otherwise.}\end{cases}$$ $A = ie^{-\pi 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 = \sqrt{-1}$$i$$\psi = \lvert \psi_i b_i b_{i+1} \cdots\rangle$$\psi_i$$i - 1$$\psi$$z_i = \ell_{i-1}(\psi_i)$ Wir definierenU σ i (ψ)=ψfür nicht zulässige Basiselementeψ. $$\begin{align} U_{\sigma_i}(\lvert\psi_i 00 \cdots\rangle) & = A^{-1}\lvert\psi_i 00 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 01 \cdots \rangle) & = \left( A\frac{\lambda_{z_i-1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 01 \cdots\rangle + A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 10 \cdots \rangle) & = A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 01 \cdots\rangle + \left(A\frac{\lambda_{z_i+1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 11 \cdots\rangle) & = A^{-1}\lvert\psi_i 11 \cdots\rangle \end{align}$$ $U_{\sigma_i}(\psi) = \psi$$\psi$

$U_{\sigma_i}$$n$$k$$U_{\sigma_i}$$i - 1$$z_i$$z_i$$k$$U_{\sigma_i}$$U_{\sigma_i}$$1 \leq z_i \leq k - 1$

Um es noch einmal zusammenzufassen:

1. $\sigma \in B_{2n}$$m$
2. $\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$
3. $i \in \{1, 2, \ldots, m\}$$U_{\sigma_{a_i}}$$\epsilon_i = -1$
4. $U_{\sigma}$
5. $\lvert 1010 \cdots 10\rangle$
6. $\sigma$$e^{2\pi i/k}$

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:

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 .