Mengukur biaya komputasional

Selanjutnya, kita akan membahas kerangka matematis yang dapat digunakan untuk mengukur biaya komputasional, dengan fokus sempit pada kebutuhan kursus ini. Analisis algoritma dan kompleksitas komputasional adalah subjek tersendiri, dan masih banyak lagi yang bisa dikatakan tentang gagasan-gagasan ini.

Sebagai titik awal, pertimbangkan gambar berikut dari pelajaran sebelumnya, yang merepresentasikan abstraksi tingkat tinggi dari sebuah komputasi.

Komputasi itu sendiri bisa dimodelkan atau dijelaskan dalam berbagai cara, seperti dengan program komputer yang ditulis dalam Python, mesin Turing, rangkaian Boolean, atau rangkaian kuantum. Fokus kita adalah pada rangkaian (baik Boolean maupun kuantum).

Pengkodean dan panjang input

Mari kita mulai dengan input dan output dari masalah komputasional, yang kita asumsikan berupa string biner. Simbol yang berbeda bisa digunakan, tetapi kita akan menjaga hal-hal tetap sederhana untuk tujuan diskusi ini dengan membatasi perhatian kita pada input dan output string biner. Melalui string biner, kita bisa mengkode berbagai objek menarik yang berkaitan dengan masalah yang ingin kita selesaikan, seperti angka, vektor, matriks, dan graf, serta daftar dari objek-objek ini dan lainnya.

Misalnya, untuk mengkode bilangan bulat non-negatif, kita bisa menggunakan notasi biner. Tabel berikut mencantumkan pengkodean biner dari sembilan bilangan bulat non-negatif pertama, bersama dengan panjang (yang berarti jumlah total bit) dari setiap pengkodean.

Angka	Pengkodean biner	Panjang
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Kita bisa dengan mudah memperluas pengkodean ini untuk menangani bilangan bulat positif dan negatif dengan menambahkan bit tanda ke representasi jika kita mau. Terkadang juga lebih mudah untuk memungkinkan representasi biner dari bilangan bulat non-negatif memiliki leading zero, yang tidak mengubah nilai yang dikodekan tetapi bisa memungkinkan representasi mengisi string atau kata dengan ukuran tetap.

Menggunakan notasi biner untuk merepresentasikan bilangan bulat non-negatif adalah hal yang umum dan efisien, tetapi jika kita mau, kita bisa memilih cara yang berbeda untuk merepresentasikan bilangan bulat non-negatif menggunakan string biner, seperti yang disarankan dalam tabel berikut. Spesifikasi dari alternatif-alternatif ini tidak penting untuk diskusi ini — intinya hanya untuk memperjelas bahwa kita memang memiliki pilihan untuk pengkodean yang kita gunakan.

Angka	Pengkodean unary	Pengkodean leksikografi
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(Dalam tabel ini, simbol $\varepsilon$ merepresentasikan string kosong, yang tidak memiliki simbol di dalamnya dan panjangnya sama dengan nol. Tentu saja, untuk menghindari sumber kebingungan yang jelas, kita menggunakan simbol khusus seperti $\varepsilon$ untuk merepresentasikan string kosong daripada benar-benar tidak menulis apa-apa.)

Jenis input lainnya, seperti vektor dan matriks, atau objek yang lebih rumit seperti deskripsi molekul, juga bisa dikodekan sebagai string biner. Sama seperti yang kita lakukan untuk bilangan bulat non-negatif, berbagai skema pengkodean yang berbeda dapat dipilih atau diciptakan. Untuk skema apa pun yang kita buat untuk mengkode input ke masalah tertentu, kita menginterpretasikan panjang string input sebagai merepresentasikan ukuran instance masalah yang sedang dipecahkan.

Misalnya, jumlah bit yang diperlukan untuk mengekspresikan bilangan bulat non-negatif $N$ dalam notasi biner, yang kadang dilambangkan $\operatorname{lg}(N),$ diberikan oleh rumus berikut.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Dengan mengasumsikan bahwa kita menggunakan notasi biner untuk mengkode input ke masalah faktorisasi integer, panjang input untuk angka $N$ oleh karena itu adalah $\operatorname{lg}(N).$ Perhatikan, khususnya, bahwa panjang (atau ukuran) input $N$ bukan $N$ itu sendiri; ketika $N$ besar kita tidak memerlukan hampir sebanyak bit untuk mengekspresikan $N$ dalam notasi biner.

Dari sudut pandang yang benar-benar formal, setiap kali kita mempertimbangkan masalah atau tugas komputasional, harus dipahami bahwa skema tertentu telah dipilih untuk mengkode objek apa pun yang diberikan sebagai input atau diproduksi sebagai output. Ini memungkinkan komputasi yang memecahkan masalah menarik untuk dilihat secara abstrak sebagai transformasi dari input string biner ke output string biner.

