Pomoc algorytmu faktoringu Shora

Mam mały problem z pełnym zrozumieniem ostatnich kroków algorytmu faktoringu Shora.

Biorąc pod uwagę którą chcemy uwzględnić, wybieramy losowy który ma porządek . $N$ $x$ $r$

Pierwszy krok obejmuje skonfigurowanie rejestrów i zastosowanie operatora Hadamard. W drugim kroku stosuje się operator liniowy. Trzeci krok jest mierzony drugim rejestrem (uważam, że ten krok można wykonać później). Czwarty krok dyskretna transformata Fouriera jest stosowana do pierwszego rejestru. Następnie mierzymy pierwszy rejestr.

Oto, gdzie jestem trochę zamglony:

Dostajemy pomiar w formie . $\mid j , x^k \textrm{mod} N \rangle$

Z tego możemy znaleźć zbieżności ułamka , zbieżności są możliwymi wartościami rzędu. Czy po prostu wypróbowujemy wszystkie zbieżnościa jeśli nie znajdziemyjako jednego ze zbieżności, to zaczynamy od nowa? $\frac{j}{2^q}$ $r$ $< N$ $r$

W jaki sposób różni się prawdopodobieństwo dla możliwych wartości ? Sądzę, że widzę, że wszyscy powinni mieć takie samo prawdopodobieństwo, ale artykuł Shora mówi, że tak nie jest? $j$

Tylko trochę zdezorientowany, ponieważ niektóre dokumenty wydają się mówić różne rzeczy.

Dzięki.

quantum-computing Callum
źródło

@Peter Shor może nawet ci w tym pomóc.

Dave Clarke

Od czasu zadawania tych pytań myślę, że lepiej to rozumiem. Aby wyjaśnić tym, którzy są zainteresowani, otrzymujemy pomiar w postaci gdzie potrzebujemy tylko . Wartość można zapisać jako , dzieląc przez otrzymujemy i z tego możemy znaleźć jej zbieżności, mianownik zbieżności jest możliwą wartością , jeżeli to nie algorytm jest uruchamiany ponownie. Prawdopodobieństwo znalezienia zależy od sumy, która zależy od wartości i okresu .

∣ j, x^{k} \mod N ⟩

$\mid j , x^k \mod N \rangle$

j

$j$

j

$j$

j = 2^{q} k / r

$j= 2^q k/ r$

2^{q}

$2^q$

k / r

$k/r$

< N

$< N$

r

$r$

j

$j$

2^{q}

$2^q$

r

$r$

Callum

Odpowiedzi:

Z tego możemy znaleźć zbieżności ułamka , zbieżności są możliwymi wartościami rzędu Czy po prostu wypróbowujemy wszystkie zbieżności a jeśli nie znajdziemy jako jednego ze zbieżności, to zaczynamy od nowa? $j/2^q$ $r.$ $<N$ $r$

Mógłbyś; algorytm działa dość szybko, jeśli to zrobisz. Jeśli chcesz zmniejszyć oczekiwaną liczbę kroków kwantowych, możesz również wykonać inne testy; na przykład powinieneś sprawdzić, czy jest małą wielokrotnością jednego ze zbieżności. Ale jeśli nie znajdziesz po tych rozszerzonych testach, musisz zacząć od nowa. $r$ $r$

W jaki sposób różni się prawdopodobieństwo dla możliwych wartości ? Sądzę, że widzę, że wszyscy powinni mieć takie samo prawdopodobieństwo, ale artykuł Shora mówi, że tak nie jest? $j$

Nie wiem, czy mogę ci w tym pomóc, ponieważ nie dostarczyłeś mi wystarczającej ilości informacji, aby wyjaśnić, dlaczego jesteś zdezorientowany. Prawdopodobieństwo dla każdej wartości we frakcji jest (bardzo prawie) takie samo. Jednak w zależności od tego, gdzie dokładnie mieści się między sąsiednimi wartościami i , prawdopodobieństwo określonych wartości różni się. $k$ $k/r$ $k/r$ $j/2^q$ $(j+1)/2^q$ $j$

Peter Shor
źródło

Podoba mi się to, jak określasz ten artykuł jako „papier Shora” :)

Suresh Venkat,

Nie jestem pewien, jak działa prawdopodobieństwo. Czy mam rację mówiąc, że . W przykładach, które widziałem, istniała symetria rozkładu prawdopodobieństwa w środkowej części osi , czy zawsze tak jest? Załóżmy, że , oznacza to, że dla wszystkich możliwych wartości , gdzie , wszystkie będą miały jednakowe prawdopodobieństwo z ? Dzięki.

Prob (j) = \frac{1}{2^{q} \times ([\frac{2^{q} - k - 1}{r}] + 1)} | \sum_{a = 0}^{[\frac{2^{q} - k - 1}{r}]} e^{- 2 π i r j a / 2^{q}} |^{2}

$\textrm{Prob} (j) = \frac{1}{2^q \times ([ \frac{2^q - k -1}{r}]+1)} \Bigg| \sum^{[ \frac{2^q - k -1}{r}]}_{a=0} e^{ -2 \pi i rja/2^q } \Bigg| ^2$

x

$x$

r = 2^{t}

$r= 2^t$

j = \frac{k_{0} 2^{q}}{r}

$j= \frac{ k_0 2^q}{r}$

k_{0} = 0, \dots, r - 1

$k_0 = 0, \cdots , r-1$

j

$j$

\frac{1}{2^{t}}

$\frac{1}{2^t}$

Callum,

Jeśli , to rzeczywiście wszystkie możliwe wartości będą miały równe prawdopodobieństwo .

r = 2^{t}

$r=2^t$

j

$j$

1 / 2^{t}

$1/2^t$

Peter Shor,