Tanya Jawab Quantum Excellence Luar Biasa

Dari sebuah blog oleh Scott Joel Aronson, Spesialis Ilmu dan Sistem Komputer, Dosen, Departemen Ilmu Komputer, Universitas Texas di Austin

Anda membaca kisah-kisah ini - di Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [ di Habr / sekitar. terjemahan.] atau di tempat lain - bahwa sekelompok peneliti di Google telah mencapai keunggulan komputasi kuantum dengan perangkat superkonduktor 53-qubit-nya. Mereka mudah ditemukan, tetapi saya tidak akan memberikan tautan kepada mereka - hanya karena mereka belum ada.

Dunia tahu bahwa Google benar-benar menyiapkan pengumuman besar keunggulan kuantum, yang harus keluar bersamaan dengan publikasi karya penelitian di salah satu jurnal ilmiah yang disegani. Dan ini kemungkinan akan terjadi dalam sebulan.

Sementara itu, NASA, yang berpartisipasi dalam pengembangan ini, secara tidak sengaja memposting versi lama Google di situs publik. Dia menghabiskan waktu singkat di sana, tetapi cukup untuk sampai ke Financial Times, kotak masuk saya dan jutaan tempat lainnya. Argumen tentang karya ini, tanpa fakta, diprediksi tersebar di mana-mana.

Rupanya, dunia kita telah kehilangan kesempatan untuk secara jelas mengumumkan momen baru "masuknya manusia ke ruang angkasa," di mana tesis Church-Turing yang kuat akan secara eksperimental ditolak di sebuah konferensi pers. Ini akan lebih seperti penerbangan Wright Bersaudara, rumor terpisah tentang yang muncul dalam interval dari 1903 ke 1908, di mana Wilbur dan Orville akhirnya setuju untuk penerbangan demonstrasi (hanya dalam kasus kami, untungnya, penjelasan masalah ini akan pergi ke tempat betapa sedikit waktu!)

Saya sudah mendapatkan informasi selama beberapa bulan; sangat sulit bagi saya untuk tidak menulis tentang ini di blog saya. Saya berjanji untuk diam, tetapi saya tidak bisa menahan keinginan untuk meninggalkan petunjuk yang berbeda di sana-sini - misalnya, selama pidato saya di acara terakhir yang didedikasikan untuk Paul Bernays , saya secara khusus merancang program kuliah saya sehingga mereka akan sampai pada titik ini.

Entri ini adalah pengumuman resmi yang mengkonfirmasi fakta-fakta ini. Dan jika kilat sudah terlihat oleh kami, maka hak untuk menyuarakan guntur milik sekelompok peneliti dari Google, serta waktu dan tempat untuk ini.

Alih-alih, saya memutuskan untuk mengklarifikasi pertanyaan ini, untuk menjernihkan informasi yang salah yang beredar di Internet dalam peran saya sebagai blogger dan "intelektual sosial", dan untuk menyajikan kepada Anda "Satu set pertanyaan dan jawaban yang sangat baik tentang keunggulan kuantum dari Scott". Kalau-kalau Anda tiba-tiba tertarik pada keunggulan kuantum, atau ingin tahu apa yang akan terjadi jika beberapa perusahaan mesin pencari dari Mountain View atau di tempat lain secara hipotetis mengumumkan pencapaian keunggulan kuantum .

Nah, jangan menarik ekor kucing:

Pertanyaan 1: Apa itu keunggulan komputasi kuantum?

Istilah ini sering disingkat menjadi kuantum superioritas (KP). Ini menunjukkan penggunaan komputer kuantum (QC) untuk memecahkan set masalah tertentu yang terdefinisi dengan baik, solusinya, dengan menggunakan algoritma yang dikenal saat ini pada komputer klasik yang ada saat ini, akan menerima pesanan yang lebih besar lagi - dan tidak hanya seperti itu, tetapi karena kompleksitas kuantum asimtotik. Penekanannya di sini adalah pada 100% yakin bahwa tugas sedang diselesaikan pada QC, dan itu benar-benar tidak dapat didekati dengan bantuan komputer klasik; Idealnya, tugas harus sedemikian rupa sehingga sudah dapat diselesaikan dalam waktu dekat (dengan bantuan berisik, bukan QC universal yang sudah ada atau akan segera muncul). Dan jika tugas ini masih bermanfaat, semakin baik - tetapi ini tidak perlu. Pesawat Wright Brothers atau Chicago Woodpile tidak berguna bagi mereka.

