Buku “Pemrograman Komputer Kuantum. Algoritme dasar dan contoh kode "

Halo para Penduduk! Komputer kuantum telah memicu revolusi komputer baru, dan Anda memiliki peluang besar untuk bergabung dengan terobosan teknologi saat ini. Pengembang, spesialis grafik komputer, dan calon profesional TI akan menemukan informasi praktis tentang komputasi kuantum yang dibutuhkan pemrogram dalam buku ini. Alih-alih mempelajari teori dan rumus, Anda akan segera fokus pada masalah spesifik yang menunjukkan kemampuan unik teknologi kuantum.



Eric Johnston, Nick Harrigan, dan Mercedes Gimeno-Segovia membantu mengembangkan keterampilan dan intuisi yang diperlukan, serta menguasai alat yang diperlukan untuk membuat aplikasi kuantum. Anda akan memahami apa yang mampu dilakukan komputer kuantum dan bagaimana menerapkannya dalam kehidupan nyata. Buku ini terdiri dari tiga bagian: - Pemrograman QPU: konsep dasar pemrograman prosesor kuantum, melakukan operasi dengan qubit dan teleportasi kuantum. - Primitif QPU: primitif algoritmik dan metode, amplifikasi amplitudo, transformasi Fourier kuantum, dan estimasi fase. - Berlatih QPU: memecahkan masalah spesifik menggunakan primitif QPU, metode pencarian kuantum, dan algoritma dekomposisi Shor.

Data nyata

Aplikasi QPU lengkap dibuat untuk bekerja dengan data non-pelatihan yang nyata. Data sebenarnya tidak selalu terbatas pada bilangan bulat dasar yang telah kita bahas sejauh ini. Oleh karena itu, pertanyaan tentang bagaimana merepresentasikan data yang lebih kompleks dalam QPU sepadan dengan usaha, dan struktur data yang baik bisa sama pentingnya dengan algoritma yang baik. Dalam bab ini, kami akan mencoba menjawab dua pertanyaan yang sebelumnya telah dilewati:

1. Bagaimana cara merepresentasikan tipe data kompleks dalam register QPU? Bilangan bulat positif dapat direpresentasikan dalam pengkodean biner sederhana. Tapi bagaimana dengan bilangan irasional, atau bahkan tipe data komposit seperti vektor atau matriks? Pertanyaan ini mengambil kedalaman baru ketika kami mempertimbangkan bahwa superposisi dan fase relatif dapat memberikan opsi pengkodean kuantum baru untuk tipe data ini.
2. , QPU? , WRITE . , QPU . , , , QPU , .

Mari kita mulai dengan pertanyaan pertama. Saat mendeskripsikan representasi QPU untuk tipe data dengan kompleksitas yang meningkat, kita akan sampai pada pengenalan struktur data kuantum lengkap dan konsep memori akses acak kuantum (QRAM). Quantum RAM adalah sumber daya penting untuk banyak aplikasi QPU praktis.



Materi pada bab-bab selanjutnya akan sangat bergantung pada struktur data yang disajikan dalam bab ini. Misalnya, apa yang disebut pengkodean amplitudo kompleks yang akan dijelaskan untuk data vektor adalah inti dari semua aplikasi pembelajaran mesin kuantum yang diperkenalkan di Bab 13.

Data non-target

Bagaimana cara menyandikan data numerik non-integer di register QPU? Dua cara standar untuk merepresentasikan nilai tersebut dalam biner adalah representasi titik tetap dan titik mengambang. Meskipun representasi floating point lebih fleksibel (dan dapat disesuaikan dengan kisaran nilai yang perlu diwakili dengan sejumlah bit), karena nilai qubit yang tinggi dan keinginan kami untuk kesederhanaan, representasi titik tetap adalah tempat yang lebih baik untuk memulai.



