Model query komputasi

Saat kita memodelkan komputasi dalam istilah matematika, kita biasanya memikirkan jenis proses yang diwakili oleh gambar berikut, di mana informasi diberikan sebagai input, komputasi berlangsung, dan output dihasilkan.

Meskipun benar bahwa komputer yang kita gunakan saat ini terus menerima input dan menghasilkan output, pada dasarnya berinteraksi dengan kita dan komputer lain dengan cara yang tidak tercermin dalam gambar tersebut, niat gambar ini bukan untuk mewakili operasi komputer yang sedang berlangsung. Melainkan, untuk membuat abstraksi komputasi yang sederhana, dengan fokus pada tugas komputasi yang terisolasi. Misalnya, input mungkin mengkodekan angka, vektor, matriks, graf, deskripsi molekul, atau sesuatu yang lebih rumit, sementara output mengkodekan solusi untuk tugas komputasi yang kita pikirkan.

Poin utamanya adalah bahwa input diberikan ke komputasi, biasanya dalam bentuk string biner, tanpa bagian mana pun yang tersembunyi.

Deskripsi model

Dalam model query komputasi, seluruh input tidak diberikan ke komputasi seperti dalam model standar yang disarankan di atas. Melainkan, input tersedia dalam bentuk fungsi, yang diakses komputasi dengan membuat query. Alternatifnya, kita bisa melihat komputasi dalam model query sebagai memiliki random access ke bit (atau segmen bit) dari input.

Kita sering menyebut input sebagai yang disediakan oleh oracle atau black box dalam konteks model query. Kedua istilah ini menyiratkan bahwa deskripsi lengkap input tersembunyi dari komputasi, dengan satu-satunya cara mengaksesnya adalah dengan mengajukan pertanyaan. Seolah-olah kita berkonsultasi dengan Oracle di Delphi tentang input: dia tidak akan memberitahu kita semua yang dia ketahui, dia hanya menjawab pertanyaan spesifik. Istilah black box masuk akal terutama ketika kita memikirkan input sebagai yang diwakili oleh suatu fungsi; kita tidak bisa melihat ke dalam fungsi dan memahami cara kerjanya, kita hanya bisa mengevaluasinya pada argumen yang kita pilih.

Kita akan bekerja secara eksklusif dengan string biner dalam pelajaran ini, berbeda dengan string yang berisi simbol berbeda, jadi mari tulis $\Sigma = \{0,1\}$ mulai sekarang untuk merujuk ke alfabet biner demi kemudahan. Kita akan memikirkan masalah komputasi yang berbeda, dengan beberapa contoh sederhana yang dijelaskan segera, tetapi untuk semuanya input akan direpresentasikan oleh fungsi berbentuk

$$f:\Sigma^n \rightarrow \Sigma^m$$

untuk dua bilangan bulat positif $n$ dan $m.$ Tentu saja, kita bisa memilih nama yang berbeda selain $f,$ tetapi kita akan tetap menggunakan $f$ sepanjang pelajaran.

Untuk mengatakan bahwa komputasi membuat query berarti bahwa beberapa string $x \in \Sigma^n$ dipilih, dan kemudian string $f(x)\in\Sigma^m$ tersedia untuk komputasi oleh oracle. Cara tepatnya ini bekerja untuk algoritma kuantum akan dibahas segera — kita perlu memastikan bahwa ini mungkin dilakukan dengan operasi kuantum uniter yang memungkinkan query dibuat dalam superposisi — tetapi untuk saat ini kita bisa memikirkannya secara intuitif pada tingkat tinggi.

Akhirnya, cara kita mengukur efisiensi algoritma query sederhana: kita menghitung jumlah query yang diperlukan. Ini terkait dengan waktu yang dibutuhkan untuk melakukan komputasi, tetapi tidak sama persis karena kita mengabaikan waktu untuk operasi selain query, dan kita juga memperlakukan setiap query seolah-olah memiliki biaya unit. Kita bisa memperhitungkan operasi selain query jika mau (dan ini kadang dilakukan), tetapi membatasi perhatian hanya pada jumlah query membantu menjaga hal-hal tetap sederhana.