Detail tentang bagaimana objek dikodekan sebagai string biner pasti penting bagi komputasi ini pada beberapa tingkat. Biasanya, meski begitu, kita tidak terlalu khawatir tentang detail-detail ini saat kita menganalisis biaya komputasional, sehingga kita bisa menghindari masuk ke detail yang kurang penting. Alasan dasarnya adalah bahwa kita mengharapkan biaya komputasional dari konversi bolak-balik antara skema pengkodean yang "wajar" menjadi tidak signifikan dibandingkan dengan biaya memecahkan masalah yang sebenarnya. Dalam situasi di mana hal ini tidak berlaku, detail dapat (dan harus) diperjelas.

Misalnya, komputasi yang sangat sederhana mengkonversi antara representasi biner dari bilangan bulat non-negatif dan pengkodean leksikografinya (yang tidak kami jelaskan secara detail, tetapi dapat disimpulkan dari tabel di atas). Untuk alasan ini, biaya komputasional dari faktorisasi integer tidak akan berbeda secara signifikan jika kita memutuskan untuk beralih dari menggunakan salah satu pengkodean ini ke yang lain untuk input $N.$ Di sisi lain, mengkode bilangan bulat non-negatif dalam notasi unary menimbulkan blow-up eksponensial dalam jumlah total simbol yang diperlukan, dan kita tidak akan menganggapnya sebagai skema pengkodean yang "wajar" untuk alasan ini.

Operasi dasar

Sekarang mari kita pertimbangkan komputasi itu sendiri, yang direpresentasikan oleh persegi panjang biru dalam gambar di atas. Cara kita mengukur biaya komputasional adalah dengan menghitung jumlah operasi dasar yang diperlukan oleh setiap komputasi. Secara intuitif, operasi dasar adalah operasi yang melibatkan sejumlah kecil bit atau qubit yang tetap, yang dapat dilakukan dengan cepat dan mudah — seperti menghitung AND dari dua bit. Sebaliknya, menjalankan fungsi factorint tidak secara wajar dipandang sebagai operasi dasar.

Secara formal, ada pilihan yang berbeda untuk apa yang merupakan operasi dasar tergantung pada model komputasional yang digunakan. Fokus kita adalah pada model rangkaian, dan khususnya rangkaian kuantum dan Boolean.

Set gate universal

Untuk model komputasi berbasis rangkaian, biasanya setiap gate dipandang sebagai operasi dasar. Ini mengarah pada pertanyaan tentang gate mana yang tepat yang kita izinkan dalam rangkaian kita. Dengan fokus sejenak pada rangkaian kuantum, kita telah melihat beberapa gate sejauh ini dalam seri ini, termasuk gate $X,$ $Y,$ $Z,$ $H,$ $S,$ dan $T$, gate swap, versi terkontrol dari gate (termasuk gate controlled-NOT, Toffoli, dan Fredkin), serta gate yang merepresentasikan pengukuran basis standar. Dalam konteks permainan CHSH kita juga melihat beberapa gate rotasi tambahan.

Kita juga membahas gate query dalam konteks model query, dan kita juga melihat bahwa operasi uniter mana pun $U,$ yang bekerja pada sejumlah qubit, dapat dipandang sebagai gate jika kita mau — tetapi kita akan mengabaikan kedua opsi ini untuk keperluan diskusi ini. Kita tidak akan bekerja dalam model query (meskipun implementasi gate query menggunakan operasi dasar dibahas nanti dalam pelajaran), dan memandang gate uniter sewenang-wenang, yang berpotensi bekerja pada jutaan qubit, sebagai operasi dasar tidak mengarah pada gagasan biaya komputasional yang bermakna atau realistis.

Dengan tetap menggunakan gate kuantum yang beroperasi pada jumlah qubit kecil, satu pendekatan untuk menentukan mana yang dianggap dasar adalah dengan merumuskan kriteria yang tepat — tetapi ini bukan pendekatan standar atau yang akan kita ambil. Sebaliknya, kita cukup membuat pilihan.

Ini adalah satu pilihan standar, yang akan kita adopsi sebagai set gate default untuk rangkaian kuantum:

• Gate uniter qubit tunggal dari daftar ini: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ dan $T^{\dagger}$
• Gate Controlled-NOT
• Pengukuran basis standar qubit tunggal

Alternatif umum adalah memandang gate Toffoli, Hadamard, dan $S$ sebagai dasar, selain pengukuran basis standar. Terkadang semua gate qubit tunggal dipandang sebagai dasar, meskipun ini memang mengarah pada model yang tidak realistis kuat ketika akurasi pelaksanaan gate tidak diperhitungkan dengan benar.

Gate uniter dalam koleksi default kita membentuk apa yang disebut set gate universal. Ini berarti bahwa kita dapat mendekati operasi uniter apa pun pada sejumlah qubit apa pun ke derajat akurasi apa pun yang kita inginkan, menggunakan rangkaian yang terdiri dari gate-gate ini saja. Untuk memperjelas, definisi universalitas tidak menempatkan persyaratan pada biaya aproksimasi tersebut, yang berarti jumlah gate dari set kita yang kita butuhkan. Memang, argumen yang cukup sederhana berdasarkan gagasan matematis tentang ukuran mengungkapkan bahwa sebagian besar operasi uniter pasti memiliki biaya yang sangat tinggi. Membuktikan universalitas set gate kuantum bukanlah hal yang mudah dan tidak akan dibahas dalam kursus ini.

