Cara mengubah komputer kuantum menjadi generator angka acak sempurna

Kebetulan murni dan dapat diverifikasi sulit ditemukan. Dua kalimat baru menunjukkan bagaimana membuat pabrik angka acak dari komputer kuantum.

Ucapkan "keunggulan kuantum" pada setiap pertemuan ilmuwan komputer, dan Anda mungkin akan melihat mereka memutar mata mereka. Frasa ini merujuk pada gagasan bahwa komputer kuantum akan segera melewati batas, di luar itu mereka akan dapat melakukan tugas yang sangat sulit bagi komputer klasik dengan relatif mudah. Dan hingga baru-baru ini, tugas-tugas ini dianggap kurang bermanfaat untuk aplikasi nyata - karenanya memutar mata.

Tapi sekarang prosesor Google dikatakan dekat dengan tujuan itu, superioritas kuantum segera mungkin memiliki penggunaan penting: menghasilkan keacakan murni.

Keacakan adalah penting untuk hampir semua yang terjadi dalam komputasi dan infrastruktur komunikasi. Secara khusus, ini digunakan untuk mengenkripsi data yang melindungi segalanya dari percakapan biasa hingga transaksi keuangan dan rahasia negara.

Keacakan nyata yang dikonfirmasi - bayangkan sebagai properti yang ada dalam urutan angka dan membuatnya tidak mungkin untuk memprediksi nomor berikutnya dalam urutan - sangat sulit ditemukan.

Tetapi situasi ini dapat berubah ketika komputer kuantum menunjukkan keunggulannya. Tugas-tugas pertama ini, yang sejak awal hanya harus menunjukkan keunggulan teknologi, juga dapat memberikan kebetulan yang disertifikasi. "Kami senang menyambut ini," kata John Martinis , seorang fisikawan di Universitas California, Santa Barbara, yang menjalankan proyek komputasi kuantum di Google. "Kami berharap ini akan menjadi penggunaan pertama komputer kuantum."

Keacakan dan entropi

Keacakan dan teori kuantum berjalan beriringan seperti guntur dan kilat. Dalam kedua kasus, yang pertama adalah konsekuensi yang tak terhindarkan dari yang terakhir. Di dunia kuantum, sistem sering dikatakan sebagai kombinasi dari beberapa negara - yang disebut "Superposisi". Ketika Anda mengukur suatu sistem, itu "runtuh" ​​menjadi salah satu dari keadaan ini. Dan sementara teori kuantum memungkinkan Anda untuk menghitung probabilitas apa yang akan Anda temukan dalam suatu pengukuran, hasil pastinya akan selalu acak secara fundamental.

Fisikawan telah mempelajari hubungan ini untuk membuat generator bilangan acak. Mereka semua mengandalkan pengukuran semacam superposisi kuantum. Dan meskipun untuk sebagian besar metode menghasilkan angka acak yang dibutuhkan orang, sistem ini sudah cukup, mungkin sulit untuk bekerja dengan mereka. Selain itu, sangat sulit untuk membuktikan kepada orang skeptis tentang keacakan sebenarnya dari generator angka acak ini. Akhirnya, beberapa metode yang paling efektif untuk menghasilkan keacakan terkonfirmasi membutuhkan desain canggih dari beberapa perangkat yang dipisahkan oleh jarak yang sangat jauh.


Google AI Lab Memperkenalkan Bristlecone 72-Qubit Quantum Processor Pada tahun 2018

Satu proposal baru-baru ini untuk mengekstrak keacakan dari hanya satu perangkat - komputer kuantum - menggunakan apa yang disebut. tugas pengambilan sampel, yang akan menjadi salah satu tes pertama keunggulan kuantum. Untuk memahaminya, bayangkan Anda diberi sekotak ubin. Pada setiap ubin ada beberapa unit dan beberapa nol - 000, 010, 101 dan seterusnya.

Jika hanya ada tiga bit, maka ada delapan opsi yang memungkinkan. Namun, mungkin ada beberapa salinan dari setiap ubin di dalam kotak. Mungkin ada 50 ubin berlabel 010 dan 25 ubin berlabel 001. Distribusi ubin menentukan kemungkinan bahwa Anda secara tidak sengaja mengeluarkan ubin tertentu. Dalam kasus kami, Anda dapat menarik ubin 010 dengan probabilitas dua kali lebih tinggi dari ubin 001.

Tugas pengambilan sampel mencakup algoritma komputer yang setara dengan menarik ubin secara acak dari kotak dengan distribusi ubin tertentu. Semakin tinggi probabilitas yang ditentukan untuk ubin apa pun dalam distribusi, semakin besar kemungkinan algoritma akan menarik ubin itu.

Tentu saja, algoritme tidak mengeluarkan ubin nyata dari kotak nyata. Itu hanya secara acak menghasilkan jumlah biner panjang 50 bit, setelah menerima distribusi yang menentukan probabilitas yang diinginkan untuk masing-masing garis kemungkinan panjang 50 bit.

