Memprogram komputer kuantum: menghasilkan angka acak yang benar

Komputer adalah mesin yang deterministik, dapat diprediksi dan dirancang untuk secara membabi buta mengikuti serangkaian instruksi secara berulang. Sifat komputer ini tentu saja telah membantu kita dengan sangat baik sepanjang sebagian besar abad terakhir, tetapi desain ini dilengkapi dengan kelemahan mendasar: ia tidak dapat melakukan operasi acak¹. Generator angka acak adalah komponen yang sangat penting dari banyak aplikasi saat ini, tetapi sementara angka yang mereka hasilkan mungkin cukup acak, mereka "pseudo" acak dan sering mungkin untuk memprediksi atau membalikkan insinyur dalam beberapa cara.

Saat ini dimungkinkan untuk memanfaatkan sifat aneh, partikel subatom yang tidak terduga dan menggunakannya untuk melakukan perhitungan di dalam komputer kuantum. Dengan hanya beberapa baris kode kita dapat memprogram komputer kuantum nyata untuk menghasilkan angka acak yang sebenarnya bagi kita. Sesuatu yang sebelumnya tidak mungkin menggunakan komputer klasik berbasis Turing.

Generator angka acak hari ini

Sebagian besar bahasa pemrograman populer memiliki beberapa bentuk penghasil angka acak bawaan untuk digunakan para pengembang. Generator ini umumnya mengambil seed input yang mewakili tanggal dan waktu saat ini, mengacak nilai ini menggunakan algoritma, dan mengeluarkan nilai yang sangat berbeda dari input yang kami anggap acak. Fungsi pengacakan adalah algoritma yang dapat diprediksi dengan jumlah entropi yang tinggi (untuk perubahan kecil pada input mereka mengembalikan perubahan besar dalam output), dan kami mendapatkan angka yang berbeda setiap kali karena seed input berubah seiring waktu. Untuk hampir semua aplikasi praktis sistem ini bekerja dengan sangat baik, tetapi karena merupakan sistem yang dapat diprediksi, sistem ini tidak sepenuhnya acak.

Mari kita ambil penghasil angka acak yang disediakan oleh Javascript sebagai contoh. Pertama-tama, karena Javascript adalah bahasa yang ditafsirkan dalam lingkungan yang berbeda (browser atau node.js), tergantung pada penerjemah untuk memutuskan algoritma apa yang digunakan yang sesuai dengan spesifikasi ECMAScript. Saat ini, sebagian besar browser modern menggunakan algoritma keacakan yang sama untuk memberi fungsi fungsi Jav.random () Javascript yang disebut xorshift128 +.

Berikut ini adalah versi umum dari algoritma ini yang ditulis dalam bahasa C²:

Tujuan dari kode ini adalah untuk mengambil beberapa input (seed) dan mengacaknya sedemikian rupa sehingga setiap dua output dari dua input yang terpisah akan tampak sangat berbeda satu sama lain dan oleh karena itu acak. Algoritma mencapai ini dengan menggeser representasi biner seed ke atas dan ke bawah dan membalikkan representasi bit di antara langkah-langkah, menghasilkan sedikit representasi dari angka yang sama sekali berbeda dari input seed.

Agar fungsi ini memberikan hasil yang berbeda setiap kali dijalankan, kita membutuhkan seed yang selalu berubah. Browser (dan bahasa pemrograman lainnya) sering hanya menggunakan representasi numerik dari tanggal dan waktu saat ini³, misalnya zaman UNIX, jumlah milidetik yang telah berlalu sejak 1 Januari 1970⁴.

Dengan seed ini, dan algoritma entropi tinggi di atas, kita dapat mencapai generator angka acak yang sangat meyakinkan. Sistem komputer menggunakan fungsi-fungsi ini sepanjang waktu tanpa masalah, tetapi kita tidak dapat menyebutnya sebagai penghasil bilangan yang benar-benar acak. Jika seseorang tahu bagaimana generator angka acak bekerja, dan dapat memprediksi seed input, mereka juga dapat memprediksi output dari fungsi tersebut. Salah satu cara untuk meningkatkan keacakan sistem ini adalah dengan membuat benih lebih sulit untuk diprediksi. Sebagai contoh, banyak sistem menggunakan radiasi latar belakang gelombang mikro kosmik (gelombang radio elektromagnetik yang masih tersisa oleh big bang) sebagai benih⁵ karena tidak ada yang dapat memprediksi bagaimana kebisingan latar belakang ini akan berperilaku pada titik waktu tertentu.