Untuk rangkaian Boolean, kita akan mengambil gate AND, OR, NOT, dan FANOUT sebagai gate yang merepresentasikan operasi dasar. Kita tidak benar-benar memerlukan gate AND dan gate OR — kita bisa menggunakan hukum De Morgan untuk mengkonversi dari salah satu ke yang lain dengan menempatkan gate NOT pada semua tiga kabel input/output — tetapi tetap saja biasa dan nyaman untuk mengizinkan keduanya gate AND maupun OR. Gate AND, OR, NOT, dan FANOUT membentuk set universal untuk komputasi deterministik, yang berarti bahwa fungsi apa pun dari sejumlah bit input tetap ke sejumlah bit output tetap dapat diimplementasikan dengan gate-gate ini.

Prinsip pengukuran tertunda

Gate pengukuran basis standar dapat muncul dalam rangkaian kuantum, tetapi kadang-kadang mudah untuk menundanya hingga akhir. Ini memungkinkan kita untuk memandang komputasi kuantum sebagai terdiri dari bagian uniter (yang merepresentasikan komputasi itu sendiri), diikuti oleh fase baca-keluar sederhana di mana qubit diukur dan hasilnya dikeluarkan. Ini selalu dapat dilakukan, asalkan kita bersedia menambahkan qubit tambahan untuk setiap pengukuran basis standar. Pada gambar berikut, rangkaian di sebelah kanan menggambarkan bagaimana ini dapat dilakukan untuk gate di sebelah kiri.

Secara khusus, bit klasikal dalam rangkaian di sebelah kiri digantikan oleh qubit di sebelah kanan (diinisialisasi ke state $\vert 0\rangle$), dan pengukuran basis standar digantikan oleh gate controlled-NOT, diikuti oleh pengukuran basis standar pada qubit bawah. Intinya adalah bahwa pengukuran basis standar dalam rangkaian di sebelah kanan dapat didorong ke akhir rangkaian. Jika bit klasikal dalam rangkaian di sebelah kiri kemudian digunakan sebagai bit kontrol, kita bisa menggunakan qubit bawah dalam rangkaian di sebelah kanan sebagai kontrol sebagai gantinya, dan efek keseluruhannya akan sama. (Kita mengasumsikan bahwa bit klasikal dalam rangkaian di sebelah kiri tidak ditimpa setelah pengukuran berlangsung oleh pengukuran lain — tetapi jika itu terjadi, kita selalu bisa menggunakan bit klasikal baru daripada menimpa yang digunakan untuk pengukuran sebelumnya.)

Ukuran dan kedalaman rangkaian

Ukuran rangkaian

Jumlah total gate dalam rangkaian disebut sebagai ukuran rangkaian tersebut. Dengan demikian, dengan mengasumsikan bahwa gate dalam rangkaian kita merepresentasikan operasi dasar, ukuran rangkaian merepresentasikan jumlah operasi dasar yang diperlukan — atau, dengan kata lain, biaya komputasionalnya. Kita menulis $\operatorname{size}(C)$ untuk merujuk ke ukuran rangkaian tertentu $C.$

Misalnya, pertimbangkan rangkaian Boolean berikut untuk menghitung XOR dari dua bit.

Ukuran rangkaian ini adalah 7 karena ada 7 gate secara total. (Operasi Fanout tidak selalu dihitung sebagai gate, tetapi untuk keperluan pelajaran ini kita akan menghitungnya sebagai gate.)

Waktu, biaya, dan kedalaman rangkaian

Waktu adalah sumber daya yang sangat penting, atau batasan pembatas, untuk komputasi. Contoh-contoh di atas, seperti tugas memfaktorkan RSA1024, memperkuat sudut pandang ini. Fungsi factorint tidak gagal untuk memfaktorkan RSA1024 per se, hanya saja kita tidak memiliki cukup waktu untuk membiarkannya selesai.

Gagasan biaya komputasional, sebagai jumlah operasi dasar yang diperlukan untuk melakukan komputasi, dimaksudkan sebagai proksi abstrak untuk waktu yang diperlukan untuk mengimplementasikan komputasi. Setiap operasi dasar memerlukan sejumlah waktu tertentu untuk dilakukan, dan semakin banyak operasi yang diperlukan komputasi, semakin lama waktu yang dibutuhkan, setidaknya secara umum. Demi kesederhanaan, kita akan terus membuat asosiasi ini antara biaya komputasional dan waktu yang diperlukan untuk menjalankan algoritma.