Untuk komputer klasik, kompleksitas tugas ini tumbuh secara eksponensial dengan peningkatan jumlah bit dalam sebuah string. Tetapi untuk komputer kuantum, tugas tersebut diperkirakan akan tetap kurang lebih sama untuk kedua 5 bit dan 50.

Komputer kuantum dimulai dengan mengatakan bahwa semua bit kuantumnya - qubit - berada dalam keadaan tertentu. Misalkan mereka semua mulai dengan 0. Bagaimana komputer klasik dapat bekerja dengan bit klasik menggunakan apa yang disebut. gerbang logika, dan komputer kuantum memanipulasi qubit menggunakan persamaan kuantumnya, gerbang kuantum.

Namun, gerbang kuantum dapat menempatkan qubit dalam kondisi aneh. Misalnya, satu jenis gerbang dapat menempatkan qubit yang dimulai dengan nilai 0 dalam superposisi 0 dan 1. Jika Anda kemudian mengukur keadaan qubit, itu secara acak akan runtuh ke 0 atau 1 dengan probabilitas yang sama.

Bahkan yang lebih aneh, gerbang kuantum yang dapat bekerja dengan dua atau lebih qubit pada saat yang sama dapat menyebabkan qubit menjadi saling terjerat. Dalam kasus ini, status qubit saling terkait sehingga sekarang semua qubit ini dapat dijelaskan hanya menggunakan satu status kuantum.

Jika Anda membawa sekelompok gerbang kuantum ke satu tempat, dan kemudian membuatnya bekerja dengan seperangkat qubit dalam urutan tertentu, ini akan menjadi sirkuit kuantum. Dalam kasus kami, untuk mendapatkan string acak 50 bit, Anda bisa membangun sirkuit kuantum yang menempatkan 50 qubit dalam superposisi status yang menggambarkan distribusi yang Anda butuhkan.

Saat mengukur qubit, seluruh superposisi secara acak runtuh menjadi string 50-bit tunggal. Probabilitas bahwa ia runtuh menjadi garis tertentu ditentukan oleh distribusi yang ditentukan oleh kontur kuantum. Pengukuran qubit mirip dengan bagaimana seorang pria yang ditutup matanya meraih ke dalam tas dan secara tidak sengaja menarik keluar satu baris dengan distribusi.


Scott Aaronson, Spesialis Ilmu Komputer, Universitas Texas di Austin

Dan bagaimana semua ini terkait dengan angka acak? Adalah penting bahwa string 50-bit yang dipilih oleh komputer kuantum akan mengandung banyak entropi, ukuran gangguan atau ketidakpastian, dan karenanya keacakan. "Dan ini, pada kenyataannya, dapat memiliki konsekuensi yang sangat serius," kata Scott Aaronson , seorang spesialis IT di University of Texas di Austin yang membuat protokol baru. "Bukan karena ini adalah penggunaan komputer kuantum yang paling penting - saya pikir itu jauh dari itu - tetapi karena sepertinya mungkin penggunaan pertama komputer kuantum yang dapat dipraktikkan."

Protokol Aaronson untuk menghasilkan angka acak cukup sederhana. Komputer klasik pertama mengumpulkan beberapa bit acak dari beberapa sumber tepercaya, dan kemudian menggunakan "benih keacakan" ini untuk menghasilkan deskripsi kontur kuantum. Bit acak menentukan jenis gerbang kuantum dan urutan di mana mereka harus bertindak pada qubit. Komputer klasik mengirim deskripsi ke komputer kuantum yang mengimplementasikan rangkaian kuantum, mengukur qubit, dan mengirimkan kembali string 50-bit. Dengan demikian, ternyata dipilih secara acak dari distribusi yang ditentukan oleh kontur.

Kemudian ulangi proses ini beberapa kali - misalnya, 10 kali untuk setiap rangkaian kuantum. Komputer klasik menggunakan tes statistik untuk memastikan bahwa jalur output berisi jumlah entropi yang adil. Aaronson menunjukkan (sebagian dalam karya yang diterbitkan ditulis dalam kolaborasi dengan Lijie Chen dan sebagian dalam karya yang belum diterbitkan) bahwa, di bawah asumsi tertentu yang masuk akal bahwa tugas-tugas tersebut kompleks secara komputasional, tidak ada komputer klasik yang dapat menghasilkan entropi seperti itu di waktu yang dapat dibandingkan dengan waktu di mana komputer kuantum menciptakan seleksi acak dari distribusi. Setelah diperiksa, komputer klasik mengumpulkan semua string 50-bit dan mengumpankannya ke algoritma klasik yang terkenal. "Ini menghasilkan string acak yang panjang dan hampir sempurna," kata Aaronson.

Perangkap kuantum

