Model pertanyaan pengkomputeran

Apabila kita memodelkan pengkomputeran dalam istilah matematik, kita biasanya memikirkan jenis proses yang digambarkan dalam rajah berikut, di mana maklumat diberikan sebagai input, pengiraan berlaku, dan output dihasilkan.

Walaupun benar bahawa komputer yang kita gunakan hari ini sentiasa menerima input dan menghasilkan output, pada dasarnya berinteraksi dengan kita dan komputer lain dengan cara yang tidak digambarkan oleh rajah tersebut, niat di sini bukan untuk mewakili operasi berterusan komputer. Sebaliknya, ia adalah untuk mencipta abstraksi pengkomputeran yang mudah, memberi tumpuan kepada tugas pengkomputeran yang terpencil. Sebagai contoh, input mungkin mengekodkan nombor, vektor, matriks, graf, penerangan molekul, atau sesuatu yang lebih kompleks, manakala output mengekodkan penyelesaian kepada tugas pengkomputeran yang kita fikirkan.

Perkara utamanya ialah input diberikan kepada pengiraan, biasanya dalam bentuk rentetan binari, tanpa sebahagiaan pun disembunyikan.

Penerangan model

Dalam model pertanyaan pengkomputeran, keseluruhan input tidak diberikan kepada pengiraan seperti dalam model yang lebih standard yang dicadangkan di atas. Sebaliknya, input disediakan dalam bentuk fungsi, yang diakses oleh pengiraan melalui pertanyaan. Sebagai alternatif, kita boleh melihat pengiraan dalam model pertanyaan sebagai mempunyai capaian rawak kepada bit (atau segmen bit) input.

Kita sering merujuk input sebagai disediakan oleh oracle atau kotak hitam dalam konteks model pertanyaan. Kedua-dua istilah mencadangkan bahawa penerangan lengkap input disembunyikan daripada pengiraan, dengan satu-satunya cara untuk mengaksesnya adalah dengan bertanya soalan. Seolah-olah kita sedang berunding dengan Oracle di Delphi tentang input: dia tidak akan memberitahu kita semua yang dia tahu, dia hanya menjawab soalan tertentu. Istilah kotak hitam masuk akal terutamanya apabila kita berfikir tentang input sebagai diwakili oleh fungsi; kita tidak boleh melihat ke dalam fungsi dan memahami cara ia berfungsi, kita hanya boleh menilainya pada argumen yang kita pilih.

Kita akan bekerja secara eksklusif dengan rentetan binari dalam pelajaran ini, berbeza dengan rentetan yang mengandungi simbol berbeza, jadi mari kita tulis $\Sigma = \{0,1\}$ selepas ini untuk merujuk kepada abjad binari bagi kemudahan. Kita akan memikirkan pelbagai masalah pengkomputeran, dengan beberapa contoh mudah yang diterangkan tidak lama lagi, tetapi untuk semua masalah tersebut input akan diwakili oleh fungsi yang berbentuk

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

untuk dua integer positif $n$ dan $m.$ Secara semula jadi, kita boleh memilih nama lain sebagai ganti $f,$ tetapi kita akan menggunakan $f$ sepanjang pelajaran ini.

Untuk mengatakan bahawa pengiraan membuat pertanyaan bermakna bahawa beberapa rentetan $x \in \Sigma^n$ dipilih, dan kemudian rentetan $f(x)\in\Sigma^m$ disediakan kepada pengiraan oleh oracle. Cara tepat ini berfungsi untuk algoritma kuantum akan dibincangkan tidak lama lagi — kita perlu memastikan ini boleh dilakukan dengan operasi kuantum uniter yang membolehkan pertanyaan dibuat dalam superposisi — tetapi buat masa ini kita boleh memikirkannya secara intuitif pada tahap tinggi.

Akhirnya, cara kita mengukur kecekapan algoritma pertanyaan adalah mudah: kita akan mengira bilangan pertanyaan yang diperlukan. Ini berkaitan dengan masa yang diperlukan untuk melaksanakan pengiraan, tetapi tidak sama persis kerana kita mengabaikan masa untuk operasi selain pertanyaan, dan kita juga menganggap setiap pertanyaan mempunyai kos unit. Kita boleh mengambil kira operasi selain pertanyaan jika kita mahukan (dan ini kadangkala dilakukan), tetapi mengehadkan perhatian kita hanya kepada bilangan pertanyaan membantu memudahkan perkara.