Tetapi perhatikan bahwa ukuran rangkaian tidak selalu berkorespondensi langsung dengan berapa lama waktu yang dibutuhkan untuk dijalankan. Dalam rangkaian Boolean kita untuk menghitung XOR dari dua bit, misalnya, dua gate FANOUT bisa dilakukan secara bersamaan, begitu pula dua gate NOT, serta dua gate AND. Cara berbeda untuk mengukur efisiensi rangkaian, yang mempertimbangkan kemungkinan paralelisasi ini, adalah melalui kedalaman mereka. Ini adalah jumlah minimum lapisan gate yang diperlukan dalam rangkaian, di mana gate dalam setiap lapisan beroperasi pada kabel yang berbeda. Ekuivalen, kedalaman rangkaian adalah jumlah maksimum gate yang ditemui pada jalur mana pun dari kabel input ke kabel output. Untuk rangkaian di atas, misalnya, kedalamannya adalah 4.

Kedalaman rangkaian adalah salah satu cara untuk memformalkan waktu berjalan dari komputasi paralel. Ini adalah topik lanjutan, dan ada konstruksi rangkaian yang sangat canggih yang diketahui untuk meminimalkan kedalaman yang diperlukan untuk komputasi tertentu. Ada juga beberapa pertanyaan yang menarik dan belum terjawab mengenai kedalaman rangkaian. (Misalnya, banyak yang masih belum diketahui tentang kedalaman rangkaian yang diperlukan untuk menghitung GCD.) Kita tidak akan terlalu banyak membahas kedalaman rangkaian dalam seri ini, selain menyertakan beberapa fakta menarik tentang kedalaman rangkaian seiring berjalannya waktu, tetapi harus diakui dengan jelas bahwa paralelisasi adalah sumber potensial dari keunggulan komputasional.

Menetapkan biaya ke gate yang berbeda

Satu catatan terakhir tentang ukuran rangkaian dan biaya komputasional adalah bahwa mungkin untuk menetapkan biaya yang berbeda ke gate, daripada memandang setiap gate berkontribusi sama terhadap total biaya.

Misalnya, seperti yang sudah disebutkan, gate FANOUT sering dipandang gratis untuk rangkaian Boolean — artinya kita bisa memilih bahwa gate FANOUT memiliki biaya nol. Sebagai contoh lain, ketika kita bekerja dalam model query dan kita menghitung jumlah query yang dibuat oleh rangkaian ke fungsi input (dalam bentuk kotak hitam), kita secara efektif menetapkan biaya unit ke gate query dan biaya nol ke gate lain, seperti gate Hadamard. Contoh terakhir adalah bahwa kita kadang-kadang menetapkan biaya yang berbeda ke gate tergantung pada seberapa sulit mereka untuk diimplementasikan, yang bisa bervariasi tergantung pada hardware yang dipertimbangkan.

Meskipun semua opsi ini masuk akal dalam konteks yang berbeda, untuk pelajaran ini kita akan menjaga hal-hal tetap sederhana dan tetap menggunakan ukuran rangkaian sebagai representasi dari biaya komputasional.

Biaya sebagai fungsi dari panjang input

Kita terutama tertarik pada bagaimana biaya komputasional berskala seiring input menjadi semakin besar dan besar. Ini mengarah kita untuk merepresentasikan biaya algoritma sebagai fungsi dari panjang input.

Keluarga rangkaian

Input ke masalah komputasional tertentu dapat bervariasi dalam panjang, berpotensi menjadi sangat besar. Setiap rangkaian, di sisi lain, memiliki jumlah gate dan kabel yang tetap. Untuk alasan ini, ketika kita memikirkan algoritma dalam bentuk rangkaian, kita umumnya memerlukan keluarga rangkaian yang tak terbatas untuk merepresentasikan algoritma. Yang dimaksud dengan keluarga rangkaian adalah urutan rangkaian yang tumbuh dalam ukuran, memungkinkan input yang semakin besar untuk diakomodasi.

Misalnya, bayangkan kita memiliki algoritma klasikal untuk faktorisasi integer, seperti yang digunakan oleh factorint. Seperti semua algoritma klasikal, algoritma ini dapat diimplementasikan menggunakan rangkaian Boolean — tetapi untuk melakukannya kita akan memerlukan rangkaian terpisah untuk setiap panjang input yang mungkin. Jika kita melihat rangkaian yang dihasilkan untuk panjang input yang berbeda, kita akan melihat bahwa ukurannya secara alami tumbuh seiring panjang input tumbuh — mencerminkan fakta bahwa memfaktorkan bilangan bulat 4-bit jauh lebih mudah dan memerlukan jauh lebih sedikit operasi dasar daripada memfaktorkan bilangan bulat 1024-bit, misalnya.