Contoh masalah query

Berikut beberapa contoh sederhana masalah query.

• OR. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma$ (jadi $m=1$ untuk masalah ini). Tugasnya adalah menghasilkan output $1$ jika ada string $x\in\Sigma^n$ yang $f(x) = 1,$ dan menghasilkan output $0$ jika tidak ada string seperti itu. Jika kita memikirkan fungsi $f$ sebagai mewakili urutan $2^n$ bit yang bisa diakses secara random, masalahnya adalah menghitung OR dari bit-bit ini.

• Paritas. Fungsi input lagi berbentuk $f:\Sigma^n \rightarrow \Sigma.$ Tugasnya adalah menentukan apakah jumlah string $x\in\Sigma^n$ yang $f(x) = 1$ adalah genap atau ganjil. Lebih tepatnya, output yang diperlukan adalah $0$ jika himpunan $\{x\in\Sigma^n : f(x) = 1\}$ memiliki jumlah elemen yang genap dan $1$ jika memiliki jumlah elemen yang ganjil. Jika kita memikirkan fungsi $f$ sebagai mewakili urutan $2^n$ bit yang bisa diakses secara random, masalahnya adalah menghitung paritas (atau exclusive-OR) dari bit-bit ini.

• Minimum. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma^m$ untuk pilihan bilangan bulat positif $n$ dan $m$ mana pun. Output yang diperlukan adalah string $y \in \{f(x) : x\in\Sigma^n\}$ yang datang pertama dalam pengurutan leksikografis (yaitu, kamus) dari $\Sigma^m.$ Jika kita memikirkan fungsi $f$ sebagai mewakili urutan $2^n$ bilangan bulat yang dikodekan sebagai string panjang $m$ dalam notasi biner yang bisa diakses secara random, masalahnya adalah menghitung minimum dari bilangan bulat ini.

Kita juga mempertimbangkan masalah query di mana kita memiliki janji pada input. Artinya, kita diberikan semacam jaminan pada input, dan kita tidak bertanggung jawab atas apa yang terjadi ketika jaminan ini tidak terpenuhi. Cara lain untuk mendeskripsikan jenis masalah ini adalah dengan mengatakan bahwa beberapa fungsi input (yang tidak memenuhi janji) dianggap sebagai input "don't care". Tidak ada persyaratan sama sekali yang ditempatkan pada algoritma ketika mereka diberikan input "don't care".

Berikut satu contoh masalah dengan janji:

• Pencarian unik. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma,$ dan kita dijanjikan bahwa ada tepat satu string $z\in\Sigma^n$ yang $f(z) = 1,$ dengan $f(x) = 0$ untuk semua string $x\neq z.$ Tugasnya adalah menemukan string unik $z$ ini.

Keempat contoh yang baru saja dijelaskan bersifat alami, dalam arti bahwa mudah untuk dideskripsikan dan kita bisa membayangkan berbagai situasi atau konteks di mana mereka bisa muncul.

Sebaliknya, beberapa masalah query tidaklah "alami" seperti ini sama sekali. Bahkan, dalam studi model query, kita terkadang membuat masalah yang sangat rumit dan sangat dibuat-buat di mana sulit membayangkan bahwa seseorang pernah benar-benar ingin menyelesaikannya dalam praktik. Namun ini bukan berarti masalahnya tidak menarik! Hal-hal yang mungkin tampak dibuat-buat atau tidak alami pada awalnya bisa memberikan petunjuk tak terduga atau menginspirasi ide-ide baru. Algoritma kuantum Shor untuk pemfaktoran, yang terinspirasi oleh algoritma Simon, adalah contoh yang bagus. Ini juga merupakan bagian penting dari studi model query untuk mencari ekstrem, yang bisa menerangi potensi keunggulan maupun keterbatasan komputasi kuantum.

Gate query