T2: Jika peneliti Google benar-benar mencapai HF, apakah ini berarti bahwa "kode apa pun dapat diretas," sebagai kandidat untuk kepresidenan dari Partai Demokrat AS, Andrew Young, baru-baru ini men-tweet?



Tidak benar (meskipun sebagai kandidat, Young cantik bagiku).

Ada dua masalah. Pertama, perangkat yang dibuat oleh Google, IBM, dan lainnya saat ini terdiri dari 50-100 qubit dan tidak memiliki sistem koreksi kesalahan. Untuk menjalankan algoritma Shore untuk memecahkan enkripsi RSA, diperlukan beberapa ribu qubit logis. Dan dengan metode koreksi kesalahan yang dikenal saat ini, ini dapat dengan mudah membutuhkan jutaan qubit fisik, dan kualitasnya lebih baik daripada yang ada. Saya tidak berpikir ada orang yang dekat dengan ini, dan kami tidak tahu berapa lama.

Kedua, bahkan di masa depan hipotetis, QC yang dapat diukur dengan koreksi kesalahan akan, seperti yang kita lihat sekarang, dapat memecahkan beberapa kode, tetapi tidak semua. Secara kebetulan, kunci publik yang dapat mereka crack meliputi sebagian besar kunci yang kita gunakan saat ini untuk keamanan Internet: RSA, protokol Diffie-Hellman, kurva elips, dll. Enkripsi kunci pribadi akan memiliki dampak minimal. Dan ada juga kandidat untuk sistem kunci publik (misalnya, berdasarkan ucapan terima kasih), metode peretasan yang belum diketahui siapa pun selama 20 tahun upaya di QC; selain itu, upaya telah dilakukan untuk beralih ke sistem tersebut. Rinciannya ada dalam surat saya kepada Rebecca Goldstein .

T3: Perhitungan apa, yang dianggap rumit secara klasik, yang Google rencanakan untuk lakukan, atau telah dilakukan?

Bisa saya katakan, meski saya malu. Perhitungannya adalah sebagai berikut: "tester" menghasilkan rangkaian kuantum acak C (urutan acak gerbang 1 qubit dan qubit kedua terdekat, kedalaman sekitar 20, pada kisi dua dimensi 50-60 qubit). Kemudian tester mengirim C ke komputer kuantum dan menginstruksikannya untuk menerapkan rangkaian ke keadaan awal semua-0, mengukur hasilnya dengan basis {0,1}, mengirim string n bit yang diamati, dan mengulanginya beberapa ribu atau juta kali. Akhirnya, menggunakan pengetahuannya tentang C, tester klasik menerapkan tes statistik untuk memverifikasi bahwa output mengkonfirmasi bahwa QC melakukan perhitungan.

Artinya, ini bukan tugas seperti anjak piutang, memiliki satu jawaban yang benar. Sirkuit C menghasilkan distribusi probabilitas, sebut saja DC, lebih dari string n bit, dan tugasnya adalah untuk menghasilkan sampel dari distribusi ini. Bahkan, 2 ⁿ baris akan berbicara mendukung D _C - dan akan ada banyak dari mereka yang jika QC bekerja sebagaimana mestinya, maka kita tidak akan pernah melihat output yang sama. Yang penting, distribusi DC tidak seragam. Beberapa garis akan mengalami gangguan amplitudo yang konstruktif, dan probabilitasnya akan lebih besar, sementara yang lain akan menderita gangguan destruktif, dan probabilitasnya akan lebih kecil. Dan meskipun kita akan melihat hanya beberapa sampel, jumlah yang dibandingkan dengan 2 ⁿ akan menjadi kecil, kita dapat memeriksa apakah mereka tertarik ke baris, yang kita anggap lebih mungkin, dan pada akhirnya ini akan meningkatkan kepercayaan diri kita bahwa sesuatu yang secara klasik tidak mungkin tercapai terjadi .