Bilangan fixed-point sering dijelaskan dalam notasi-Q (sayangnya, Q dalam hal ini tidak berarti "kuantum"). Ini membantu menghilangkan ambiguitas tentang di mana bit pecahan berakhir dan bit integer dimulai. Notasi Qn.m menunjukkan register n-bit, yang m bit-nya adalah untuk bagian pecahan (dan oleh karena itu, sisanya (n - m) berisi bagian bilangan bulat). Tentu saja, Anda dapat menggunakan notasi yang sama untuk menentukan bagaimana register QPU harus digunakan untuk mengenkode nomor poin tetap. Misalnya, pada Gambar. 9.1 menunjukkan register QPU delapan qubit, yang mengkodekan nilai 3.640625 dalam representasi titik tetap Q8.6.



Dalam contoh yang diberikan, nomor yang dipilih dapat dikodekan secara akurat dalam representasi titik tetap, karena 3.640625 =Tentu saja, keberuntungan seperti itu tidak selalu ditemukan. Meningkatkan jumlah bit dalam bagian bilangan bulat dari register titik tetap memperluas kisaran nilai bilangan bulat yang dapat direpresentasikan, sementara meningkatkan jumlah bit dalam bagian pecahan akan meningkatkan ketepatan bagian pecahan dari suatu bilangan. Semakin banyak qubit di bagian pecahan, semakin besar kemungkinan beberapa kombinasi dapat secara akurat mewakili bilangan tertentu.





Meskipun kami akan secara singkat menyebutkan penggunaan representasi titik tetap di bab-bab berikut, ini memainkan peran yang sangat penting dalam bereksperimen dengan data nyata di register QPU kecil. Saat bekerja dengan metode pengkodean yang berbeda, Anda perlu dengan hati-hati memantau pengkodean spesifik mana yang digunakan untuk data dalam register QPU tertentu untuk menafsirkan status qubitnya dengan benar.

QRAM

Register QPU dapat menyimpan representasi dari nilai numerik yang berbeda, tetapi bagaimana Anda menyimpan nilai-nilai ini di dalamnya? Data yang diinisialisasi dengan tangan menjadi usang dengan sangat cepat. Yang benar-benar kita butuhkan adalah kemampuan untuk membaca nilai dari memori, mengambil nilai yang disimpan di alamat biner. Pemrogram bekerja dengan memori akses acak tradisional menggunakan dua register: satu diinisialisasi dengan alamat memori, dan yang lainnya tetap tidak diinisialisasi. Memori akses acak menulis ke register kedua data biner yang disimpan di alamat yang ditentukan oleh register pertama, seperti yang ditunjukkan pada Gambar. 9.2.





Dapatkah memori tradisional digunakan untuk menyimpan nilai yang dimaksudkan untuk menginisialisasi register QPU? Tentu saja idenya terlihat menarik.



Jika Anda ingin menginisialisasi register QPU hanya dengan satu nilai tradisional (dua komplemen, titik tetap, atau pengkodean biner sederhana), maka RAM sudah cukup. Nilai yang diinginkan cukup disimpan dalam memori, dan write () dan read () digunakan untuk menulis atau membaca dari register QPU. Mekanisme terbatas inilah yang telah digunakan oleh kode JavaScript QCEngine untuk berinteraksi dengan register QPU sejauh ini.



Sebagai contoh, kode contoh dalam Daftar 9.1, yang menerima sebuah larik a dan mengimplementasikan operasi a [2] + = 1 ;, secara implisit mengambil larik nilai ini dari RAM untuk menginisialisasi register QPU. Sirkuit ditunjukkan pada Gambar. 9.3.

Kode sampel

Contoh ini dapat dilakukan secara online di http://oreilly-qc.github.io?p=9-1.

Daftar 9.1. Menggunakan QPU untuk menambah angka dalam memori

var a = [4, 3, 5, 1];

qc.reset(3);
var qreg = qint.new(3, 'qreg');

qc.print(a);
increment(2, qreg);
qc.print(a);

function increment(index, qreg)
{
      qreg.write(a[index]);
      qreg.add(1);
      a[index] = qreg.read();
}