Saat kita mendeskripsikan komputasi dengan sirkuit, query dibuat oleh gate khusus yang disebut query gate.

Cara paling sederhana untuk mendefinisikan query gate untuk sirkuit Boolean klasik adalah dengan cukup mengizinkan mereka menghitung fungsi input $f$ secara langsung, seperti yang disarankan gambar berikut.

Ketika sirkuit Boolean dibuat untuk masalah query, fungsi input $f$ diakses melalui gate ini, dan jumlah query yang dibuat sirkuit adalah cukup dengan jumlah query gate yang muncul dalam sirkuit. Wire input dari sirkuit Boolean itu sendiri diinisialisasi ke nilai tetap, yang harus dianggap sebagai bagian dari algoritma (berbeda dengan menjadi input untuk masalah).

Misalnya, berikut sirkuit Boolean dengan query gate klasik yang memecahkan masalah paritas yang dijelaskan di atas untuk fungsi berbentuk $f:\Sigma\rightarrow\Sigma$:

Algoritma ini membuat dua query karena ada dua query gate. Cara kerjanya adalah fungsi $f$ di-query pada dua input yang mungkin, $0$ dan $1,$ dan hasilnya dimasukkan ke sirkuit Boolean yang menghitung XOR. (Sirkuit khusus ini muncul sebagai contoh sirkuit Boolean dalam pelajaran Sirkuit kuantum dari kursus Dasar-dasar informasi kuantum.)

Untuk sirkuit kuantum, definisi query gate ini tidak berfungsi, karena gate ini akan non-uniter untuk beberapa pilihan fungsi $f.$ Jadi, yang kita lakukan sebagai gantinya adalah mendefinisikan query gate uniter yang beroperasi seperti yang disarankan gambar ini pada status basis standar:

Di sini, asumsi kita adalah bahwa $x\in\Sigma^n$ dan $y\in\Sigma^m$ adalah string sembarang. Notasi $y\oplus f(x)$ mengacu pada exclusive-OR bitwise dari dua string, yang memiliki panjang $m$ dalam kasus ini. Misalnya, $001 \oplus 101 = 100.$

Secara intuitif, yang dilakukan gate $U_f$ (untuk fungsi $f$ yang dipilih) adalah menggemakan string input atas $x$ dan meng-XOR nilai fungsi $f(x)$ ke string input bawah $y,$ yang merupakan operasi uniter untuk setiap pilihan fungsi $f.$ Sebenarnya, ini adalah operasi deterministik, dan merupakan inversnya sendiri. Ini menyiratkan bahwa, sebagai matriks, $U_f$ selalu merupakan matriks permutasi, yaitu matriks dengan satu $1$ di setiap baris dan setiap kolom, dengan semua entri lainnya bernilai $0.$ Menerapkan matriks permutasi ke vektor sekadar mengacak entri vektor (karena itu istilah matriks permutasi), dan oleh karena itu tidak mengubah norma Euclidean vektor tersebut — mengungkapkan bahwa matriks permutasi selalu uniter.

Perlu ditekankan bahwa, ketika kita menganalisis algoritma query dengan cukup menghitung jumlah query yang dibuat algoritma query, kita sepenuhnya mengabaikan kesulitan membangun query gate secara fisik — baik untuk versi klasik maupun kuantum yang baru saja dijelaskan. Secara intuitif, konstruksi query gate adalah bagian dari persiapan input, bukan bagian dari menemukan solusi.

Itu mungkin tampak tidak masuk akal, tetapi kita harus ingat bahwa kita tidak mencoba mendeskripsikan komputasi praktis atau memperhitungkan sepenuhnya sumber daya yang diperlukan. Melainkan, kita mendefinisikan model teoretis yang membantu menerangi potensi keunggulan komputasi kuantum. Kita akan memiliki lebih banyak hal yang bisa dikatakan tentang poin ini dalam pelajaran berikutnya ketika kita beralih ke model komputasi yang lebih standar di mana input diberikan secara eksplisit ke sirkuit sebagai string biner.