Contoh masalah pertanyaan

Berikut adalah beberapa contoh mudah masalah pertanyaan.

• OR. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma$ (jadi $m=1$ untuk masalah ini). Tugasnya adalah untuk mengeluarkan $1$ jika terdapat rentetan $x\in\Sigma^n$ di mana $f(x) = 1,$ dan untuk mengeluarkan $0$ jika tiada rentetan sedemikian. Jika kita memikirkan fungsi $f$ sebagai mewakili jujukan $2^n$ bit yang kita ada capaian rawak, masalahnya adalah untuk mengira OR bagi bit-bit ini.

• Pariti. Fungsi input sekali lagi berbentuk $f:\Sigma^n \rightarrow \Sigma.$ Tugasnya adalah untuk menentukan sama ada bilangan rentetan $x\in\Sigma^n$ di mana $f(x) = 1$ adalah genap atau ganjil. Secara tepat, output yang diperlukan adalah $0$ jika set $\{x\in\Sigma^n : f(x) = 1\}$ mempunyai bilangan elemen yang genap dan $1$ jika ia mempunyai bilangan elemen yang ganjil. Jika kita memikirkan fungsi $f$ sebagai mewakili jujukan $2^n$ bit yang kita ada capaian rawak, masalahnya adalah untuk mengira pariti (atau XOR eksklusif) bagi bit-bit ini.

• Minimum. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma^m$ untuk sebarang pilihan integer positif $n$ dan $m.$ Output yang diperlukan adalah rentetan $y \in \{f(x) : x\in\Sigma^n\}$ yang muncul pertama dalam susunan leksikografik (iaitu, susunan kamus) bagi $\Sigma^m.$ Jika kita memikirkan fungsi $f$ sebagai mewakili jujukan $2^n$ integer yang dikodkan sebagai rentetan panjang $m$ dalam notasi binari yang kita ada capaian rawak, masalahnya adalah untuk mengira minimum integer-integer ini.

Kita juga mempertimbangkan masalah pertanyaan di mana kita mempunyai janji pada input. Maksudnya ialah kita diberi sejenis jaminan pada input, dan kita tidak bertanggungjawab terhadap apa yang berlaku apabila jaminan ini tidak dipenuhi. Cara lain untuk menerangkan jenis masalah ini ialah mengatakan bahawa beberapa fungsi input (yang janji tidak dipenuhi) dianggap sebagai input "tidak kisah". Tiada keperluan langsung diletakkan pada algoritma apabila ia diberikan input "tidak kisah".

Berikut adalah satu contoh masalah dengan janji:

• Carian unik. Fungsi input berbentuk $f:\Sigma^n \rightarrow \Sigma,$ dan kita dijanjikan bahawa terdapat tepat satu rentetan $z\in\Sigma^n$ di mana $f(z) = 1,$ dengan $f(x) = 0$ untuk semua rentetan $x\neq z.$ Tugasnya adalah untuk mencari rentetan unik $z$ ini.

Keempat-empat contoh yang baru diterangkan adalah semula jadi, dalam erti kata ia mudah diterangkan dan kita boleh membayangkan pelbagai situasi atau konteks di mana ia mungkin timbul.

Sebaliknya, beberapa masalah pertanyaan tidak "semula jadi" begini. Malah, dalam kajian model pertanyaan, kita kadangkala menghasilkan masalah yang sangat kompleks dan direka-reka di mana sukar untuk membayangkan bahawa sesiapa pun sebenarnya mahu menyelesaikannya dalam amalan. Namun ini tidak bermakna masalah tersebut tidak menarik! Perkara yang mungkin kelihatan direka-reka atau tidak semula jadi pada mulanya boleh memberikan petunjuk yang tidak dijangka atau menginspirasi idea baru. Algoritma kuantum Shor untuk pemfaktoran, yang diilhamkan oleh algoritma Simon, adalah contoh yang baik. Ia juga merupakan bahagian penting dalam kajian model pertanyaan untuk mencari ekstrem, yang boleh menjelaskan kedua-dua potensi kelebihan dan had pengkomputeran kuantum.

Gerbang pertanyaan