Ini mengarah kita untuk merepresentasikan biaya komputasional dari sebuah algoritma dengan fungsi $t,$ yang didefinisikan sehingga $t(n)$ adalah jumlah gate dalam rangkaian yang mengimplementasikan algoritma untuk input $n$ bit. Dalam istilah yang lebih formal, sebuah algoritma dalam model rangkaian Boolean dijelaskan oleh urutan rangkaian $\{C_1, C_2, C_3,\ldots\},$ di mana $C_n$ memecahkan masalah apa pun yang kita bicarakan untuk input $n$-bit (atau, lebih umum, untuk input yang ukurannya diparameterisasi dengan cara tertentu oleh $n$), dan fungsi $t$ yang merepresentasikan biaya algoritma ini didefinisikan sebagai

$$t(n) = \operatorname{size}(C_n).$$

Untuk rangkaian kuantum situasinya serupa, di mana rangkaian yang semakin besar diperlukan untuk mengakomodasi string input yang semakin panjang.

Contoh: penjumlahan integer

Untuk menjelaskan lebih lanjut, mari kita luangkan waktu untuk mempertimbangkan masalah penjumlahan integer, yang jauh lebih sederhana dari faktorisasi integer atau bahkan menghitung GCD.

Penjumlahan integer

Input: bilangan bulat $N$ dan $M$
Output: $N+M$

Bagaimana kita bisa merancang rangkaian Boolean untuk memecahkan masalah ini?

Untuk menjaga hal-hal tetap sederhana, mari kita batasi perhatian kita pada kasus di mana $N$ dan $M$ keduanya adalah bilangan bulat non-negatif yang direpresentasikan oleh string $n$-bit menggunakan notasi biner. Kita akan mengizinkan sejumlah leading zero dalam pengkodean ini, sehingga

$$0\leq N,M\leq 2^n - 1.$$

Outputnya akan menjadi string biner $(n+1)$-bit yang merepresentasikan jumlahnya, yang merupakan jumlah bit maksimum yang kita butuhkan untuk mengekspresikan hasilnya.

Kita mulai dengan sebuah algoritma — algoritma standar untuk penjumlahan representasi biner — yang merupakan analogi basis $2$ dengan cara penjumlahan yang diajarkan di sekolah dasar/SD di seluruh dunia. Algoritma ini dapat diimplementasikan dengan rangkaian Boolean sebagai berikut.

Dimulai dari bit-bit paling tidak signifikan, kita bisa menghitung XOR mereka untuk menentukan bit paling tidak signifikan untuk jumlahnya. Kemudian kita menghitung bit carry, yang merupakan AND dari dua bit paling tidak signifikan dari $N$ dan $M.$ Terkadang dua operasi ini bersama-sama dikenal sebagai half adder.

Menggunakan rangkaian XOR yang telah kita lihat beberapa kali bersama dengan gate AND dan dua gate FANOUT, kita bisa membangun half adder dengan 10 gate. Jika karena suatu alasan kita berubah pikiran dan memutuskan untuk menyertakan gate XOR dalam set operasi dasar kita, kita akan membutuhkan 1 gate AND, 1 gate XOR, dan 2 gate FANOUT untuk membangun half adder.

Melanjutkan ke bit-bit yang lebih signifikan, kita bisa menggunakan prosedur yang serupa, tetapi kali ini termasuk bit carry dari setiap posisi sebelumnya ke dalam perhitungan kita. Dengan mengalirkan dua half adder dan mengambil OR dari bit carry yang mereka hasilkan, kita bisa membuat apa yang dikenal sebagai full adder.

Ini memerlukan 21 gate secara total: 2 gate AND, 2 gate XOR (masing-masing memerlukan 7 gate untuk diimplementasikan), satu gate OR, dan 4 gate FANOUT.

Akhirnya, dengan mengalirkan full adder, kita mendapatkan rangkaian Boolean untuk penjumlahan integer non-negatif. Misalnya, rangkaian berikut menghitung jumlah dua bilangan bulat 4-bit.

Secara umum, ini memerlukan

$$21 (n-1) + 10 = 21 n - 11$$

gate. Jika kita memutuskan untuk menyertakan gate XOR dalam set operasi dasar kita, kita akan membutuhkan $2n-1$ gate AND, $2n-1$ gate XOR, $n-1$ gate OR, dan $4n-2$ gate FANOUT, untuk total $9n-5$ gate. Jika selain itu kita memutuskan untuk tidak menghitung gate FANOUT, itu adalah $5n-3$ gate.

Notasi asimtotik

Di satu sisi, baik untuk mengetahui dengan tepat berapa banyak gate yang diperlukan untuk melakukan berbagai komputasi, seperti dalam contoh penjumlahan integer di atas. Detail-detail ini penting untuk benar-benar membangun rangkaian.

Di sisi lain, jika kita melakukan analisis di tingkat detail ini untuk semua komputasi yang kita minati, termasuk yang jauh lebih rumit dari penjumlahan, kita akan sangat cepat terkubur dalam detail. Untuk menjaga hal-hal tetap dapat dikelola, dan untuk secara sengaja menekan detail yang kurang penting, kita biasanya menggunakan notasi Big-O saat menganalisis algoritma. Melalui notasi ini kita bisa mengekspresikan orde di mana fungsi tumbuh.