Perlu dicatat bahwa dalam kasus sederhana ini, tidak hanya RAM tradisional yang digunakan untuk menyimpan integer, tetapi juga prosesor tradisional mengindeks array untuk memilih dan mengirimkan QPU dari nilai yang diinginkan.



Meskipun penggunaan RAM ini memungkinkan register QPU untuk diinisialisasi ke nilai biner sederhana, ini memiliki keterbatasan yang serius. Bagaimana jika Anda perlu menginisialisasi register QPU dengan superposisi nilai yang disimpan? Misalnya, dalam RAM, nilai 3 (110) disimpan di alamat 0x01, dan nilai 5 (111) disimpan di alamat 0x11. Bagaimana cara menyiapkan register input dalam superposisi kedua nilai ini?



Dengan RAM tradisional dan operasi write () tradisional yang kikuk, ini tidak akan berfungsi. Prosesor kuantum, seperti nenek moyang tabung mereka dulu, akan membutuhkan peralatan memori baru yang fundamental - di alam kuantum. Meet Quantum Random Access Memory (QRAM) memungkinkan Anda membaca dan menulis data di level kuantum. Sudah ada beberapa ide tentang bagaimana membangun QRAM secara fisik, tetapi perlu dicatat bahwa sejarah mungkin terulang kembali, dan prosesor kuantum yang sangat kuat mungkin muncul jauh sebelum ada perangkat keras memori kuantum yang bisa diterapkan.



Perlu dijelaskan sedikit lebih tepatnya apa yang dilakukan QRAM. Seperti memori tradisional, QRAM menerima dua register sebagai input: register alamat QPU untuk alamat memori dan register output QPU, yang mengembalikan nilai yang disimpan di alamat yang diberikan. Untuk QRAM, kedua register terdiri dari qubit. Ini berarti bahwa dalam register alamat Anda dapat mengatur superposisi sel memori dan, sebagai hasilnya, mendapatkan superposisi dari nilai yang sesuai dalam register keluaran (Gbr. 9.4).





Jadi QRAM sebenarnya memungkinkan Anda membaca nilai yang disimpan dalam superposisi. Amplitudo kompleks yang tepat dari superposisi yang akan diperoleh dalam register keluaran ditentukan oleh superposisi yang disediakan dalam register alamat. Dalam gambar. Gambar 9.2 menunjukkan perbedaan ketika melakukan operasi penambahan yang sama pada Listing 9.1 (Gambar 9.5), tetapi menggunakan QRAM untuk mengakses data daripada operasi baca / tulis QPU. Huruf "A" menunjukkan register di mana alamat QRAM (atau superposisi) ditransmisikan. Huruf "D" menunjukkan register di mana QRAM mengembalikan superposisi yang sesuai dari nilai yang disimpan (data).

Kode sampel

Contoh ini dapat dilakukan secara online di oreilly-qc.github.io?p=9-2 .

Daftar 9.2. Menggunakan QPU untuk menaikkan angka dari QRAM - register alamat mungkin berisi superposisi, yang akan menyebabkan register keluaran berisi superposisi dari nilai yang disimpan

var a = [4, 3, 5, 1];
var reg_qubits = 3;
qc.reset(2 + reg_qubits + qram_qubits());
var qreg = qint.new(3, 'qreg');
var addr = qint.new(2, 'addr');
var qram = qram_initialize(a, reg_qubits);

qreg.write(0);
addr.write(2);
addr.hadamard(0x1);

qram_load(addr, qreg);
qreg.add(1);

Deskripsi QRAM ini mungkin tampak terlalu kabur - apa itu perangkat keras memori kuantum? Dalam buku ini, kami tidak akan memberikan penjelasan tentang bagaimana membangun QRAM dalam prakteknya (seperti, katakanlah, kebanyakan buku tentang C ++ tidak memberikan penjelasan rinci tentang bagaimana memori tradisional bekerja). Contoh kode seperti yang ada di Listing 9.2 dijalankan dengan model sederhana yang meniru perilaku QRAM. Namun demikian, prototipe teknologi QRAM masih ada.