Sederhananya, KK hanya akan diminta untuk melakukan urutan operasi acak (tetapi diketahui) - bukan karena kita membutuhkan hasil yang spesifik, tetapi karena kita sedang mencoba untuk membuktikan bahwa itu bisa unggul dari komputer klasik dalam beberapa tugas yang jelas.

T4: Tetapi jika KK ada hanya untuk memberikan sampah acak, satu-satunya artinya adalah sulit untuk disimulasikan pada komputer klasik, lalu siapa yang peduli? Bukankah itu sandwich kaleng tanpa apa-apa?

Tidak. Seperti yang sudah saya tulis, ini bukan sandwich dengan semuanya sekaligus, tapi pasti sandwich dengan sesuatu!

Hormati besarnya topik yang dibahas, dan pencapaian teknik yang sangat rumit yang diperlukan untuk implementasinya. Sebelum CP muncul, skeptis mungkin bersenang-senang pada saat yang sama bahwa setelah semua miliaran dihabiskan dalam lebih dari 20 tahun, tidak ada satu pun QC yang pernah digunakan untuk menyelesaikan tugas yang akan ditangani lebih cepat daripada laptop Anda, atau setidaknya masalah tidak dapat diselesaikan dengan cara yang tergantung pada sifat kuantum komputer ini. Tetapi di dunia KP yang akan datang, ini sudah salah. Superposisi 2 ⁵⁰ atau 2 ⁶⁰ bilangan kompleks dikuasai secara komputasi, menggunakan waktu dan sumber daya yang kecil dibandingkan dengan ²⁵⁰ atau ²⁶⁰ .

Saya terus-menerus ingat pesawat Wright bersaudara karena saya dikejutkan oleh jurang pemisah antara apa yang kita bicarakan dan pengabaian di Internet dari semua sisi dengan topik ini. Ini mirip dengan reaksi seseorang yang sangat percaya bahwa tidak mungkin melakukan perjalanan yang berguna di udara, dan kemudian dia melihat pesawat baling-baling kayu yang menjulang di udara - tontonan ini tidak akan menyangkal pandangannya, tetapi tidak akan mendukungnya.

Sudahkah saya benar-benar khawatir selama bertahun-tahun bahwa hype konstan tentang tonggak penting yang dicapai oleh CC akan mengurangi kesabaran orang, dan mereka tidak akan peduli ketika sesuatu yang benar-benar berharga terjadi?

T5: Bertahun-tahun yang lalu, Anda mempermalukan massa karena terlalu memuji D-Wave dan pernyataannya tentang percepatan kuantum yang sangat besar dalam menyelesaikan masalah optimisasi melalui anil kuantum. Sekarang Anda malu dengan massa karena tidak dengan antusias mengagumi Partai Komunis. Kenapa kamu tidak memutuskan?

Karena tujuan saya bukan untuk memimpin "tingkat antusiasme" ke arah tertentu, tetapi untuk memastikan bahwa itu benar! Tidak bisakah Anda mengatakan, melihat ke belakang bahwa saya pada umumnya benar tentang D-Wave, bahkan ketika kritik saya terhadap topik ini membuat saya tidak populer di beberapa kalangan? Jadi soal KP, saya juga berusaha benar.

T6: Jika perhitungan yang terkait dengan KP hanya memperhitungkan sampel dari distribusi probabilitas, bagaimana saya bisa memverifikasi bahwa perhitungannya benar?

Untung kamu bertanya! Ini adalah pertanyaan tentang teori yang telah kami dan ilmuwan lain kembangkan selama dekade terakhir. Saya sudah menjelaskannya secara singkat di B3: perhitungan dapat diperiksa secara statistik dari sampel yang dikembalikan oleh QC, dan pastikan bahwa mereka lebih suka menambahkan "puncak" dari distribusi probabilitas D _C. Salah satu cara mudah untuk melakukan ini adalah apa yang Google sebut sebagai "pemeriksaan lintas-entropi linier": ini adalah untuk menjumlahkan Pr [C output s _i ] untuk semua sampel s ₁ , .., s _k yang dihasilkan QC, dan kemudian menyatakan cek berhasil jika jumlah ini keluar di luar batas tertentu - misalnya, bk / 2 ⁿ untuk konstanta 1 <b <2.