Sistem keacakan menggunakan benih yang tidak dapat diprediksi seperti latar belakang gelombang mikro pada saat ini benar-benar acak berdasarkan pengetahuan saat ini. Saat ini tidak ada yang dapat memprediksi bagaimana benih ini akan berperilaku pada suatu titik waktu tertentu, sehingga tidak dapat memprediksi angka acak yang dihasilkannya. Jenis benih ini bahkan mungkin tidak mungkin bagi kita untuk diprediksi di masa depan, tetapi jika kita memiliki pengukuran yang sama dari latar belakang gelombang mikro kosmik seperti orang lain dan menggunakannya sebagai input ke pembangkit bilangan acak kita akan dapat memprediksi hasilnya .

Untuk menghasilkan bilangan yang benar-benar acak, kita perlu menemukan sesuatu di alam yang tidak dapat kita prediksi dengan sempurna, sesuatu yang hanya bisa dijelaskan dengan probabilitas. Sampai awal abad ke-20 ini diyakini tidak ada, tetapi teori mekanika kuantum membuka pintu ke dunia yang bahkan lebih aneh dan tak terduga.

Probabilitas di dunia kuantum

Mekanika kuantum adalah teori yang menggambarkan sifat partikel pada skala subatomik. Dikatakan bahwa ketika kita mengamati dunia pada skala yang lebih kecil dan lebih kecil, deskripsi klasik partikel dan gaya seperti yang didefinisikan oleh Sir Isaac Newton pada abad ke-18 menjadi kurang akurat dan kita harus beralih ke deskripsi kuantum berbeda yang didorong oleh statistik dan probabilitas. Sebagai contoh, posisi pasti dari elektron di sekitar atom tidak dapat diprediksi, kita hanya dapat memprediksi probabilitas menemukan elektron di area tertentu di sekitar atom pada waktu tertentu⁶.

Untuk membuat hal-hal lebih aneh, Interpretasi Kopenhagen dari mekanika kuantum yang dirancang oleh Niels Bohr dan Werner Heisenberg menyatakan bahwa sistem kuantum tidak memiliki sifat yang pasti sebelum diukur, tetapi ada di semua keadaan yang mungkin secara bersamaan dalam sebuah prinsip yang dikenal sebagai superposisi. Hanya ketika sistem diamati bahwa superposisi runtuh dan sistem ada dalam satu kondisi tertentu. Ini dikenal sebagai efek pengamat. Dengan mengambil contoh posisi elektron, kita dapat memperkirakan probabilitas bahwa elektron akan hadir di lokasi tertentu pada waktu tertentu, tetapi sebelum pengukuran itu elektron ada di semua posisi yang mungkin di sekitar atom. Selama pengukuran, elektron akan mengungkapkan dirinya berada di satu tempat, tetapi dengan mengamati dan mengukur elektron kita telah mengubah kondisinya dan tidak dapat menentukan sifat-sifat lain seperti momentum karena prinsip ketidakpastian⁷.

Penafsiran dunia kuantum ini dimengerti mengguncang komunitas fisika pada saat itu, dan diperdebatkan hingga hari ini. Einstein menolak untuk percaya bahwa realitas diatur oleh probabilitas dan dengan terkenal mengatakan "Saya, bagaimanapun, saya yakin bahwa Dia (Tuhan) tidak melempar dadu" dan "Apakah Anda benar-benar berpikir bulan tidak ada di sana jika Anda tidak melihat itu? ". Sebagai tanggapan, Niles Bohr kemudian merespons, "Einstein, jangan katakan kepada Tuhan apa yang harus dilakukan." ⁸

Suka atau tidak, teori Quantum tetap menjadi pemahaman terbaik kita tentang dunia subatomik dan telah berkembang menjadi jantung dari semua jenis prosesor informasi baru. Komputer kuantum mengandalkan kemampuan partikel-partikel kuantum untuk eksis dalam superposisi beberapa keadaan sekaligus untuk melakukan perhitungan. Karena komputer kuantum dapat memanipulasi superposisi partikel yang diatur oleh probabilitas, kita dapat menggunakannya sebagai alat untuk memanfaatkan sifat dunia kuantum dan membangun generator angka acak yang benar.

Qubit dan gerbang kuantum

