Beberapa hari yang lalu sebuah draft artikel dari Google tentang pencapaian keunggulan kuantum dalam komputer kuantum superkonduktor bocor ke jaringan. Teks itu sendiri dengan cepat dihapus, dan rumor dan asumsi, termasuk yang salah, berlipat ganda di sekitarnya. Penulis posting ini adalah
Profesor Scott Aaronson , salah satu spesialis terkemuka dalam algoritma kuantum, dan memiliki blog yang luar biasa. Dalam posting terakhir, dia menjawab pertanyaan utama tentang superioritas kuantum.
Dari penerjemah. Saya sama sekali bukan spesialis dalam kompleksitas algoritme dan khususnya algoritma kuantum. Tetapi pos itu bagi saya terlalu menarik untuk tidak membahasnya di Habré, dan untuk kesalahan dalam hal penggunaannya yang tidak biasa, tolong tendang saya di PM.
Anda telah melihat cerita - di
Financial Times ,
Technology Review ,
CNET , Facebook, Reddit, Twitter, atau di tempat lain - yang berbicara tentang grup dari Google yang mencapai keunggulan kuantum dengan komputer superkonduktor 53-qubit. Kisah-kisah ini mudah ditemukan, saya tidak akan melampirkannya di sini, karena belum ada satupun yang ada.
Seperti yang diketahui seluruh dunia sekarang, Google sebenarnya menyiapkan pernyataan besar tentang keunggulan kuantum, yang direncanakan bersama dengan artikel ilmiah di majalah keren (yang mana? Pilihannya kecil - satu dari dua). Saya harap ini terjadi dalam sebulan.
Sementara itu, NASA, tempat beberapa penulis artikel itu bekerja, secara tidak sengaja menerbitkan versi lama artikel itu di situs publik. Dia ada di sana untuk waktu yang singkat, tetapi cukup lama berada di
Financial Times, surat-suratku
, dan jutaan tempat lainnya. Spekulasi tanpa fakta tentang maknanya diperkirakan akan berlipat ganda.
Tampaknya dunia telah kehilangan momen murni "pendaratan di bulan", di mana tesis Gereja-Thuring yang luas dihancurkan oleh bukti eksperimental selama konferensi pers. Ini akan lebih seperti penerbangan saudara-saudara Wright - tentang mana rumor dan kebenaran setengah merembes ke ruang publik antara 1903 dan 1908, ketika Will dan Orville akhirnya memutuskan untuk menunjukkan penerbangan mereka. (Kali ini, untungnya, semuanya akan diklarifikasi lebih cepat!)
Posting ini bukan pernyataan resmi atau konfirmasi apa pun. Meskipun baut kilat sudah terlihat, guntur milik grup dari Google, dalam waktu dan tempat pilihan mereka.
Sebaliknya, saya ingin menghentikan aliran informasi yang keliru dan menawarkan di sini, sebagai blogger dan "intelektual publik," FAQ Supremasi Kuantum Tertinggi Scott saya. Anda tahu, jika Anda tiba-tiba ingin tahu tentang keunggulan kuantum atau selalu ingin tahu apa yang akan terjadi jika tiba-tiba beberapa perusahaan pencarian dari Mountain View atau dari tempat lain secara hipotetis menyatakan bahwa keunggulan kuantum telah tercapai.
Tanpa basa-basi lagi, ini dia:
B1. Apa keunggulan komputasi kuantum?Seringkali direduksi menjadi sekadar "keunggulan kuantum," istilah ini merujuk pada penggunaan komputer kuantum untuk memecahkan serangkaian masalah khusus, solusi yang pada komputer klasik menggunakan algoritma yang dikenal akan menerima pesanan besar lebih lama - dan bukan karena alasan acak, tetapi dari karena kompleksitas kuantum asimptotik. Penekanannya di sini adalah pada kepastian yang mungkin bahwa masalahnya benar-benar diselesaikan dengan cara kuantum dan benar-benar tidak dapat dicapai secara klasik, dan idealnya itu akan memungkinkan kita untuk mencapai percepatan perhitungan dalam waktu dekat (dengan komputer kuantum berisik dan non-universal yang sudah kita miliki disana atau akan segera). Jika tugas itu juga berguna untuk sesuatu, itu jauh lebih baik, tetapi itu tidak perlu. Pesawat Wright dan tumpukan kayu Fermi tidak berguna bagi mereka sendiri.
B2. Jika Google benar-benar telah mencapai keunggulan kuantum, apakah ini berarti bahwa sekarang tidak ada kode crack , seperti Andrew Young, seorang kandidat untuk kepresidenan AS, baru-baru ini ditutup?Tidak, itu tidak (walaupun saya masih suka pencalonan Young).
Ada dua masalah. Pertama, perangkat yang dibuat oleh Google, IBM dan lainnya memiliki 50-100 qubit, dan tidak ada koreksi kesalahan. Meretas RSA menggunakan algoritma Shore akan membutuhkan beberapa ribu qubit logis. Dengan metode koreksi kesalahan yang terkenal, jutaan qubit fisik, dan kualitas yang lebih baik dari yang kita miliki sekarang, dapat dengan mudah diperlukan untuk ini. Sepertinya saya tidak ada yang dekat dengan ini, dan kami tidak tahu seberapa cepat mereka akan bisa dekat dengan ini.
Dan masalah kedua adalah bahwa bahkan di masa depan hipotetis QC dengan koreksi kesalahan, kita akan dapat memecahkan hanya beberapa kode, tetapi tidak semua, setidaknya sejauh yang kita tahu sekarang. Secara kebetulan, kunci publik yang dapat di-crack mencakup sebagian besar algoritma yang kami gunakan untuk mengamankan Internet: RSA, Diffie-Hellman, kriptografi elips, dll. Tetapi kriptografi berdasarkan kunci privat seharusnya tidak terpengaruh. Dan ada juga cryptosystems untuk kunci publik (misalnya, berdasarkan ucapan terima kasih) yang tidak ada yang tahu cara memecahkan menggunakan QC bahkan setelah 20 tahun mencoba, dan ada upaya untuk beralih ke sistem ini. Sebagai contoh, lihat
surat saya
kepada Rebecca Goldstein .
B3. Perhitungan seperti apa yang Google rencanakan untuk lakukan (atau telah dilakukan), yang dianggap rumit secara klasik.Tentu saja, saya dapat memberitahu Anda, tetapi saya merasa bodoh pada saat yang sama. Perhitungannya adalah ini: eksperimen menghasilkan rangkaian kuantum acak C (yaitu, urutan acak 1-qubit dan 2-qubit - antara tetangga terdekat - gerbang, dengan kedalaman 20, misalnya, bekerja pada jaringan 2D n = 50-60 qubit). Setelah itu, eksperimen mengirim C ke komputer kuantum, dan memintanya untuk menerapkan C ke keadaan awal 0, mengukur hasilnya dalam basis {0,1}, mengirim kembali urutan n-bit yang dapat diamati (string) dan mengulangi beberapa ribu atau juta kali. Akhirnya, dengan menggunakan pengetahuannya tentang C, peneliti melakukan pemeriksaan statistik pada kepatuhan hasil dengan output yang diharapkan dari komputer kuantum.
Tugas ini bukan salah satu tugas dengan satu-satunya jawaban yang benar, tidak seperti faktorisasi angka. Hasil operasi skema C ternyata menjadi distribusi statistik (sebut saja D
C ) di atas string n-bit, dari mana kita perlu memilih sampel. Bahkan, biasanya DC dapat sesuai dengan 2
n garis - begitu banyak sehingga jika QC bekerja seperti yang diharapkan, itu tidak akan pernah menghasilkan garis yang sama dalam output dua kali. Adalah penting bahwa distribusi DC tidak seragam. Beberapa garis muncul sebagai akibat gangguan konstruktif amplitudo dan oleh karena itu memiliki probabilitas yang lebih tinggi, dan yang lain sebagai akibat dari destruktif, dan memiliki probabilitas yang lebih rendah. Dan meskipun kami hanya mendapatkan sebagian kecil dari semua sampel 2
n yang mungkin, kami dapat memeriksa distribusi sampel ini secara statistik untuk kesesuaian dengan distribusi yang tidak merata yang diharapkan, dan memastikan bahwa kami mendapatkan sesuatu yang sulit direproduksi secara klasik.
TL; DR, komputer kuantum diminta untuk menerapkan urutan acak (tetapi diketahui) operasi kuantum - bukan karena kami tertarik pada hasilnya, tetapi karena kami berusaha membuktikan bahwa QC dapat melakukan tugas yang jelas ini lebih baik daripada komputer klasik.
B4. Tetapi jika komputer kuantum hanya menjalankan beberapa kode sampah, yang tujuannya hanya untuk menyulitkan simulasi klasik, siapa yang peduli? Bukankah itu over-pie besar dengan ... tidak ada apa-apa?Tidak. Ini, tentu saja, bukan kue dengan segala yang enak, tapi setidaknya kue dengan sesuatu.
Setidaknya hormati sedikit atas besarnya apa yang kita bicarakan di sini dan jenis rekayasa genius yang diperlukan untuk menerjemahkan ini menjadi kenyataan. Sebelum kuantum superioritas (KP), skeptis KP hanya tertawa bahwa bahkan setelah miliaran dolar dan 20 + tahun kerja, komputer kuantum masih tidak dapat melakukan sesuatu yang lebih cepat daripada laptop Anda. Setidaknya tidak menggunakan kuantum. Setelah mencapai supremasi kuantum di dunia, mereka tidak lagi tertawa. Superposisi 2
50 atau 2
60 bilangan kompleks dihitung menggunakan sumber daya waktu dan volume data yang jauh lebih kecil daripada
250 atau
260Saya berbicara tentang pesawat Wright hanya karena kesenjangan antara apa yang kita bicarakan dan penolakan, sesuatu yang saya lihat di berbagai bagian Internet, benar-benar tidak dapat dipahami. Seolah-olah Anda percaya bahwa pada prinsipnya tidak mungkin terbang, dan kemudian Anda melihat pesawat kayu yang tipis - mungkin tidak mengguncang keyakinan Anda, tetapi tentu saja tidak seharusnya menguatkannya.
Apakah saya benar,
khawatir bertahun-tahun yang lalu bahwa hype terus-menerus tentang prestasi KK yang jauh lebih kecil akan membuat orang lelah dan mereka akan peduli ketika sesuatu yang benar-benar berharga akhirnya terjadi?
B5. Bertahun-tahun yang lalu, Anda menyalahkan massa karena antusiasme mereka terhadap D-Wave dan klaim mereka tentang keunggulan kuantum yang menakjubkan dalam masalah optimasi menggunakan anil kuantum. Sekarang Anda mencela mereka karena kurangnya antusiasme terhadap superioritas kuantum. Kenapa kau begitu berubah-ubah?Karena tujuan saya bukan untuk menggeser tingkat antusiasme ke arah yang jelas dipilih, tetapi untuk menjadi benar. Kalau dipikir-pikir, bukankah saya terutama benar tentang D-Wave, bahkan ketika pernyataan saya membuat saya sangat tidak populer di beberapa kalangan? Nah, sekarang saya mencoba untuk menjadi benar tentang keunggulan kuantum juga.
B6. Jika perhitungan superioritas kuantum hanya didasarkan pada sampel dari distribusi probabilitas, bagaimana seseorang dapat memverifikasi bahwa mereka dibuat dengan benar?Terima kasih sudah bertanya! Inilah tepatnya topik di mana saya dan orang lain telah mengembangkan banyak landasan teoretis dalam sepuluh tahun terakhir. Saya sudah memberi tahu versi singkat dalam jawaban saya B3: Anda menguji ini dengan menjalankan tes statistik pada sampel yang diberikan komputer kuantum untuk memverifikasi bahwa mereka terkonsentrasi di sekitar puncak distribusi probabilitas acak D
C. Salah satu cara mudah untuk melakukan ini, yang oleh Google disebut "uji lintas-entropi linier", adalah dengan menjumlahkan semua Pr [C menghasilkan s
i ] untuk semua sampel s
1 , ..., s
k bahwa KK dikembalikan, dan kemudian menyatakan pengujiannya berhasil jika dan hanya jika jumlahnya melebihi tingkat tertentu - katakanlah, bk / 2
n , di mana b adalah konstan antara 1 dan 2.
Jujur, untuk menerapkan tes ini, Anda harus menghitung semua probabilitas Pr [C memberikan s] pada komputer klasik - dan satu-satunya cara yang diketahui untuk melakukan ini adalah beralih lebih dari ~ 2
n . Tetapi apakah itu mengganggu siapa pun? Tidak, jika n = 50, dan Anda google dan Anda dapat menghitung angka seperti 2
50 (meskipun Anda tidak akan mendapatkan 2
1000 , yang lebih unggul dari
google , khe-khe). Setelah mengusir sekelompok besar core klasik selama, katakanlah, sebulan, Anda akan berakhir dengan hasil bahwa CC diproduksi dalam beberapa detik - pada saat yang sama, pastikan bahwa CC adalah beberapa pesanan lebih cepat. Namun demikian, ini berarti bahwa eksperimen berdasarkan pengambilan sampel hampir secara khusus dirancang untuk perangkat dengan ~ 50 qubit. Bahkan dengan 100 qubit, kami tidak tahu bagaimana memastikan hasilnya bahkan menggunakan semua daya komputasi yang tersedia di Bumi.
(Saya mencatat secara terpisah bahwa masalah ini hanya khusus untuk eksperimen pengambilan sampel, mirip dengan apa yang sedang dilakukan sekarang. Jika Anda menggunakan algoritme Shor untuk memfaktorkan angka 2000 digit, Anda dapat dengan mudah memeriksa hasilnya dengan hanya mengalikan semua faktor dan memeriksa kesederhanaannya. Tepatnya jika KK digunakan untuk mensimulasikan biomolekul kompleks, Anda dapat memeriksa hasilnya dengan bereksperimen dengan molekul.)
B7. Tunggu sebentar. Jika komputer klasik hanya dapat memverifikasi hasil percobaan pada superioritas kuantum hanya dalam mode di mana komputer klasik masih dapat mensimulasikan percobaan (walaupun sangat lambat), bagaimana seseorang dapat berbicara tentang "keunggulan kuantum"?Baiklah kalau begitu kamu. Dengan chip 53-qubit, Anda melihat akselerasi beberapa juta kali, dan Anda masih dapat memverifikasi hasilnya dan juga memverifikasi bahwa akselerasi tumbuh secara eksponensial dengan jumlah qubit, seperti yang diprediksi oleh analisis asimptotik. Ini tidak signifikan.
B8 Adakah bukti matematis bahwa tidak ada komputer klasik cepat yang dapat mengalahkan hasil percobaan KP berdasarkan pengambilan sampel?Tidak saat ini. Tapi ini bukan kesalahan para peneliti dari keunggulan kuantum! Selama ahli teori tidak dapat membuktikan bahkan hipotesis dasar, seperti P ≠ NP atau P ≠ PSPACE, dan tanpa ini kita tidak dapat tanpa syarat mengecualikan kemungkinan simulasi klasik yang cepat. Yang terbaik yang bisa kita harapkan adalah kompleksitas bersyarat. Dan kami memiliki beberapa hasil tentang ini, misalnya, artikel tentang
boson sampling atau
artikel oleh Bouldand et al. tentang # P-kompleksitas rata-rata menghitung amplitudo dari rangkaian acak, atau
artikel saya
dengan Lijie Chen ("Yayasan Kompleksitas-Teoretik Eksperimen Supremasi Kuantum"). Pertanyaan terbuka paling penting dalam bidang ini, menurut pendapat saya, adalah bukti kesulitan bersyarat terbaik.
B9. Apakah ada gunanya untuk pengambilan sampel keunggulan kuantum?Sampai baru-baru ini, jawabannya jelas tidak! (Dan saya tahu, karena saya sendiri adalah salah satu dari orang-orang seperti itu). Namun baru-baru ini, situasinya telah berubah - misalnya, berkat protokol
keacakan bersertifikat saya, yang menunjukkan bagaimana KP berdasarkan pengambilan sampel dapat digunakan secara independen untuk menghasilkan bit yang dapat dibuktikan secara acak bahkan untuk pihak ketiga yang skeptis (dengan asumsi tentang perhitungan). Ini pada gilirannya memiliki aplikasi dalam cryptocurrency dan protokol kriptografi lainnya. Saya harap lebih banyak aplikasi seperti itu segera hadir.
B10. Jika eksperimen tentang keunggulan kuantum menghasilkan bit acak, mengapa ini menarik? Apakah tidak mungkin untuk secara sepintas mengubah qubit menjadi bit acak hanya dengan mengukurnya?Intinya adalah bahwa QC menghasilkan bit acak yang tidak terdistribusi secara merata. Alih-alih, ia menciptakan seleksi dari beberapa distribusi probabilitas terkorelasi yang kompleks pada string 50-60 bit. Dalam protokol saya, penyimpangan dari keseragaman memainkan peran sentral dalam bagaimana QC meyakinkan skeptis bahwa dia benar-benar memilih bit acak daripada menggunakan semacam generator pseudo-acak secara rahasia.
B11. Pernahkah beberapa dekade percobaan mekanika kuantum, misalnya, dengan pelanggaran ketimpangan Bell, tidak menunjukkan keunggulan kuantum?Ini adalah pertanyaan yang sepenuhnya leksikal. Eksperimen-eksperimen tersebut menunjukkan tipe superioritas kuantum lain: misalnya, dalam kasus ketidaksetaraan Bell, mereka dapat disebut "superioritas korelasi kuantum". Mereka tidak menunjukkan keunggulan komputasi kuantum, yaitu kemampuan untuk menemukan sesuatu yang tidak dapat diakses oleh komputer klasik (di mana simulasi klasik tidak memiliki batasan spasial secara lokal, dll.). Saat ini, ketika orang menggunakan ungkapan "keunggulan kuantum", yang mereka maksudkan adalah keunggulan komputasi kuantum.
B12. Meski begitu, tidak ada contoh bahan dan reaksi kimia yang tak terhitung jumlahnya yang sulit untuk disimulasikan secara klasik, dan simulator kuantum yang dibangun secara khusus (seperti yang ada dalam kelompok Lukin di Harvard). Mengapa mereka tidak dianggap sebagai keunggulan komputasi kuantum?Dalam definisi beberapa orang, mereka dianggap! Perbedaan utama dengan komputer Google adalah bahwa mereka memiliki komputer yang sepenuhnya dapat diprogram - Anda dapat memasukkan urutan sewenang-wenang dari gerbang 2-qubit (untuk qubit tetangga) dengan hanya memasukkan perintah dari komputer klasik.
Dengan kata lain, skeptis KP tidak dapat lagi secara sembrono memperhatikan bahwa, tentu saja, sistem kuantum sulit untuk disimulasikan secara klasik, tetapi ini hanya karena alam umumnya sulit untuk disimulasikan, dan Anda tidak dapat memprogram ulang molekul acak yang ditemukan di lapangan ke komputer untuk mensimulasikan dirinya sendiri. dirimu sendiri. Dengan definisi apa pun yang masuk akal, perangkat superkonduktor yang dibuat oleh Google, IBM, dan lainnya adalah komputer dalam arti kata yang lengkap.
B13 Apakah Anda (Scott Aaronson) menemukan konsep keunggulan kuantum?Tidak. Saya memainkan peran dalam perkembangannya, dan karena itu, misalnya, Sabina Hosenfelder, antara lain,
secara keliru menghubungkan kepenulisan dari seluruh gagasan itu kepada
saya . Istilah "keunggulan kuantum" diusulkan oleh John Preskill pada tahun 2012, meskipun dalam arti tertentu, ide dasarnya muncul pada awal kontribusi kuantum di awal tahun 80-an. Pada tahun 1994, menggunakan algoritma Shore untuk memfaktisasi sejumlah besar menjadi percobaan utama untuk menguji superioritas kuantum, meskipun saat ini ini masih terlalu sulit untuk diproduksi.
Gagasan utama bahwa pengambilan sampel dapat digunakan sebagai gantinya adalah, sejauh yang saya tahu, pertama kali diusulkan oleh Barbara Terhal dan David DiVincenzo dalam
sebuah artikel tahun 2002. Upaya saat ini pada CP sampel dimulai sekitar tahun 2011, ketika Alex Arkhipov dan saya menerbitkan artikel kami tentang
pengambilan sampel bosonik, dan Bremner, Jozsa, dan Shepherd secara independen menerbitkan
sebuah artikel tentang model-model perjalanan orang Hamilton . Artikel-artikel ini menunjukkan tidak hanya "sederhana", bukan sistem kuantum universal yang dapat memecahkan masalah pengambilan sampel yang jelas kompleks, tetapi juga bahwa keberadaan algoritma klasik yang efektif akan berarti penurunan
hierarki polinomial . Arkhipov dan saya juga meletakkan dasar untuk argumen bahwa bahkan versi perkiraan pengambilan sampel kuantum bisa rumit secara klasik.
Sejauh yang saya tahu, gagasan "sirkuit pengambilan sampel acak" —yaitu, menghasilkan masalah pengambilan sampel yang kompleks dengan secara acak memilih urutan gerbang 2-qubit di, katakanlah, arsitektur superkonduktor - korespondensi mereka muncul, yang saya mulai pada Desember 2015, termasuk John Martinis, Hartmut Neven , Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg, dan lainnya. Utas itu berjudul "Masalah Penentuan Sampel dengan 40 Qubit," dan surat itu dimulai dengan "Maaf atas spam."
Di dalamnya, saya membahas berbagai keuntungan dan kerugian dari tiga opsi untuk menunjukkan keunggulan kuantum menggunakan sampling: (1) sirkuit acak, (2) komuter Hamiltonians, (3) boson sampling. Setelah Greg Cooperberg membela opsi (1), sebuah konsensus dengan cepat menyatakan bahwa (1) akan benar-benar menjadi pilihan terbaik dari sudut pandang teknik, dan bahwa jika kita belum memiliki justifikasi teoretis yang memuaskan untuk (1), kita dapat entah bagaimana dapat menyiasati ini.Setelah itu, tim Google melakukan pekerjaan yang hebat untuk menganalisis skema pengambilan sampel acak, baik secara teoritis maupun numerik, sementara Lijie Chen dan I dan Bouland et al. memberikan bukti berbeda dari kompleksitas klasik dari masalah ini dari sudut pandang teori kompleksitas.B14. Jika superioritas kuantum tercapai, apa artinya ini bagi orang yang skeptis?Wow, saya tidak ingin berada di tempat mereka sekarang! Mereka mungkin kembali pada posisi yang, yah, tentu saja, superioritas kuantum adalah mungkin (dan siapa yang mengatakan sebaliknya? Yah, tentu saja tidak!), Dan seluruh kesulitan selalu dalam koreksi kesalahan kuantum. Dan faktanya, ada yang mengatakannya sejak awal. Dan yang lain, teman baik saya Gil Kalai, di antara mereka, dengan menulis, tepat di blog ini, meramalkan bahwa keunggulan kuantum tidak akan pernah tercapai karena alasan mendasar. Sekarang mereka tidak akan kacau.B15. Jadi apa selanjutnya?Jika ini benar-benar mencapai keunggulan kuantum, maka saya pikir grup Google memiliki semua perangkat keras untuk menunjukkan protokol saya untuk pembuatan bit acak tersertifikasi. Dan ini sebenarnya salah satu dari hal-hal berikut dalam rencana mereka.Dan di samping itu, langkah nyata berikutnya adalah menggunakan QC yang dapat diprogram, dengan 50-100 qubit untuk beberapa simulasi kuantum yang berguna (misalnya, sistem dengan keadaan materi terkondensasi) jauh lebih cepat daripada metode klasik. Dan langkah kedua yang jelas adalah menunjukkan penggunaan koreksi kesalahan untuk menjaga agar qubit logis tetap hidup lebih lama dari umur qubit fisik yang menjadi dasarnya. Tidak ada keraguan bahwa IBM, Google dan para pemain lainnya akan saling mengejar untuk mendapatkan keunggulan dalam langkah-langkah ini.