Algoritma pemfaktoran Shor membantu

Saya mengalami sedikit kesulitan untuk sepenuhnya memahami langkah-langkah terakhir dari algoritma anjak piutang Shor.

Diberikan ingin kita faktor, kita memilih acak yang memiliki urutan . $N$ $x$ $r$

Langkah pertama melibatkan pengaturan register dan menerapkan operator Hadamard. Langkah kedua diterapkan operator linier. Langkah ketiga register kedua diukur (saya percaya langkah ini bisa dilakukan nanti). Langkah keempat transformasi Fourier diskrit diterapkan ke register pertama. Kemudian kita mengukur register pertama.

Di sinilah aku agak kabur:

Kami mendapatkan pengukuran dalam bentuk . $\mid j , x^k \textrm{mod} N \rangle$

Dari ini kita dapat menemukan konvergensi fraksi , konvergensi adalah nilai yang mungkin dari urutan . Di sini kita hanya mencoba semua konvergensi dan jika kita tidak menemukan sebagai salah satu konvergensi, kita mulai lagi? $\frac{j}{2^q}$ $r$ $< N$ $r$

Juga bagaimana perbedaan untuk nilai yang mungkin berbeda? Menurutku mereka semua harus memiliki probabilitas yang sama, tetapi surat kabar Shor mengatakan ini bukan masalahnya? $j$

Hanya sedikit bingung karena beberapa makalah tampaknya mengatakan hal yang berbeda.

Terima kasih.

quantum-computing Callum
sumber

@ Peter Shor bahkan mungkin membantu Anda dengan yang ini.

Dave Clarke

Sejak mengajukan pertanyaan ini saya pikir saya memiliki pemahaman yang lebih baik tentang itu. Untuk memperjelas bagi mereka yang tertarik, kami mendapatkan pengukuran dalam bentuk

di mana semua yang kita perlu adalah

. Nilai

dapat ditulis sebagai

dengan membaginya dengan

kita mendapatkan

dan dari sini kita dapat menemukan konvergennya, penyebutnya

dari konvergen adalah nilai yang mungkin dari

, jika itu bukan algoritma yang dijalankan lagi. Kemungkinan menemukan

didasarkan pada jumlah yang tergantung pada nilai

dan apa periode

∣ 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

Jawaban:

Dari sini kita dapat menemukan konvergensi fraksi , konvergensi adalah nilai yang mungkin dari ordo Di sini kita hanya mencoba semua konvergensi dan jika kita tidak menemukan sebagai salah satu konvergensi, kita mulai lagi? $j/2^q$ $r.$ $<N$ $r$

Anda bisa; Algoritma bekerja cukup cepat jika Anda melakukannya. Jika Anda ingin mengurangi jumlah langkah kuantum yang diharapkan, Anda juga bisa melakukan beberapa tes lain; misalnya Anda harus memeriksa apakah adalah kelipatan kecil dari salah satu konvergensi. Tetapi jika Anda tidak menemukan setelah tes yang diperpanjang ini, Anda harus memulai lagi. $r$ $r$

Juga bagaimana perbedaan untuk nilai yang mungkin berbeda? Menurutku mereka semua harus memiliki probabilitas yang sama, tetapi surat kabar Shor mengatakan ini bukan masalahnya? $j$

Saya tidak tahu apakah saya bisa lebih membantu Anda dengan ini, karena Anda belum memberi saya informasi yang cukup untuk saya tahu mengapa Anda bingung. Probabilitas untuk setiap nilai dalam fraksi adalah (sangat hampir) sama. Namun, tergantung di mana tepatnya berada di antara nilai-nilai yang berdekatan dari dan , probabilitas nilai-nilai spesifik berbeda. $k$ $k/r$ $k/r$ $j/2^q$ $(j+1)/2^q$ $j$

Peter Shor
sumber

Saya suka bagaimana Anda menyebut kertas itu sebagai "kertas Shor" :)

Suresh Venkat

Saya hanya sedikit tidak yakin tentang cara kerja probabilitas itu saja. Apakah saya benar mengatakan bahwa

. Dalam contoh yang saya lihat ada simetri pada distribusi probabilitas tentang titik tengah dari

-axis, apakah ini selalu terjadi? Misalkan

, apakah ini berarti bahwa untuk semua kemungkinan nilai

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$

, di mana

, semua

akan memiliki probabilitas yang sama dengan

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$

? Terima kasih.

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

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

Callum

Jika

, maka sesungguhnya semua nilai yang mungkin dari

akan memiliki probabilitas yang sama

r = 2^{t}

$r=2^t$

j

$j$

1 / 2^{t}

$1/2^t$

Peter Shor