Apabila kita menerangkan pengiraan dengan litar, pertanyaan dibuat oleh gerbang khas yang dipanggil gerbang pertanyaan.

Cara paling mudah untuk mentakrifkan gerbang pertanyaan untuk litar Boolean klasik adalah dengan membenarkan ia mengira fungsi input $f$ secara terus, seperti yang dicadangkan oleh rajah berikut.

Apabila litar Boolean dicipta untuk masalah pertanyaan, fungsi input $f$ diakses melalui gerbang-gerbang ini, dan bilangan pertanyaan yang dibuat oleh litar itu hanyalah bilangan gerbang pertanyaan yang muncul dalam litar. Wayar input litar Boolean itu sendiri dimulakan kepada nilai tetap, yang harus dianggap sebagai sebahagian daripada algoritma (berbanding input kepada masalah).

Sebagai contoh, berikut adalah litar Boolean dengan gerbang pertanyaan klasik yang menyelesaikan masalah pariti yang diterangkan di atas untuk fungsi berbentuk $f:\Sigma\rightarrow\Sigma$:

Algoritma ini membuat dua pertanyaan kerana terdapat dua gerbang pertanyaan. Cara ia berfungsi ialah fungsi $f$ ditanya pada dua kemungkinan input, $0$ dan $1,$ dan hasilnya dimasukkan ke dalam litar Boolean yang mengira XOR. (Litar khusus ini muncul sebagai contoh litar Boolean dalam pelajaran Litar kuantum dalam kursus Asas maklumat kuantum.)

Untuk litar kuantum, definisi gerbang pertanyaan ini tidak berfungsi, kerana gerbang-gerbang ini akan menjadi bukan-uniter untuk sesetengah pilihan fungsi $f.$ Jadi, apa yang kita lakukan sebaliknya adalah mentakrifkan gerbang pertanyaan uniter yang beroperasi seperti yang dicadangkan rajah ini pada keadaan asas standard:

Di sini, andaian kita ialah $x\in\Sigma^n$ dan $y\in\Sigma^m$ adalah rentetan arbitrari. Notasi $y\oplus f(x)$ merujuk kepada XOR bitwise dua rentetan, yang mempunyai panjang $m$ dalam kes ini. Sebagai contoh, $001 \oplus 101 = 100.$

Secara intuitif, apa yang gerbang $U_f$ lakukan (untuk sebarang fungsi $f$ yang dipilih) adalah menggemakan rentetan input atas $x$ dan meng-XOR nilai fungsi $f(x)$ ke atas rentetan input bawah $y,$ yang merupakan operasi uniter untuk setiap pilihan fungsi $f.$ Malah, ia adalah operasi deterministik, dan ia adalah inversnya sendiri. Ini bermakna bahawa, sebagai matriks, $U_f$ sentiasa merupakan matriks permutasi, iaitu matriks dengan satu $1$ tunggal dalam setiap baris dan setiap lajur, dengan semua entri lain bernilai $0.$ Menggunakan matriks permutasi pada vektor hanya mengacak entri vektor (oleh itu istilah matriks permutasi), dan oleh itu tidak mengubah norma Euclidean vektor tersebut — mendedahkan bahawa matriks permutasi sentiasa uniter.

Perlu ditekankan bahawa apabila kita menganalisis algoritma pertanyaan dengan hanya mengira bilangan pertanyaan yang dibuat oleh algoritma pertanyaan, kita sepenuhnya mengabaikan kesukaran membina gerbang pertanyaan secara fizikal — untuk kedua-dua versi klasik dan kuantum yang baru diterangkan. Secara intuitif, pembinaan gerbang pertanyaan adalah sebahagian daripada penyediaan input, bukan sebahagian daripada mencari penyelesaian.

Itu mungkin kelihatan tidak munasabah, tetapi kita mesti ingat bahawa kita tidak cuba menerangkan pengkomputeran praktikal atau mengambil kira sepenuhnya sumber yang diperlukan. Sebaliknya, kita mendefinisikan model teoritikal yang membantu menjelaskan potensi kelebihan pengkomputeran kuantum. Kita akan mempunyai lebih banyak perkara untuk dikatakan tentang perkara ini dalam pelajaran selepas ini apabila kita menumpukan perhatian kepada model pengkomputeran yang lebih standard di mana input diberikan secara eksplisit kepada litar sebagai rentetan binari.