Secara formal, jika kita memiliki dua fungsi $g(n)$ dan $h(n),$ kita menulis bahwa $g(n) = O(h(n))$ jika ada bilangan real positif $c > 0$ dan bilangan bulat positif $n_0$ sehingga

$$g(n) \leq c\cdot h(n)$$

untuk semua $n \geq n_0.$ Biasanya $h(n)$ dipilih sebagai ekspresi sesederhana mungkin, sehingga notasi dapat digunakan untuk mengungkapkan perilaku pembatas dari fungsi dalam istilah sederhana. Misalnya, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Notasi ini dapat diperluas ke fungsi yang memiliki banyak argumen dengan cara yang cukup langsung. Misalnya, jika kita memiliki dua fungsi $g(n,m)$ dan $h(n,m)$ yang didefinisikan pada bilangan bulat positif $n$ dan $m,$ kita menulis bahwa $g(n,m) = O(h(n,m))$ jika ada bilangan real positif $c > 0$ dan bilangan bulat positif $k_0$ sehingga

$$g(n,m) \leq c\cdot h(n,m)$$

setiap kali $n+m \geq k_0.$

Menghubungkan notasi ini dengan contoh penjumlahan integer non-negatif, kita menyimpulkan bahwa ada keluarga rangkaian Boolean $\{C_1, C_2,\ldots,\},$ di mana $C_n$ menjumlahkan dua bilangan bulat non-negatif $n$-bit bersama, sehingga $\operatorname{size}(C_n) = O(n).$ Ini mengungkapkan fitur paling esensial dari bagaimana biaya penjumlahan berskala dengan ukuran input: ia berskala linear.

Perhatikan juga bahwa ini tidak bergantung pada detail spesifik apakah kita menganggap gate XOR memiliki biaya unit atau biaya $7.$ Secara umum, menggunakan notasi Big-O memungkinkan kita membuat pernyataan tentang biaya komputasional yang tidak sensitif terhadap detail tingkat rendah seperti itu.

Contoh-contoh lainnya

Berikut adalah beberapa contoh lagi dari masalah-masalah dari teori bilangan komputasional, dimulai dengan perkalian.

Perkalian integer

Input: bilangan bulat $N$ dan $M$
Output: $NM$

Membuat rangkaian Boolean untuk masalah ini lebih sulit daripada membuat rangkaian untuk penjumlahan — tetapi dengan memikirkan algoritma perkalian standar, kita bisa menemukan rangkaian dengan ukuran $O(n^2)$ untuk masalah ini (dengan mengasumsikan $N$ dan $M$ keduanya direpresentasikan oleh representasi biner $n$-bit). Lebih umumnya, jika $N$ memiliki $n$ bit dan $M$ memiliki $m$ bit, ada rangkaian Boolean berukuran $O(nm)$ untuk mengalikan $N$ dan $M.$

Sebenarnya ada cara lain untuk mengalikan yang berskala lebih baik. Misalnya, algoritma perkalian Schönhage-Strassen dapat digunakan untuk membuat rangkaian Boolean untuk mengalikan dua bilangan bulat $n$-bit dengan biaya $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Kerumitan metode ini menyebabkan banyak overhead, bagaimanapun, membuatnya hanya praktis untuk angka yang memiliki puluhan ribu bit.

Masalah dasar lainnya adalah pembagian, yang kami interpretasikan sebagai menghitung kuosien dan sisa yang diberikan pembagi dan dividen integer.

Pembagian integer

Input: bilangan bulat $N$ dan $M\neq0$
Output: bilangan bulat $q$ dan $r$ yang memenuhi $0\leq r < |M|$ dan $N = q M + r$

Biaya pembagian integer mirip dengan perkalian: jika $N$ memiliki $n$ bit dan $M$ memiliki $m$ bit, ada rangkaian Boolean berukuran $O(nm)$ untuk memecahkan masalah ini. Dan seperti perkalian, metode yang secara asimtotik lebih unggul diketahui.

Kita sekarang bisa membandingkan algoritma yang diketahui untuk menghitung GCD dengan yang untuk penjumlahan dan perkalian. Algoritma Euclid untuk menghitung GCD dari bilangan bulat $n$-bit $N$ dan bilangan bulat $m$-bit $M$ memerlukan rangkaian Boolean berukuran $O(nm),$ mirip dengan algoritma standar untuk perkalian dan pembagian. Juga mirip dengan perkalian dan pembagian, ada algoritma GCD yang secara asimtotik lebih cepat — termasuk yang memerlukan $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operasi dasar untuk menghitung GCD dari dua bilangan bulat $n$-bit.

Komputasi yang agak lebih mahal yang muncul dalam teori bilangan adalah eksponen modular.

Eksponen modular integer

Input: bilangan bulat $N,$ $K,$ dan $M$ dengan $K\geq 0$ dan $M\geq 1$
Output: $N^K \hspace{1mm} (\text{mod }M)$