Tentu saja, untuk melakukan tes ini, perlu untuk menghitung probabilitas Pr [C output s _i ] pada komputer klasik - dan satu-satunya cara untuk melakukan ini adalah menghabiskan waktu 2 ^{n secara} mendalam. Apakah ada masalah dengan ini? Tidak, jika n = 50, dan Anda adalah Google, dan Anda dapat memproses angka seperti ²⁵⁰ (meskipun Anda tidak dapat mengatasi 2 ¹⁰⁰⁰ , angka yang melebihi googol - ha, ha). Dengan meluncurkan sekelompok kernel klasik di suatu tempat selama sebulan, Anda pada akhirnya akan dapat mengkonfirmasi keluarnya QC Anda dengan benar, yang dikeluarkannya dalam beberapa detik - dan pada saat yang sama bahwa QC bekerja banyak pesanan dengan magnitude lebih cepat. Namun, ini juga berarti bahwa percobaan CP berbasis sampel dirancang untuk perangkat 50-qubit yang mereka buat hari ini. Dan bahkan dengan seratus qubit, kita tidak akan dapat mengkonfirmasi hasil QC, bahkan menggunakan semua kekuatan komputasi planet ini.

Saya menekankan bahwa masalah ini khas untuk percobaan dengan sampel yang mirip dengan yang kami lakukan sekarang. Jika algoritme Shore memfaktorkan sejumlah 2000 digit, kami akan dengan mudah memeriksa ini dengan hanya mengalikan faktor yang dihasilkan dan memeriksa apakah itu milik primes. Atau, jika CC digunakan untuk mensimulasikan biomolekul kompleks, kita dapat menguji operasinya dalam sebuah eksperimen.

T7: Tunggu sebentar. Jika komputer klasik dapat memverifikasi hasil percobaan di KP hanya dalam mode simulasi percobaan (meskipun lambat), lalu bagaimana ini bisa menjadi "keunggulan kuantum"?

Ayo kamu. Dengan keping 53 qubit, cukup logis untuk mengharapkan akselerasi beberapa juta kali dalam mode di mana Anda masih dapat langsung memeriksa hasil kerja, dan juga melihat bahwa akselerasi tumbuh secara eksponensial dengan peningkatan jumlah qubit - seperti yang diprediksi oleh analisis asimtotik.

T8: Apakah ada bukti matematis bahwa tidak ada algoritma klasik cepat yang akan menyalip eksperimen KP dengan pengambilan sampel?

Tidak hari ini Tapi ini bukan kesalahan peneliti KP! Para ahli dalam ilmu komputer teoretis bahkan tidak dapat membuktikan hipotesis yang paling sederhana, seperti P ≠ NP atau P ≠ PSPACE, jadi Anda tidak boleh berharap bahwa akan ada kemungkinan untuk mengecualikan kehadiran simulasi klasik yang cepat. Kami hanya bisa berharap untuk kompleksitas bersyarat. Dan kami benar-benar membuktikan beberapa hasil ini . Masalah teoritis terbesar di bidang ini adalah bukti hasil terbaik dari kompleksitas bersyarat.

T9: Apakah kerangka sampling itu sendiri memiliki kegunaan yang bermanfaat?

Ketika memikirkan topik ini untuk pertama kalinya, orang biasanya percaya bahwa jawaban yang jelas untuk pertanyaan ini adalah "tidak" (dan saya adalah salah satunya). Namun belakangan ini, situasinya telah berubah - misalnya, berkat protokol keacakan terkonfirmasi saya, yang menunjukkan bagaimana percobaan dengan CP dengan pengambilan sampel dapat dengan sangat cepat berubah menjadi generator bit, suatu keacakan yang dapat dibuktikan kepada pengamat pihak ketiga yang skeptis (di bawah beberapa asumsi komputasi). Dan ini berpotensi diterapkan pada pembuatan cryptocurrency PoS dan protokol kriptografi lainnya. Saya berharap bahwa dalam waktu dekat aplikasi yang lebih banyak akan ditemukan.