Komputer klasik menggunakan digit biner, atau bit, untuk merepresentasikan informasi. Sedikit dapat mengambil nilai 0 atau 1 dan diwakili oleh salah satu dari dua level tegangan DC di dalam prosesor komputer. Komputer kuantum biasanya merepresentasikan informasi dengan cara yang sama, menggunakan bit 0 atau 1, tetapi mereka secara fisik mengimplementasikan status ini menggunakan properti biner dari partikel subatom. Sifat-sifat ini dapat berupa putaran elektron (berputar ke atas dan berputar ke bawah) atau polarisasi foton (polarisasi horizontal dan vertikal). Salah satu dari representasi ini dapat dijelaskan oleh mekanika kuantum, dan dapat berada di superposisi dari kedua kondisi sekaligus⁹. Ini berarti bahwa sedikit informasi kuantum, atau qubit, dapat ada dalam superposisi dari kedua status 0 dan 1 pada saat yang sama. Untuk mengukur hasil perhitungan, kita harus mengukur keadaan kuantum di dalam komputer dan memaksa partikel-partikel ini untuk memilih keadaan 0 atau 1.

Untuk memanipulasi qubit dalam komputer kuantum kami menggunakan gerbang kuantum seperti gerbang sirkuit klasik. Sementara komputer klasik dapat melakukan operasi pada bit seperti membalikkannya ke nilai berlawanan, gerbang kuantum dapat melakukan operasi ini dan operasi kuantum yang lebih maju seperti mendorong qubit ke superposisi dari kedua nilai yang mungkin. Gerbang yang mendorong qubit ke superposisi disebut gerbang Hadamard dan merupakan salah satu gerbang logika yang paling mendasar dan umum digunakan dalam komputasi kuantum¹⁰.

Ketika kita mendorong perputaran elektron ke dalam superposisi dari kedua kemungkinan keadaan naik dan turun yang mewakili nilai 1 dan 0 dari qubit, elektron dapat dikatakan memiliki putaran simultan dari kedua nilai, dan qubit berada dalam superposisi dari 0 dan 1. Saat mengukur qubit ini, kami menutup superposisi dan memaksanya menjadi salah satu dari dua kondisi yang memungkinkan ini, masing-masing dengan probabilitas yang sama terjadi¹¹. Dengan setiap superposisi dan pengukuran, kami memiliki peluang 50% untuk mengukur 1 atau 0. Kami kemudian akan melakukan setara dengan flip koin menggunakan hukum dasar dunia subatomik.

Untuk menghasilkan nomor acak dari lemparan koin kuantum, yang perlu kita lakukan adalah:

  1. Dapatkan qubit dengan status yang telah ditentukan. 0 atau 1 akan dilakukan.
  2. Paksa qubit itu menjadi superposisi menggunakan gerbang Hadamard.
  3. Ukur status qubit.
  4. Dapatkan nilai 0 atau 1 dengan probabilitas yang sama.

Sekarang yang perlu kita lakukan untuk membuat generator angka acak kita yang sebenarnya adalah mendapatkan akses ke komputer kuantum dan program dalam langkah-langkah di atas.

Memprogram komputer kuantum

Hebatnya, beberapa perusahaan sekarang telah membuat komputer kuantum sederhana tersedia di cloud untuk digunakan oleh masyarakat umum. Salah satu layanan ini disediakan oleh IBM dan disebut IBM Q Experience. Saat ini layanan ini menyediakan akses ke dua prosesor 5 qubit dan dua prosesor 16 qubit yang didistribusikan di seluruh dunia. Setelah pengguna membuat akun gratis, waktu perhitungan dialokasikan menggunakan sistem kredit, dan pengguna gratis diberikan sejumlah kecil kredit untuk menggunakan penyegaran itu setiap hari. Anda dapat mendesain sirkuit Anda menggunakan editor online atau secara programatik melalui SDK (16 prosesor qubit saat ini hanya tersedia untuk pengguna SDK), dan ketika program Anda siap dijalankan, ia dimasukkan ke dalam antrian untuk dijalankan ketika prosesor sedang selanjutnya tersedia.

Untuk membangun generator nomor acak kami, kami akan menggunakan SDK yang disediakan untuk IBM Q Experience yang disebut Qiskit. Kita perlu menulis kode kita dengan Python, dan sambil menulis aplikasi kita juga akan dapat mengujinya pada prosesor kuantum yang disimulasikan secara lokal di mesin kita sendiri untuk menghemat waktu dan kredit.

Pertama mari kita mulai dengan kode dasar untuk menyelesaikan empat langkah di atas:

Di sini kita membuat sirkuit kuantum dari dua register bit tunggal, satu register kuantum dengan qubit tunggal dan register klasik berukuran serupa untuk berinteraksi dengan register kuantum. Kami kemudian menerapkan gerbang Hadamard ke qubit tunggal kami untuk memaksanya menjadi status superposisi, dan mengukur status itu ke register klasik kami. Akhirnya kami menjalankan proses yang baru saja kami jelaskan pada prosesor simulasi lokal, memberitahu SDK untuk hanya menjalankan proses sekali. Untuk sebagian besar tujuan lain, kami ingin menjalankan rangkaian kuantum beberapa kali dan rata-rata hasilnya untuk menghilangkan keacakan yang melekat dalam sistem, tetapi untuk tujuan kami hanya satu putaran akan bekerja dengan sempurna. Kami dapat mencetak hitungan hasil kami, yang akan ditampilkan sebagai peta kemungkinan nilai bit dengan berapa kali mereka diukur untuk setiap proses, mis. {"0": 1, "1": 0}. Anda akan menemukan bahwa begitu program ini dijalankan pada prosesor kuantum, pengukuran nilai 0 atau 1 akan terjadi dengan probabilitas 50%.

Kode ini telah memberikan kita setara dengan lemparan koin yang sempurna, jadi sekarang yang perlu kita lakukan adalah menemukan cara untuk mengambil serangkaian lemparan koin biner dan mengonversinya menjadi angka acak dalam rentang yang diberikan. Cara mudah untuk melakukan ini adalah dengan mengambil nilai bit acak yang kami hasilkan dengan kode di atas dan menyatukannya secara berurutan untuk membuat angka biner. Ketika kita mengonversi angka biner ini menjadi desimal kita akan menemukan bahwa itu akan menjadi desimal acak setiap waktu.

Jika kita akan mengizinkan input dari pengguna untuk memilih rentang untuk menghasilkan nomor kita, kita perlu mencari tahu berapa banyak bit yang diperlukan untuk mewakili integer basis 10 yang diberikan sehingga kita tahu berapa banyak bit acak untuk menghasilkan. Persamaan yang perlu kita lakukan adalah ¹²:

Yang bisa kita wakili dengan python sebagai fungsinya:

Menggunakan ini kita dapat menulis fungsi yang menghasilkan angka acak ke maksimum yang diberikan dengan mengulangi sirkuit kuantum di atas untuk setiap bit yang kita butuhkan:

Kode ini adalah inti dari penghasil bilangan acak kuantum kami. Kami menghitung jumlah bit yang diperlukan untuk menghasilkan angka hingga maksimum yang diberikan, dan untuk setiap bit yang diperlukan kami menghasilkan nilai acak menggunakan Qiskit dan menambahkannya ke string bit yang dihasilkan. Kami kemudian mengurai string ini sebagai basis 10 integer dari basis 2.

Namun ada masalah penting dengan kode ini; jika Anda menjalankannya cukup banyak, Anda akan menyadari bahwa itu benar-benar menghasilkan angka hingga maksimum kekuatan terdekat berikutnya dari dua input. Ini karena kami telah menghitung berapa banyak bit yang diperlukan untuk mewakili angka yang diberikan, tetapi jika semua bit ini memiliki nilai 1, maka angka kami dapat dengan mudah lebih tinggi dari jumlah maksimum yang diberikan. Sangat sulit untuk menyelesaikan masalah ini, dan cara terbaik untuk menjaga angka di bawah maksimum kami tanpa memperkenalkan beberapa bias statistik lainnya adalah menggunakan rejection sampling¹³. Kami hanya perlu menghasilkan angka, dan jika terlalu besar tolak angka itu dan jalankan prosesnya lagi. Karena kami memiliki sumber daya terbatas pada akun gratis dengan IBM Q Experience, kami akan menjaga kode kami tetap sederhana dan hanya membatasi input pengguna menjadi dua, dengan mengumpulkan input ke kekuatan tertinggi berikutnya:

Kami juga dapat dengan mudah mem-parsing input baris perintah dari pengguna untuk mendapatkan maksimum yang diinginkan, serta tanda untuk memberi tahu program apakah akan berjalan di komputer kuantum nyata dan opsi untuk meneruskan kunci API untuk Pengalaman Q IBM:

Akhirnya, sebelum kita dapat menjalankan kode kita pada prosesor kuantum nyata, akan lebih baik untuk mengoptimalkan solusi kita untuk mengulang beberapa kali minimal untuk menghemat sumber daya gratis pada prosesor kuantum cloud kita. Sebagai contoh, jika kita menggunakan prosesor 5 qubit "IBM Q5 Tenerife" (nama belakang ibmqx4), kita dapat memanfaatkan semua 5 qubit dengan melewati semuanya melalui gerbang Hadamard dan menggabungkan nilainya ketika diukur. Ini akan memungkinkan kami untuk menghasilkan angka acak hingga 31 dengan satu loop, dan IBM Q Experience memberikan kredit yang cukup untuk 3 instruksi yang memungkinkan kami untuk menghasilkan angka hingga 32767 dalam sekali jalan.