Dengan $N^K\hspace{1mm} (\text{mod }M)$ yang dimaksud adalah sisa ketika $N^K$ dibagi oleh $M,$ artinya bilangan bulat unik $r$ yang memenuhi $0\leq r < M$ dan $N^K = q M + r$ untuk beberapa bilangan bulat $q.$

Jika $N$ memiliki $n$ bit, $M$ memiliki $m$ bit, dan $K$ memiliki $k$ bit, masalah ini dapat diselesaikan dengan rangkaian Boolean berukuran $O(k m^2 + nm).$ Ini sama sekali tidak jelas. Solusinya bukan dengan terlebih dahulu menghitung $N^K$ lalu mengambil sisanya, yang akan mengharuskan penggunaan bit yang secara eksponensial banyak hanya untuk menyimpan angka $N^K.$ Sebaliknya, kita bisa menggunakan algoritma pangkat (yang secara bergantian dikenal sebagai metode biner dan repeated squaring), yang memanfaatkan representasi biner dari $K$ untuk melakukan seluruh komputasi modulo $M.$ Dengan mengasumsikan $N,$ $M,$ dan $K$ semuanya adalah bilangan $n$-bit, kita mendapatkan algoritma $O(n^3)$ — atau algoritma kubik. Dan sekali lagi, ada algoritma yang diketahui yang lebih rumit tetapi secara asimtotik lebih cepat.

Biaya faktorisasi integer

Berbeda dengan algoritma yang baru saja dibahas, algoritma yang diketahui untuk faktorisasi integer jauh lebih mahal — seperti yang mungkin kita harapkan dari diskusi sebelumnya dalam pelajaran.

Satu pendekatan sederhana untuk memfaktorkan adalah pembagian percobaan, di mana algoritma mencari melalui daftar $2,\ldots,\sqrt{N}$ untuk menemukan faktor prima dari input angka $N.$ Ini memerlukan iterasi $O(2^{n/2})$ dalam kasus terburuk ketika $N$ adalah bilangan $n$-bit. Setiap iterasi memerlukan pembagian percobaan, yang berarti $O(n^2)$ operasi dasar untuk setiap iterasi (menggunakan algoritma standar untuk pembagian integer). Kita berakhir dengan rangkaian berukuran $O(n^2 2^{n/2}),$ yang eksponensial dalam ukuran input $n.$

Ada algoritma untuk faktorisasi integer yang memiliki skala yang lebih baik. Number field sieve yang disebutkan sebelumnya, misalnya, yang merupakan algoritma yang menggunakan keacakan, secara umum diyakini (tetapi tidak terbukti secara ketat) memerlukan

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

operasi dasar untuk memfaktorkan bilangan bulat $n$-bit dengan probabilitas tinggi. Meskipun cukup signifikan bahwa $n$ dipangkatkan $1/3$ dalam eksponen ekspresi ini, fakta bahwa ia muncul dalam eksponen masih menjadi masalah yang menyebabkan skala yang buruk — dan menjelaskan sebagian mengapa RSA1024 tetap di luar domain penerapannya.

Biaya polinomial versus eksponensial

Algoritma klasikal untuk penjumlahan, perkalian, pembagian integer, dan menghitung faktor pembagi terbesar memungkinkan kita memecahkan masalah-masalah ini dalam sekejap untuk input dengan ribuan bit. Penjumlahan memiliki biaya linear sementara tiga masalah lainnya memiliki biaya kuadratik (atau biaya subkuadratik menggunakan algoritma asimtotik yang cepat). Eksponen modular lebih mahal tetapi masih bisa dilakukan dengan cukup efisien, dengan biaya kubik (atau biaya sub-kubik menggunakan algoritma asimtotik yang cepat).

Ini semua adalah contoh algoritma yang memiliki biaya polinomial, yang berarti mereka memiliki biaya $O(n^c)$ untuk beberapa pilihan konstanta tetap $c > 0.$ Sebagai perkiraan kasar orde pertama, algoritma yang memiliki biaya polinomial secara abstrak dipandang sebagai algoritma yang efisien.

Sebaliknya, algoritma klasikal yang diketahui untuk faktorisasi integer memiliki biaya eksponensial. Terkadang biaya number field sieve digambarkan sebagai sub-eksponensial karena $n$ dipangkatkan $1/3$ dalam eksponen, tetapi dalam teori kompleksitas lebih umum untuk mereservasi istilah ini untuk algoritma yang biayanya adalah

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

untuk setiap $\varepsilon > 0.$ Masalah-masalah yang disebut NP-complete adalah kelas masalah yang tidak diketahui memiliki (dan secara luas diperkirakan tidak memiliki) algoritma berbiaya polinomial. Formulasi berbasis rangkaian dari exponential-time hypothesis mengemukakan sesuatu yang bahkan lebih kuat, yaitu bahwa tidak ada masalah NP-complete yang dapat memiliki algoritma berbiaya sub-eksponensial.