T10: Jika eksperimen KP hanya menghasilkan bit acak, apakah itu menarik? Apakah ini bukan tugas sepele untuk mengubah qubit menjadi bit acak hanya dengan mengukurnya?

Intinya adalah bahwa percobaan dengan KP tidak menghasilkan bit acak yang seragam. Dia membuat pilihan dari beberapa distribusi probabilitas berkorelasi kompleks pada garis 50-bit atau 60-bit. Dalam protokol keacakan yang dikonfirmasi, penyimpangan dari homogenitas memainkan peran sentral dalam bagaimana CP dapat meyakinkan skeptis klasik bahwa bit benar-benar acak dan tidak memiliki sistem rahasia (seperti generator angka pseudo-acak).

T11: Tetapi apakah sudah puluhan tahun percobaan mekanika kuantum - misalnya, percobaan yang melanggar ketidaksetaraan Bell - belum menunjukkan KP?

Ini hanya kebingungan dalam hal. Eksperimen-eksperimen itu menunjukkan "superioritas kuantum" jenis lain. Misalnya, dalam kasus pelanggaran ketidaksetaraan Bell, itu adalah "superioritas korelasi kuantum". Itu tidak menunjukkan keunggulan komputasi, yaitu, sesuatu yang tidak dapat disimulasikan pada komputer klasik (terlepas dari kenyataan bahwa simulasi klasik tidak akan memiliki batasan pada lokalitas spasial atau sesuatu seperti itu). Saat ini, orang biasanya berarti keunggulan komputasi kuantum oleh KP.

T12: Ya, tetapi ada banyak contoh bahan dan reaksi kimia yang sulit untuk disimulasikan secara klasik, serta simulator kuantum khusus (misalnya, kelompok Lukin dari Harvard). Mengapa mereka tidak dianggap sebagai contoh KP?

Dengan beberapa definisi, mereka dapat dianggap sebagai contoh KP! Perbedaan utama antara karya peneliti Google adalah bahwa perangkat mereka sepenuhnya dapat diprogram - dapat diprogram ke dalam urutan sewenang-wenang gerbang 2-qubit dengan tetangga terdekat, cukup mengirim sinyal yang diperlukan dari komputer kuantum.

Dengan kata lain, skeptis-KP tidak dapat lagi mendengus bahwa, kata mereka, jika ada sistem kuantum yang sulit untuk disimulasikan secara klasik, itu hanya karena alam sulit untuk disimulasikan, dan kita tidak dapat secara sewenang-wenang mengubah senyawa kimia acak yang kita temukan di alam, oleh karena itu, sistem ini tidak dapat dianggap "komputer yang mensimulasikan diri mereka sendiri." Dengan definisi yang masuk akal, perangkat superkonduktor yang dibuat oleh Google, IBM, dan perusahaan lain saat ini adalah komputer sungguhan.

T13: Sudahkah Anda menemukan konsep superioritas kuantum?

Tidak. Saya memainkan peran dalam definisinya, itulah sebabnya Sabina Hossenfelder dan yang lainnya menghubungkan saya dengan peran yang terlalu besar dalam ide ini. Istilah "keunggulan kuantum" diciptakan oleh John Preskill pada tahun 2012, meskipun dalam beberapa hal konsep kunci tanggal kembali ke awal komputasi kuantum sendiri pada awal 1980-an. Pada tahun 1994, menggunakan algoritma Shore untuk memperhitungkan jumlah besar menjadi eksperimen nyata di bidang KP - meskipun masalah ini terlalu sulit untuk dipecahkan hari ini.

