Jones Wielomian

12

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

DaftWullie
źródło

Odpowiedzi:

6

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.σkUσσB2nUσUσ

Jeśliσ 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 , ϵ 22nmσ=σa1ϵ1σa2ϵ2σamϵma1,a2,,am{1,2,,2n1} , 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 1U ϵ m σ a m .ϵ1,ϵ2,,ϵm{±1}σiB2ni(i+1)UσiUσ=Uσa1ϵ1Uσamϵ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 2b 2 n niech I ' ( ψ ) = 1 + Σ I ' j = 1 ( - 1 ), 1 - b j . Zadzwońmy do ψUσiC22nUσiψ=|b1b2b2ni(ψ)=1+j=1i(1)1bjψ 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 1i(ψ)k1i{1,2,,2n}ψ2nGkNiechA=ie-πi/2k(jest to źle wpisane w pracy AJL; zauważ także, że tu i tylko tutaj,i=

λr={sin(πr/k)if 1rk1,0otherwise.
A=ieπ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=1iψ=|ψibibi+1ψii1ψzi=i1(ψi) DefiniujemyU σ i (ψ)=ψdla niedopuszczalnych elementów podstawowychψ.
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(ψ)=ψψ

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-KitaevUσinkUσii1zizikaby 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 ik - 1 ).UσiUσi1zik1

Podsumowując:

  1. Początek oplotem z m przejściach.σ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
źródło
3

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:

wprowadź opis zdjęcia tutaj

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ą .

użytkownik1271772
źródło
1
Un
Nie ma za co. Tak, to był 4-stronicowy PRL ze szczegółami nie wyjaśnionymi tak dokładnie, jak bym chciał - może na stronie czasopisma znajduje się „Materiał uzupełniający”, który lepiej wyjaśnia U. Wielomian Jonesa i DQC-1 były popularne około 2008-2009, ale od tego czasu przestałem o tym słyszeć.
user1271772,