Dengan semua elemen ini digabungkan, kode akhir kami menjadi:

Kode lengkap dan deskripsi tentang cara menjalankannya dapat ditemukan di GitHub.

Apa yang baru saja terjadi?

Jika Anda mendaftar untuk mendapatkan akun gratis dengan IBM Q Experience, dapatkan kunci API dan jalankan program ini seperti:

python ./main.py -remote --qx-token  15

Anda akan menemukan proses akan memakan waktu untuk berjalan (sekitar 10-20 menit) dan mengembalikan bilangan bulat acak antara 0 dan 16. Inilah yang terjadi saat Anda menunggu:

  1. Komputer Anda mem-parsing input baris perintah dan menghitung berapa bit acak yang diperlukan untuk mewakili angka antara 0 dan kekuatan berikutnya 2 dari 15. Dalam hal ini 4 bit diperlukan untuk membangun angka hingga 16, yang berarti hanya satu instruksi untuk mengirim ke prosesor kuantum 5 qubit.
  2. Serangkaian instruksi dibuat oleh Qiskit SDK dan dikirim ke IBM Q Experience untuk dieksekusi.
  3. Instruksi Anda ditempatkan dalam antrian untuk dijalankan oleh komputer kuantum "IBM Q5 Tenerife" di New York.
  4. Setelah siap, komputer kuantum IBM Q5 Tenerife mengalokasikan 4 dari 5 qubit yang tersedia untuk tugas yang diminta. Ini menerapkan gerbang Hadamard ke 4 qubit ini, memasukkannya ke dalam superposisi putaran kuantum.
  5. Putaran masing-masing qubit diukur, menyatukan superposisi kuantum dan mengungkapkan keadaan biner acak yang kemudian di-output ke register klasik 4 bit.
  6. Status biner yang diukur kemudian dikirim kembali ke IBM Q Experience, dan kembali ke Qiskit SDK yang berjalan di komputer Anda.
  7. Komputer Anda melakukan pengukuran biner ini dan membuat angka biner 4 bit darinya.
  8. Nomor biner Anda dikonversi menjadi integer basis 10 dan dikembalikan ke pengguna.

Selamat, Anda baru saja mengendalikan komputer kuantum dan memanfaatkan sifat aneh partikel subatom yang tidak terduga untuk menghasilkan angka acak yang benar. Silakan pertimbangkan untuk menggunakan kekuatan super yang baru Anda temukan untuk selamanya.

Tahu beberapa aplikasi praktis yang menarik untuk komputasi awan kuantum? Beritahu saya @robbiemccorkell.

Referensi:

  1. Jason M. Rubin, MIT School of Engineering (2011), Dapatkah komputer menghasilkan angka yang benar-benar acak?
  2. Daniel Simmons, Hackernoon (2014), Bagaimana Math.random () JavaScript JavaScript menghasilkan angka acak?
  3. Adam Hyland, bocoup (2013), Pembuatan angka acak dalam Javascript
  4. Spesifikasi Basis Open Group Issue 7 (2018), 4.16: Detik Sejak Zaman
  5. Jeffrey S. Lee, Gerald B. Cleaver, Perpustakaan Universitas Cornell (2015), Spektrum Daya Radiasi Gelombang Mikro Kosmik sebagai Generator Bit Acak untuk Kriptografi Kunci Asimetris dan Asimetris-Kunci
  6. Tony Hey, Patrick Walters, Cambridge University Press (1987), The Quantum Universe
  7. Alastair I. M. Rae, Grup Taylor & Francis (2008), Mekanika Kuantum (Edisi ke-5)
  8. Wikipedia (2018), interpretasi Kopenhagen
  9. Eleanor Riefffel, Wolfgang Polak, Institut Teknologi Massachusetts (2011), Quantum Computing: A lembut pengantar
  10. Artur Ekert, Patrick Hayden, Hitoshi Inamori, University of Oxford (2008), Konsep dasar dalam perhitungan kuantum
  11. Daniel Baumann, Universitas Cambridge (2013), Konsep dalam Fisika Teoritis
  12. Rick Regan, Exploring Binary (2012), Jumlah Bit dalam Integer Desimal
  13. Dimitri DeFigueiredo Ph.D (2017), Menghasilkan bilangan bulat acak dari byte acak

Sunting: Terima kasih kepada Bob Sutor karena telah menunjukkan bahwa komputer kuantum IBM Q 5 Tenerife hanya terkait dengan Tenerife dengan nama, bukan lokasi, dan terletak di New York.

Awalnya diterbitkan di blog.red-badger.com.