Inti dari gagasan itu, yang justru untuk menunjukkan CP menggunakan masalah pengambilan sampel, sejauh yang saya tahu, pertama kali diusulkan oleh Barbara Theral dan David Divincenzo dalam sebuah karya visioner tahun 2002. Upaya "modern" untuk mengorganisasi eksperimen dimulai pada 2011, ketika Alex Arkhipov dan saya menerbitkan karya kami di BosonSampling, dan Bremner, Josa, dan Shepherd menerbitkan karya kami tentang orang Hamilton yang beralih. Karya-karya ini menunjukkan tidak hanya bahwa "sederhana", bukan sistem kuantum universal dapat menyelesaikan masalah yang tampaknya rumit dengan pengambilan sampel, tetapi juga bahwa algoritma klasik yang efektif untuk masalah ini akan menyebabkan runtuhnya hierarki polinomial . Arkhipov dan saya juga mengambil langkah pertama untuk membuktikan bahwa versi perkiraan masalah pengambilan sampel kuantum pun bisa rumit secara klasik.

Sejauh yang saya tahu, ide "pengambilan sampel acak rangkaian" - yaitu, menghasilkan masalah pengambilan sampel yang kompleks melalui pemilihan urutan katup 2-qubit acak dalam arsitektur superkonduktor - muncul dalam korespondensi email yang saya mulai pada Desember 2015, di mana John juga berpartisipasi Martinis, Hartmut Niven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Josa, Aram Harrow, Greg Cooperberg, dan lain-lain. Korespondensi itu disebut "masalah pengambilan sampel 40 qubit yang sulit", dan surat saya mulai dengan kata-kata "maaf untuk spam". Saya membahas beberapa kelebihan dan kekurangan dari tiga opsi untuk menunjukkan KP dengan pengambilan sampel: (1) kontur acak, (2) beralih Hamiltonians, (3) BosonSampling. Setelah Cooperberg membela opsi pertama, konsensus cepat terbentuk di antara para peserta,bahwa opsi pertama memang yang terbaik dari sudut pandang teknik - dan bahwa jika analisis teoritis yang ada untuk (1) tidak cukup, maka kita dapat menemukan sesuatu.

Setelah itu, sebuah kelompok dari Google melakukan sejumlah besar analisis sampel kontur acak, baik teoritis dan numerik, dan Lijie Chen dan Buland dan rekan-rekan saya menyajikan bukti dari berbagai jenis untuk kompleksitas klasik masalah.

T14: Jika KP tercapai, apa artinya ini bagi orang yang skeptis?

Saya tidak ingin berada di tempat mereka! Mereka dapat pindah ke posisi di mana KP dimungkinkan (dan siapa bilang itu tidak mungkin? Mereka tentu saja tidak!), Dan koreksi kesalahan kuantum selalu menjadi masalah nyata. Dan banyak dari mereka benar-benar mendukung posisi khusus ini. Tetapi yang lain, termasuk teman saya Gil Kalay, di sini di sebuah posting blog, berpendapat bahwa KP tidak dapat dicapai karena alasan mendasar. Dan saya tidak akan membiarkan mereka keluar.

T15: Apa selanjutnya?

Mencapai KP berarti bahwa grup Google telah memiliki peralatan yang diperlukan untuk menunjukkan protokol saya untuk menghasilkan bit acak yang dikonfirmasi. Dan ini benar-benar salah satu hal pertama yang kami rencanakan untuk dilakukan.

Tonggak nyata berikutnya yang jelas adalah penggunaan QC yang dapat diprogram dengan 50-100 qubit untuk simulasi kuantum yang berguna (misalnya, sistem keadaan terkondensasi) yang lebih cepat daripada metode klasik yang dikenal. Tonggak nyata kedua yang jelas adalah demonstrasi penggunaan koreksi kesalahan kuantum sehingga qubit yang dikodekan hidup lebih lama dari qubit fisik yang mendasarinya. Tidak ada keraguan bahwa Google, IBM dan pemain lain akan berlomba untuk berjuang untuk kedua tonggak ini.

Setelah menerbitkan artikel itu, Steve Girwin mengingatkan saya bahwa kelompok dari Yale telah mencapaikoreksi kesalahan kuantum, meskipun dalam sistem bosonik, dan bukan dalam sistem qubit superkonduktor. Jadi, mungkin, tonggak berikutnya dirumuskan lebih baik sebagai berikut: mencapai keunggulan komputasi kuantum dan koreksi kesalahan kuantum yang berguna dalam satu sistem.