Asosiasi algoritma berbiaya polinomial dengan algoritma efisien harus dipahami sebagai abstraksi yang longgar. Tentu saja, jika biaya algoritma berskala sebagai $n^{1000}$ atau $n^{1000000}$ untuk input berukuran $n,$ maka agak berlebihan untuk menggambarkan algoritma tersebut sebagai efisien. Namun, bahkan algoritma yang memiliki biaya yang berskala sebagai $n^{1000000}$ pasti melakukan sesuatu yang cerdas untuk menghindari biaya eksponensial, yang umumnya kita harapkan dari algoritma berdasarkan "brute force" atau "exhaustive search" dengan cara tertentu. Bahkan penyempurnaan canggih dari number field sieve, misalnya, gagal menghindari skala eksponensial dalam biaya ini. Algoritma berbiaya polinomial, di sisi lain, berhasil memanfaatkan struktur masalah dengan cara tertentu yang menghindari skala eksponensial.

Dalam praktiknya, identifikasi algoritma berbiaya polinomial untuk suatu masalah hanyalah langkah pertama menuju efisiensi yang sebenarnya. Melalui penyempurnaan algoritmik, algoritma berbiaya polinomial dengan eksponen besar kadang-kadang dapat ditingkatkan secara dramatis, menurunkan biaya ke skala polinomial yang lebih "wajar". Terkadang hal-hal menjadi lebih mudah ketika mereka diketahui mungkin — sehingga identifikasi algoritma berbiaya polinomial untuk suatu masalah juga dapat memiliki efek menginspirasi algoritma baru yang bahkan lebih efisien.

Saat kita mempertimbangkan keunggulan komputasi kuantum atas klasikal, pandangan kita umumnya pertama kali tertuju pada keunggulan eksponensial, atau setidaknya keunggulan super-polinomial — idealnya menemukan algoritma kuantum berbiaya polinomial untuk masalah yang tidak diketahui memiliki algoritma klasikal berbiaya polinomial. Keunggulan teoritis pada orde ini memiliki peluang terbesar untuk mengarah pada keunggulan praktis yang sebenarnya — tetapi mengidentifikasi keunggulan seperti itu adalah tantangan yang sangat sulit. Hanya beberapa contoh yang saat ini diketahui, tetapi pencarian terus berlanjut.

Keunggulan polinomial (tetapi tidak super-polinomial) dalam biaya komputasional kuantum atas klasikal juga menarik dan tidak boleh diabaikan — tetapi mengingat kesenjangan saat ini antara teknologi komputasi kuantum dan klasikal, mereka tampaknya kurang menarik saat ini. Namun suatu hari nanti, mereka bisa menjadi signifikan. Algoritma Grover, misalnya, yang dibahas dalam pelajaran selanjutnya, menawarkan keunggulan kuadratik dari kuantum atas klasikal untuk apa yang disebut unstructured searching, dan memiliki potensi untuk aplikasi yang luas.

Biaya tersembunyi dari komputasi rangkaian

Ada satu isu terakhir yang layak disebutkan, meskipun kita tidak akan mengkhawatirkannya lebih lanjut dalam kursus ini. Ada "biaya" komputasional yang "tersembunyi" saat kita bekerja dengan rangkaian, dan itu berkaitan dengan spesifikasi dari rangkaian itu sendiri. Seiring input menjadi semakin panjang, rangkaian yang semakin besar diperlukan — tetapi kita perlu mendapatkan deskripsi dari rangkaian-rangkaian ini entah bagaimana jika kita akan mengimplementasikannya.

Untuk semua contoh yang telah kita bahas, atau akan kita bahas dalam pelajaran berikutnya, ada algoritma yang mendasari dari mana rangkaian-rangkaian diturunkan. Biasanya rangkaian dalam keluarga mengikuti beberapa pola dasar yang mudah untuk diekstrapolasi ke input yang semakin besar, seperti mengalirkan full adder untuk membuat rangkaian Boolean untuk penjumlahan atau melakukan lapisan gate Hadamard dan gate lain dalam beberapa pola yang mudah dijelaskan.

Tetapi apa yang terjadi jika ada biaya komputasional yang melarang yang terkait dengan pola dalam rangkaian itu sendiri? Misalnya, deskripsi dari setiap anggota $C_n$ dalam keluarga rangkaian bisa, pada prinsipnya, ditentukan oleh beberapa fungsi dari $n$ yang sangat sulit dihitung.

Jawabannya adalah bahwa ini memang merupakan masalah — dan jadi kita harus menempatkan batasan tambahan pada keluarga rangkaian di luar memiliki biaya polinomial agar benar-benar merepresentasikan algoritma yang efisien. Properti uniformitas untuk rangkaian melakukan ini dengan menetapkan bahwa, dalam berbagai formulasi yang tepat, harus secara komputasional mudah untuk mendapatkan deskripsi dari setiap rangkaian dalam keluarga. Semua keluarga rangkaian yang akan kita bahas memang memiliki properti ini — tetapi ini tetap merupakan isu penting untuk diperhatikan secara umum saat mempelajari model rangkaian komputasi dari sudut pandang formal.