Sementara memori kuantum akan menjadi komponen penting dari setiap QPU yang serius, detail implementasi cenderung berubah, seperti pada perangkat komputasi kuantum lainnya. Yang penting bagi kami adalah gagasan tentang sumber daya fundamental yang berperilaku seperti yang ditunjukkan pada Gambar. 9.4, dan aplikasi canggih yang dapat dibangun di atasnya.

Dengan memori kuantum yang Anda inginkan, Anda dapat melanjutkan untuk membangun struktur data kuantum yang kompleks. Yang menarik adalah struktur yang memungkinkan Anda merepresentasikan data vektor dan matriks.

Pengkodean vektor

Katakanlah Anda ingin menginisialisasi register QPU untuk mewakili vektor sederhana seperti Persamaan 9.1.



Rumus 9.1. Contoh vektor untuk menginisialisasi register QPU.





Data dalam bentuk ini sering ditemukan di aplikasi pembelajaran mesin kuantum.

Mungkin metode yang paling jelas untuk mengenkode data vektor adalah dengan merepresentasikan setiap komponen sebagai register QPU terpisah dengan representasi biner yang sesuai. Kami akan menyebut ini (mungkin yang paling jelas) pengkodean status metode untuk vektor. Vektor dari contoh di atas dapat dikodekan dalam empat register dua qubit, seperti yang ditunjukkan pada Gambar. 9.6.





Salah satu masalah dengan pengkodean status naif adalah pemborosan qubit - sumber daya paling berharga dari sebuah QPU. Namun, salah satu kelebihan dari vektor berkode status tradisional adalah bahwa vektor tersebut tidak memerlukan memori kuantum. Komponen vektor dapat dengan mudah disimpan dalam memori standar dan menggunakan nilai terpisah untuk mengontrol persiapan setiap register QPU individu. Tetapi keunggulan ini juga mendasari kerugian paling serius dari pengkodean status vektor: menyimpan data vektor dengan cara tradisional ini mencegah kita menggunakan kapabilitas non-tradisional QPU. Untuk memanfaatkan kekuatan QPU, Anda harus dapat memanipulasi fase superposisi relatif, dan ini tidak mudah dilakukan,jika setiap komponen vektor benar-benar memperlakukan prosesor kuantum Anda sebagai kumpulan register biner tradisional!



Sebaliknya, Anda harus turun ke level kuantum. Misalkan komponen vektor disimpan dalam superposisi amplitudo dari satu register QPU. Karena register QPU dari n qubit dapat berada dalam superposisi dengan amplitudo 2n (dan oleh karena itu, akan ada lingkaran 2n untuk eksperimen dengan perekaman melingkar), dimungkinkan untuk merepresentasikan pengkodean vektor dengan n komponen dalam register QPU dengan qubit ceil (log (n)).



Untuk contoh vektor dari Formula 9.1, pendekatan ini akan memerlukan register dua qubit - idenya adalah menemukan skema kuantum yang sesuai untuk menyandikan data vektor pada Gambar 1. 9.7.





Mari kita sebut ini pengkodean data vektor kuantum unik pengkodean amplitudo kompleks. Penting untuk memahami perbedaan antara pengkodean amplitudo kompleks dan pengkodean status yang lebih konvensional. Meja 9.1 membandingkan dua metode pengkodean untuk data vektor yang berbeda. Contoh pengkodean status terakhir akan membutuhkan empat register 7-kbit, yang masing-masing menggunakan representasi titik tetap Q7.7.



Tabel 9.1. Perbedaan antara metode pengkodean data vektor (pengkodean amplitudo kompleks dan pengkodean status)





Untuk mendapatkan vektor dengan pengkodean amplitudo kompleks di QCEngine, Anda dapat menggunakan fungsi amplitude_encode () yang nyaman. Program dalam Daftar 9.3 mengambil vektor nilai dan referensi ke register QPU (yang harus cukup besar) dan menyiapkan register itu dengan melakukan pengkodean amplitudo kompleks pada vektor.

