Jones Wielomian

Istnieje wiele dość standardowych algorytmów kwantowych, które można zrozumieć w bardzo podobnych ramach, od algorytmu Deutscha, problemu Simona, wyszukiwania Grovera, algorytmu Shora i tak dalej.

Jednym z algorytmów, który wydaje się zupełnie inny, jest algorytm do oceny wielomianu Jonesa . Co więcej, wydaje się, że jest to kluczowy algorytm do zrozumienia w tym sensie, że jest to problem kompletny z BQP : wykazuje pełną moc komputera kwantowego. Ponadto, dla wariantu problemu, jest on kompletny DQC-1 , tzn. Wykazuje pełną moc jednego czystego kubita .

Artykuł algorytmu Jones Polynomial przedstawia algorytm w zupełnie inny sposób niż inne algorytmy kwantowe. Czy istnieje bardziej podobny / znany sposób, w jaki mogę zrozumieć algorytm (konkretnie jednostkowy w wariancie DQC-1, czy tylko cały obwód w wariancie kompletnym BQP)?$U$

Ta odpowiedź jest mniej więcej streszczeniem artykułu Aharonova-Jonesa-Landaua, z którym się łączyłeś, ale wszystko, co nie jest bezpośrednio związane z definiowaniem algorytmu, zostało usunięte. Mam nadzieję, że jest to przydatne.

Algorytm Aharonova-Jonesa-Landaua aproksymuje wielomian Jonesa zamknięcia plat warkocza w tym rdzeniu jedności, realizując go jako (pewne przeskalowanie) elementu macierzy pewnej jednolitej macierzy , obraz o pod pewnym jednolitą reprezentację grup oplot . Biorąc pod uwagę implementację jako obwodu kwantowego, przybliżenie jej elementów macierzy jest proste przy użyciu testu Hadamarda . Część nietrywialna przybliża jako obwód kwantowy.$\sigma$$k$$U_\sigma$$\sigma$$B_{2n}$$U_\sigma$$U_\sigma$

Jeśli$\sigma$ jest oplot na nici z m przejściach można napisać σ = σ ε 1 1 σ ε 2 2 ⋯ σ ε m do m , gdzie 1 , 2 , ... , m ∈ { 1 , 2 , … , 2 n - 1 } , ϵ 1 , ϵ $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\}$ , a σ i jest generatorem B 2 n, który odpowiada przecięciu i- tej nici nad ( i + 1 ) o . Wystarczy opisać U σ i , ponieważ U σ = U ϵ 1 σ a 1 ⋯ U ϵ m σ a m .$\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}$

Aby zdefiniować , najpierw podajemy pewien podzbiór standardowej podstawy C 2 2 n, na który U σ i działa nietypowo. Dla ψ = | b 1 b 2 ⋯ b 2 n ⟩ niech ℓ I ' ( ψ ) = 1 + Σ I ' j = 1 ( - 1 ), 1 - b j . Zadzwońmy do $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$ dopuszczalne, jeżeli dla wszystkich i ′ ∈ { 1 , 2 , … , 2 n } . (Odpowiada to ψ opisując ścieżkę o długości 2 n na wykresie G k zdefiniowanym w pracy AJL.) Niech λ r = { sin ( π r / k ), jeśli  1 ≤ r $1 \leq \ell_{i'}(\psi) \leq k - 1$$i' \in \{1, 2, \ldots, 2n\}$$\psi$$2n$$G_k$NiechA=ie-πi/2k(jest to źle wpisane w pracy AJL; zauważ także, że tu i tylko tutaj,i=

$$\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}$ nie jest indeksemi). Napiszψ=| ψibib i + 1 ⋯⟩, gdzieψijest pierwszymii-1bitamiψ, i niechzi=ℓ i - 1 (ψi). Następnie 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)$ DefiniujemyU σ i (ψ)=ψdla niedopuszczalnych elementów podstawowychψ. $$\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$

Chcielibyśmy teraz opisać jako obwód kwantowy z wielomianowo wieloma bramkami (w n i k ). Zauważ, że chociaż U σ i zmienia tylko dwa kubity, to zależy również od pierwszych kubitów i - 1 poprzez zależność od z i (i faktycznie zależy od wszystkich kubitów dla wymogu dopuszczalności). Możemy jednak uruchomić licznik, aby obliczyć i zapisać z i (a także określić dopuszczalność danych wejściowych) w logarytmicznie wielu kubitach ancilla (w k ), a zatem możemy zastosować algorytm Solovay-Kitaev$U_{\sigma_i}$$n$$k$$U_{\sigma_i}$$i - 1$$z_i$$z_i$$k$aby uzyskać dobre przybliżenie do używając tylko wielomianowo wielu bramek. (Artykuł apeluje do Solovay-Kitaev dwukrotnie: raz do zwiększenia licznika na każdym kroku i raz do zastosowania U σ i ; nie jestem pewien, czy istnieje bardziej bezpośredni sposób opisania któregokolwiek z nich jako obwodów kwantowych ze standardowymi bramkami W artykule nie wspomina się również o potrzebie sprawdzenia dopuszczalności; nie jestem pewien, czy jest to ważne, ale na pewno potrzebujemy co najmniej 1 ≤ z i ≤ k - 1 ).$U_{\sigma_i}$$U_{\sigma_i}$$1 \leq z_i \leq k - 1$

Podsumowując:

1. Początek oplotem z m przejściach.$\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}$

W pytaniu wspomniano o pięciu artykułach, ale jednym z nich, który nie został wspomniany, jest eksperymentalna realizacja w 2009 roku . Tutaj znajdziesz rzeczywisty obwód, który został użyty do oceny wielomianu Jonesa:

Może to być najbliżej „bardziej znanej” prezentacji algorytmu, ponieważ zainteresowanie wielomianem Jonesa i DQC-1 nieco spadło od 2009 roku.

Więcej szczegółów na temat tego eksperymentu można znaleźć w Giny Passante za tezą .