Apakah implementasi algoritma Shor 2016 benar-benar dapat diukur?

Dalam makalah Science 2016 " Realisasi algoritma Shal scalable " [ 1 ], penulis faktor 15 dengan hanya 5 qubit, yang lebih sedikit dari 8 qubit "diperlukan" menurut Tabel 1 dari [ 2 ] dan Tabel 5 dari [ 3 ] Persyaratan 8-qubit berasal dari akhir [ 4 ] yang menyatakan bahwa jumlah qubit yang diperlukan untuk anjak bit adalah yang untuk 15 adalah . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

Makalah yang hanya menggunakan 5 qubit menyatakan bahwa algoritme mereka "menggantikan QFT yang bekerja pada M qubit dengan QFT semiklasik yang berulangkali beraksi pada qubit tunggal", tetapi konsekuensi dari ini pada kompleksitas algoritme tidak pernah disebutkan dalam makalah.

Sekarang telah ada kritik keras terhadap makalah yang mengklaim faktor 15 dengan cara "scalable", seperti yang mereka katakan di Bagian 2 bahwa argumen kompleksitas untuk algoritma Shor tidak lagi berlaku. Namun, kritik ini belum dikuatkan di mana pun, dan makalah Science terus dipuji sebagai versi "scalable" dari algoritma Shor. Apa kompleksitas dari algoritma Shor "scalable"?

[ 1 ] Monz et al. (2016) Sains . Vol. 351, Edisi 6277, hlm. 1068-1070
[ 2 ] Smolin et al. (2013) Alam . 499, 163–165
[ 3 ] Dattani & Bryans (2014) arXiv: 1411.6758
[ 4 ] Zalka (2008) arXiv: quant-ph / 0601097
[ 5 ] Cao & Luo "Mengomentari: Realisasi algoritma Shor yang dapat diskalakan"

cc.complexity-theory ds.algorithms quantum-computing factoring security pengguna1271772
sumber

Tergantung pada apa yang Anda maksud dengan "scalable". Beberapa kritik terhadap Cao dan Liu tampaknya agak pilih-pilih. Misalnya, salah satu kritik mereka adalah bahwa Kitaev tidak mengklaim bahwa Anda hanya dapat menggunakan satu qubit di kertas yang dikutip untuk hasil ini. Mereka tampaknya tidak menyelidiki apakah klaim ini sendiri benar atau salah. Algoritme Kitaev sebenarnya dapat dimodifikasi untuk menggunakan hanya satu qubit, seperti yang dinyatakan makalah Science, meskipun klaim ini tampaknya tidak ada dalam makalah Kitaev pada algoritme-nya.

Peter Shor

@PeterShor, suatu kehormatan mendengar dari Anda! Ok jadi penulis (dengan benar) memperluas hasil dari makalah Kitaev untuk memungkinkannya dengan satu qubit, dan Cao & Liu mengeluh bahwa mereka menyebutnya "Algoritma Kitaev" daripada "Algoritma Kitaev yang dimodifikasi atau sesuatu seperti itu". Namun, mereka juga mengatakan bahwa argumen kompleksitas tidak lagi berlaku ketika QFT diubah menjadi "semi-klasik QFT". Saya masih mahasiswa ketika datang ke jenis analisis ini jadi saya akan sangat menghargai masukan. Apakah kompleksitasnya masih O (log n) ^ 3? Apakah masih "terukur" dalam hal polinomial, atau setidaknya <GNFS?

user1271772

Saya akan membiarkan orang lain menjawab ini, karena orang mungkin mengatakan saya bias. Tetapi izinkan saya menunjukkan bahwa penulis makalah Science tidak memperluas algoritma Kitaev ... itu adalah ekstensi terkenal. Mereka hanya tidak mengutip referensi yang benar.

Peter Shor

Rumus ini yang mencapai 8 qubit mengambil beberapa implementasi spesifik dari algoritma Shor dan menghitung berapa qubit yang dibutuhkan oleh implementasi. Mereka tidak mengklaim bahwa ini adalah implementasi terbaik.

Peter Shor

@ user1271772 Ini ditandai untuk perhatian moderat atas dasar Anda menjadi salah satu penulis yang disebutkan dalam pos Anda sendiri. Bukan berarti itu buruk, beberapa iklan diri adalah bagian dari ilmu pengetahuan yang tidak dapat dihindari, tetapi mungkin lebih baik untuk menjelaskannya?

Bjørn Kjos-Hanssen

Dorongan utama argumen Cao dan Luo adalah bahwa dalam varian algoritma yang diterapkan, register pertama — yang akhirnya berisi output — hanya berisi 1 bit. Dan jika Anda hanya mendapatkan 1 bit output dari algoritma, itu tidak cukup untuk faktorisasi. (Untuk satu hal, walaupun ini bukan argumen mereka, 1 bit jelas tidak mengandung informasi yang cukup untuk menentukan faktor-faktornya.)

$c$ $O(\log^3 N)$

Untuk mencoba bersikap adil kepada Cao dan Luo, mereka mengatakan bahwa mereka tidak berpikir algoritma ini berfungsi, dan jika itu bekerja, maka itu bukan algoritma Shor karena tidak persis cocok dengan algoritma yang dijelaskan dalam makalah anjak piutang asli . Kutipan dari makalah mereka:

Akhirnya, kami ingin menekankan bahwa jika implementasinya memang kredibel maka itu akan menjadi algoritma anjak kuantum baru, bukan algoritma Shor, karena semua persyaratan algoritma Shor asli tidak terpenuhi.

Dan memang, itu bukan algoritma dari makalah anjak piutang asli saya. Ia menggunakan prosedur estimasi fase dari algoritma factoring Kitaev, dan varian tentang itu, yang ditemukan oleh Griffiths dan Niu (bukan oleh Parker dan Plenio, seperti yang saya katakan di edit sebelumnya dari jawaban ini) yang memungkinkan algoritma menghasilkan estimasi fase sedikit demi sedikit.

Peter Shor
sumber

Tolong tunjukkan di mana di koran Cao dan Luo mereka mengatakan bahwa mengeluarkan sedikit demi sedikit mempengaruhi biaya operasi. Jika saya membaca makalah mereka dengan benar, mereka tidak. Saya pikir saya telah cukup membantah kritik mereka.

Peter Shor

c

$c$

x \cdot t

$x\cdot t$

t

$t$

Saya tidak akan melalui rangkaian untuk estimasi fase output satu-qubit dan menjelaskan mengapa perubahan yang relatif kecil yang diperlukan untuk mencapai hal ini tidak mempengaruhi kompleksitas waktu. Ini adalah "semi-klasik" modifikasi yang dijelaskan pada halaman 2 dari Parker dan Plenio ini kertas , faktorisasi Efisien dengan qubit murni tunggal dan log N qubit campuran .

Peter Shor

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

Seperti yang saya katakan, Anda harus membaca dan memahami makalahnya. Hitung sendiri jika Anda tidak mempercayai saya. Struktur dasar algoritma tidak berubah.

Peter Shor

Apakah implementasi algoritma Shor 2016 benar-benar dapat diukur?

Jawaban: