Integer apa yang telah difaktorkan dengan algoritma Shor?

Algoritma Shor diharapkan memungkinkan kita untuk memfaktorkan bilangan bulat jauh lebih besar daripada yang bisa dilakukan pada komputer klasik modern.

Saat ini, hanya bilangan bulat yang lebih kecil yang difaktorkan. Sebagai contoh, makalah ini membahas faktorisasi . $15=5{\times}3$

Dalam hal ini, apa yang paling mutakhir dalam penelitian? Apakah ada makalah baru-baru ini di mana dikatakan beberapa angka yang lebih besar telah difaktorkan?

shors-algorithm Berbaring Penari
sumber

Terkait erat, tetapi bukan duplikat persis: Manakah angka tertinggi yang difaktorkan oleh QC dalam eksperimen non-spesifik?

agaitaarino

Jawaban:

Faktorisasi utama 21 (7x3) tampaknya merupakan yang terbesar yang dilakukan saat ini dengan algoritma Shor; itu dilakukan pada 2012 sebagaimana dirinci dalam makalah ini . Perlu dicatat, bagaimanapun, bahwa angka yang jauh lebih besar, seperti 56.153 pada tahun 2014, telah diperhitungkan menggunakan algoritma minimisasi, seperti yang dijelaskan di sini . Untuk referensi yang mudah, lihat Tabel 5 dari makalah ini :

{\begin{matrix} Table 5: Quantum factorization records \\ \begin{array}{cccccc} Number & # of factors & \begin{matrix} # of qubits \\ needed \end{matrix} & Algorithm & \begin{matrix} Year \\ implemented \end{matrix} & \begin{matrix} Implemented \\ without prior \\ knowledge of \\ solution \end{matrix} \\ 15 & 2 & 8 & Shor & 2001 [2] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2009 [5] & χ \\ 2 & 8 & Shor & 2012 [6] & χ \\ 21 & 2 & 10 & Shor & 2012 [7] & χ \\ 143 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 56153 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 291311 & 2 & 6 & minimization & not yet & ✓ \\ 175 & 3 & 3 & minimization & not yet & ✓ \end{array} \end{matrix}}_{.}

$\begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}}$

heather
sumber

@SqueamishOssifrage: Di mana dikatakan algoritma minimalisasi "terbatas pada angka yang faktor-faktornya diketahui hubungan membuat ruang pencarian jauh lebih kecil, seperti berbeda hanya dalam posisi sedikit atau berbeda dalam semua tetapi beberapa posisi"?

user1271772

N

$N$

O (\log^{2} N)

$O(\log^2 N)$

\log N

$\log N$

@SqueamishOssifrage: "dengan menghilangkan variabel oleh hubungan yang diketahui antara bit faktor" Apakah Anda setuju bahwa Persamaan. 1 dari arxiv.org/pdf/1411.6758.pdf menyiratkan bahwa z12 = 0, tanpa ada hubungan "diketahui" antara bit? Apakah Anda setuju bahwa Anda dapat menyimpulkan bahwa z12 = 0 untuk p1, p2, q1, q2 yang berubah-ubah? Berikutnya: Jumlah variabel (qubit) dalam metode tabel adalah

\log (N)

$\log(N)$ tidak

\log^{2} N

$\log^2 N$ . Masalahnya dapat diselesaikan pada annealer dengan

\log (N)

$\log(N)$ qubit jika interaksi sewenang-wenang 4-qubit diizinkan. Jika hanya interaksi 2-qubit yang diizinkan, Anda perlu

\log^{2} N

$\log^2 N$ .

user1271772

@SqueamishOssifrage: "tidak ada makalah yang saya baca tampaknya melakukan upaya untuk memperkirakan pertumbuhan waktu untuk solusi sebagai fungsi dari jumlah qubit". Yang ini berusaha: journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.220405 Tetapi "waktu untuk solusi" bukanlah yang penting, itu adalah upaya yang diperlukan. Pengayakan GNF itu mudah tetapi langkah matriksnya sangat rumit. Melakukan algoritma Shor dengan cara yang optimal cukup rumit. Algoritma minimisasi sederhana.

user1271772

@SqueamishOssifrage: Finally: "Note that the minimization algorithm is limited to numbers whose factors have known relations" .. no part of the algorithm is limited to "known" relations. The algorithm does not assume anything about the factors. No relations. The bits are all unknown variables that are determined by minimization. The minimization can be done with fewer qubits for some numbers than others. The same is true for Shor's algorithm. The same is true for GNFS. In fact if the number you want to factor is even, it is rather easy to factor it.

user1271772

Untuk algorthm Shor : Keadaan seni masih 15 . Untuk "faktor" 21 di koran Heather menyebutkan, mereka harus menggunakan fakta itu $21=7\times 3$ untuk memilih basis mereka $a$ . Ini dijelaskan pada tahun 2013 di koran Berpura-pura nomor faktor pada komputer kuantum , kemudian diterbitkan oleh Nature dengan judul yang sedikit lebih ramah . Komputer kuantum tidak faktor 21, tetapi itu memverifikasi bahwa faktor 7 dan 3 memang benar.

Untuk algoritma anil : Keadaan terkini adalah 376289 . Tapi kita tidak tahu bagaimana skala ini. Batas atas yang sangat kasar untuk jumlah qubit yang diperlukan untuk faktor RSA-230 adalah 5,5 miliar qubit (tetapi ini dapat diturunkan secara signifikan oleh kompiler yang lebih baik), sementara algoritma Shor dapat melakukannya dengan 381 qubit .

pengguna1271772
sumber

Anda akan melihat di tabel dalam jawaban saya ada kolom untuk "diimplementasikan tanpa sepengetahuan sebelumnya solusi" ada "x" untuk semua implementasi algoritma shor, membuat saya percaya bahwa hal yang sama berlaku untuk anjak 15.

heather

Ukuran angka yang diperhitungkan bukanlah ukuran yang baik untuk kompleksitas masalah faktorisasi, dan juga kekuatan algoritma kuantum. Ukuran yang relevan lebih baik berupa periodisitas dari fungsi yang dihasilkan yang muncul dalam algoritma.

Ini dibahas dalam J. Smolin, G. Smith, A. Vargo: Berpura-pura memberi faktor sejumlah besar pada komputer kuantum , Nature 499, 163-165 (2013) . Secara khusus, penulis juga memberikan contoh angka dengan 20.000 digit biner yang dapat difaktorkan dengan komputer kuantum dua-qubit, dengan implementasi yang persis sama yang telah digunakan sebelumnya untuk faktor nomor lainnya.

Perlu dicatat bahwa "penyederhanaan manual" yang dilakukan penulis untuk sampai pada algoritma kuantum ini adalah sesuatu yang juga telah dilakukan misalnya untuk anjak percobaan awal 15.

Norbert Schuch
sumber