Protokol Aaronson paling cocok untuk komputer kuantum dengan qubit dari 50 hingga 100. Ketika jumlah qubit melampaui batas-batas ini, kompleksitas komputasi tidak memungkinkan bahkan superkomputer klasik untuk menggunakan protokol ini. Dalam kasus ini, skema lain untuk menghasilkan angka acak yang dapat diverifikasi menggunakan komputer kuantum memasuki lokasi. Ini menggunakan teknik matematika yang ada dengan nama trapdoor bebas cakar fungsi kompleks. "Ini kedengarannya lebih buruk daripada kenyataan," kata Umesh Wazirani , seorang spesialis IT di University of California di Berkeley, yang mengembangkan strategi baru yang dibantu oleh Zvika Brackerski , Paul Cristiano , Urmila Mahadev dan Thomas Vidik .

Perkenalkan kotak kami. Alih-alih masuk ke dalamnya dan menarik keluar string, kita melempar string n bit ke dalamnya, menyebutnya x, dan kemudian menghapus string lain dari n bit. Kotak entah bagaimana cocok dengan jalur input dan jalur output. Tetapi ia memiliki properti khusus: untuk setiap x ada jalur input lain y, yang menghasilkan jalur keluaran yang persis sama.

Dengan kata lain, ada dua jalur input unik - x dan y - di mana kotak mengembalikan garis output yang sama z. Triple ini, x, y dan z, disebut cakar. Kotak dalam bahasa ilmu komputer - fungsi. Fungsi ini mudah untuk dihitung, yaitu, untuk setiap x dan y mudah untuk menghitung z. Tetapi jika Anda hanya mengambil x dan z, maka menemukan y - dan seluruh cakar - tidak mungkin bahkan untuk komputer kuantum.


Urmila Mahadev, Umesh Vazirani dan Thomas Vidik

Satu-satunya cara untuk mendapatkan seluruh cakar adalah dengan menemukan beberapa informasi tambahan, yang disebut sebuah jebakan.

Vazirani dan rekannya ingin menggunakan fungsi seperti itu untuk tidak hanya memaksa komputer kuantum untuk menghasilkan angka acak, tetapi juga untuk memverifikasi bahwa komputer kuantum benar-benar bekerja sesuai dengan hukum kuantum - yang diperlukan untuk membangun kepercayaan dalam urutan acak.

Protokol dimulai dengan komputer kuantum yang menempatkan n qubit dalam superposisi semua string n-bit. Kemudian komputer klasik mengirimkan deskripsi kontur kuantum, menentukan fungsi yang akan diterapkan pada superposisi - fungsi perangkap tanpa cakar. Komputer kuantum mengimplementasikan sirkuit tanpa mengetahui apa pun tentang jebakan.

Pada tahap ini, komputer kuantum memasuki keadaan di mana satu set qubitnya berada dalam superposisi semua string n-bit, dan yang lainnya berisi hasil penerapan fungsi ke superposisi ini. Dua set qubit terjerat satu sama lain.

Komputer kuantum yang mengukur seperangkat qubit kedua secara acak meruntuhkan superposisi menjadi hasil tertentu z. Set qubit pertama runtuh menjadi superposisi serupa dari dua string n-bit, x dan y, karena salah satu dari mereka dapat berfungsi sebagai input untuk fungsi yang mengeluarkan z.

Komputer klasik menerima nilai output z, dan kemudian melakukan salah satu dari dua hal. Dalam kebanyakan kasus, ia meminta komputer kuantum untuk mengukur qubit yang tersisa. Ini meruntuhkan superposisi pada x atau pada y, dengan kemungkinan 50%. Ini sama dengan mendapatkan 0 atau 1 secara acak.

Terkadang, untuk menguji komputer kuantum untuk kuantum, komputer klasik meminta pengukuran khusus. Pengukuran dan hasilnya dirancang sedemikian rupa sehingga komputer klasik dengan bantuan jebakan yang hanya dapat dia akses dapat memastikan bahwa perangkat yang menanggapi permintaannya benar-benar kuantum. Vazirani dan rekannya menunjukkan bahwa jika perangkat memberikan jawaban yang benar untuk dimensi tertentu tanpa menggunakan keruntuhan qubit, itu akan setara dengan menemukan cakar tanpa jebakan. Dan ini tidak mungkin. Oleh karena itu, setidaknya satu qubit (memberi 0 atau 1 secara acak) harus runtuh di perangkat. "Protokol menciptakan qubit yang diuji di dalam komputer kuantum yang tidak kami percayai," kata Vazirani.

Qubit yang diuji ini memberikan satu informasi acak untuk setiap survei; urutan pertanyaan seperti itu dapat digunakan untuk membuat string acak panjang.

Skema ini dapat bekerja lebih cepat daripada protokol Aaronson, tetapi memiliki kelemahan yang jelas. "Dengan jumlah qubit 50 atau 70, itu tidak praktis," kata Aaronson.

Aaronson masih menunggu kemunculan sistem dari Google. "Apakah kualitas yang mereka tunjukkan kepada kita cukup untuk benar-benar mencapai keunggulan kuantum adalah pertanyaan besar," katanya.

Jika perusahaan berhasil, maka keacakan kuantum dijamin sudah di depan pintu kami. "Kami pikir itu akan menjadi pasar yang bermanfaat dan menjanjikan, dan inilah yang ingin kami tawarkan kepada orang-orang," kata Martinis.