Kode sampel

Contoh ini dapat dilakukan secara online di oreilly-qc.github.io?p=9-3 .



Daftar 9.3. Mempersiapkan vektor dengan pengkodean amplitudo kompleks di QCEngine

//     ,    
//   2
var vector = [-1.0, 1.0, 1.0, 5.0, 5.0, 6.0, 6.0, 6.0];

//        
//  
var num_qubits = Math.log2(vector.length);
qc.reset(num_qubits);
var amp_enc_reg = qint.new(num_qubits, 'amp_enc_reg');

//      amp_enc_reg
amplitude_encode(vector, amp_enc_reg);

Dalam contoh ini, vektor hanya diteruskan sebagai larik JavaScript yang disimpan dalam memori tradisional - meskipun kami telah menunjukkan bahwa pengkodean amplitudo kompleks bergantung pada QRAM. Bagaimana QCEngine melakukan pengkodean amplitudo kompleks ketika hanya RAM komputer Anda yang tersedia untuk program? Meskipun dimungkinkan untuk menghasilkan skema pengkodean amplitudo yang kompleks tanpa QRAM, hal itu tentu saja tidak dapat dilakukan secara efisien. QCEngine menyediakan model yang lambat tapi bisa diterapkan dari apa yang bisa dicapai dengan akses QRAM.

Keterbatasan pengkodean amplitudo yang kompleks

Ide di balik pengkodean amplitudo kompleks tampak hebat pada awalnya - ia menggunakan lebih sedikit qubit dan menyediakan alat kuantum untuk bekerja dengan data vektor. Dalam aplikasi apa pun yang menggunakan mekanisme ini, ada dua faktor penting yang perlu dipertimbangkan.

Masalah 1: Hasil Kuantum

Anda mungkin telah memperhatikan yang pertama dari pembatasan ini: superposisi kuantum umumnya tidak dapat dibaca oleh BACA. Musuh utama kita lagi! Jika Anda mendistribusikan komponen vektor pada superposisi kuantum, mereka tidak dapat dibaca lagi. Secara alami, ini tidak menimbulkan masalah khusus saat mentransfer data vektor ke input program QPU lain dari memori. Namun seringkali, aplikasi QPU yang menerima data vektor berenkode-AM yang kompleks pada masukan juga akan menghasilkan data vektor berenkode-AM yang kompleks pada keluaran.



Jadi, penggunaan pengkodean amplitudo yang kompleks sangat membatasi kemampuan kami untuk membaca keluaran aplikasi dengan operasi BACA. Untungnya, informasi yang berguna sering kali dapat diambil dari hasil pengkodean amplitudo yang kompleks. Seperti yang akan Anda lihat pada bab-bab berikut, meskipun Anda tidak dapat mengenali masing-masing komponen, Anda dapat mengetahui properti global vektor yang dikodekan dengan cara ini. Namun, pengkodean amplitudo yang kompleks bukanlah obat mujarab, dan penerapannya yang berhasil membutuhkan perhatian dan kecerdikan.

Masalah 2: persyaratan untuk menormalkan vektor

Masalah kedua yang terkait dengan pengkodean amplitudo kompleks disembunyikan dalam tabel. 9.1. Perhatikan lebih dekat pengkodean amplitudo kompleks dari dua vektor pertama dalam tabel: [0,1,2,3] dan [6,1,1,4]. Dapatkah amplitudo kompleks dari register QPU dua qubit mengambil nilai [0,1,2,3] atau nilai [6,1,1,4]? Sayangnya tidak. Pada bab-bab sebelumnya, kita biasanya mengabaikan pembahasan amplitudo dan fase relatif demi notasi melingkar yang lebih intuitif. Meskipun pendekatan ini lebih intuitif, pendekatan ini melindungi Anda dari satu aturan numerik penting tentang amplitudo kompleks: kuadrat amplitudo kompleks register harus berjumlah 1. Persyaratan ini, yang disebut normalisasi, tampak logis jika Anda ingat bahwa kuadrat amplitudo dalam register sesuai dengan probabilitas pembacaan. hasil yang berbeda.Karena satu hasil harus diperoleh, probabilitas ini (dan, akibatnya, kuadrat dari semua amplitudo kompleks) harus berjumlah 1. Saat menggunakan notasi melingkar yang mudah digunakan, mudah untuk melupakan tentang normalisasi, tetapi hal itu memberikan batasan penting pada vektor mana pengkodean amplitudo kompleks dapat diterapkan pada data. Hukum fisika tidak mengizinkan pembuatan register yang berada di superposisi dengan amplitudo kompleks [0,1,2,3] atau [6,1,1,4].berada di superposisi dengan amplitudo kompleks [0,1,2,3] atau [6,1,1,4].berada di superposisi dengan amplitudo kompleks [0,1,2,3] atau [6,1,1,4].



Untuk menerapkan pengkodean amplitudo kompleks ke dua vektor masalah dari Tabel. 9.1, pertama-tama Anda harus menormalkannya dengan membagi setiap komponen dengan jumlah kuadrat semua komponen. Misalnya, dalam pengkodean amplitudo kompleks dari vektor [0,1,2,3], Anda harus membagi semua komponen dengan 3,74 terlebih dahulu untuk mendapatkan vektor yang dinormalisasi [0,00, 0,27, 0,53, 0,80], yang sekarang cocok untuk pengkodean dalam amplitudo superposisi kompleks.



Apakah menormalkan data vektor memiliki efek yang tidak diinginkan? Sepertinya datanya telah berubah total! Faktanya, normalisasi membuat sebagian besar informasi penting tidak berubah (dalam representasi geometris, ini hanya menskalakan panjang vektor, membiarkan arahnya tidak berubah). Bisakah kita berasumsi bahwa data yang dinormalisasi sepenuhnya menggantikan data asli? Itu tergantung pada kebutuhan aplikasi QPU tertentu tempat Anda ingin menggunakannya. Ingatlah bahwa Anda dapat menyimpan nilai numerik faktor normalisasi di register yang berbeda jika perlu.

Pengkodean amplitudo yang kompleks dan perekaman melingkar

Ketika Anda mulai berpikir lebih spesifik tentang nilai numerik dari amplitudo kompleks register, akan sangat membantu untuk mengingatkan diri sendiri tentang bagaimana amplitudo kompleks direpresentasikan dalam notasi melingkar, dan untuk memperhatikan kemungkinan jebakan. Area yang terisi dalam notasi melingkar mewakili kuadrat amplitudo dari amplitudo kompleks dari status kuantum. Dalam situasi seperti pengkodean amplitudo kompleks, di mana amplitudo kompleks harus mewakili komponen vektor dengan nilai nyata, ini berarti bahwa area terisi ditentukan oleh kuadrat dari komponen vektor yang sesuai, dan bukan oleh komponen itu sendiri. Dalam gambar. 9.8 menunjukkan cara menafsirkan representasi vektor [0,1,2,3] dengan benar setelah normalisasi dalam notasi melingkar.





Anda sekarang cukup tahu tentang vektor berkode amplitudo yang kompleks untuk memahami aplikasi QPU yang akan disajikan dalam buku ini. Namun untuk banyak aplikasi, terutama yang terkait dengan pembelajaran mesin kuantum, perlu selangkah lebih maju dan menggunakan QPU untuk memanipulasi tidak hanya vektor, tetapi juga seluruh matriks data. Bagaimana Anda menyandikan deretan angka dua dimensi?



»Rincian lebih lanjut tentang buku dapat ditemukan di situs web rumah penerbitan

» Daftar Isi

» Kutipan



Untuk Habitants diskon 25% untuk kupon - Pemrograman



Setelah pembayaran untuk versi kertas buku, sebuah e-book dikirim ke email.