Pagsukat ng computational cost

Susunod, tatalakayin natin ang isang mathematical na balangkas para masukat ang computational cost, na nakatutok sa mga pangangailangan ng kursong ito. Ang pagsusuri ng mga algorithm at computational complexity ay malalim na mga paksa sa kanilang sarili, at marami pang masasabi tungkol sa mga konseptong ito.

Bilang panimula, tingnan ang sumusunod na figure mula sa nakaraang aralin, na kumakatawan sa isang napakataas na antas ng abstraksiyon ng isang computation.

Ang computation mismo ay maaaring i-modelo o ilarawan sa iba't ibang paraan, tulad ng isang computer program na nakasulat sa Python, isang Turing machine, isang Boolean circuit, o isang quantum circuit. Ang ating pokus ay magiging sa mga circuit (parehong Boolean at quantum).

Mga encoding at haba ng input

Simulan natin sa input at output ng isang computational na problema, na ating ipapalagay ay binary strings. Maaaring gumamit ng ibang mga simbolo, ngunit para sa simplisidad ng talakayan, ililimit natin ang ating pansin sa mga binary string na input at output. Sa pamamagitan ng mga binary string, maaari nating i-encode ang iba't ibang kawili-wiling mga bagay na kinabibilangan ng mga problemang gusto nating solusyunan, tulad ng mga numero, vector, matrix, at graph, pati na rin ang mga listahan ng mga ito at iba pang mga bagay.

Halimbawa, para i-encode ang mga non-negatibong integer, maaari tayong gumamit ng binary notation. Ang sumusunod na talahanayan ay naglalista ng binary encoding ng unang siyam na non-negatibong integer, kasama ang haba (ibig sabihin, ang kabuuang bilang ng mga bit) ng bawat encoding.

Numero	Binary encoding	Haba
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

Madali nating mapapalawak ang encoding na ito para mahawakan ang parehong positibo at negatibong integer sa pamamagitan ng pagdaragdag ng sign bit sa mga representasyon kung pipili tayo. Minsan din ay maginhawa na payagan ang mga binary na representasyon ng mga non-negatibong integer na magkaroon ng mga nangunguna (leading) na zero, na hindi nagbabago ng value na ine-encode ngunit nagbibigay-daan sa mga representasyon na mapuno ang isang string o word ng nakapirming laki.

Ang paggamit ng binary notation para kumatawan sa mga non-negatibong integer ay karaniwan at mahusay, ngunit kung gusto natin, maaari tayong pumili ng ibang paraan para kumatawan sa mga non-negatibong integer gamit ang mga binary string, tulad ng mga iminungkahi sa sumusunod na talahanayan. Hindi mahalaga ang mga detalye ng mga alternatibong ito sa talakayan na ito — ang punto lamang ay linawin na mayroon tayong mga pagpipilian para sa mga encoding na gagamitin natin.

Numero	Unary encoding	Lexicographic encoding
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

(Sa talahanayan na ito, ang simbolo na $\varepsilon$ ay kumakatawan sa walang laman na string, na walang mga simbolo at may haba na katumbas ng zero. Siyempre, para maiwasan ang isang malinaw na pinagkukunan ng kalituhan, gumagamit tayo ng espesyal na simbolo tulad ng $\varepsilon$ para kumatawan sa walang laman na string sa halip na literal na sumulat ng wala.)

Ang iba pang mga uri ng input, tulad ng mga vector at matrix, o mas kumplikadong mga bagay tulad ng mga paglalarawan ng mga molekula, ay maaari ring i-encode bilang mga binary string. Tulad ng ginawa natin para sa mga non-negatibong integer, maaaring pumili o mag-imbento ng iba't ibang encoding scheme. Para sa anumang scheme na ating maisip para i-encode ang mga input sa isang ibinigay na problema, itinuturing natin ang haba ng isang input string bilang kumakatawan sa laki ng instance ng problema na niresolusyunan.

Halimbawa, ang bilang ng mga bit na kailangan para ipahayag ang isang non-negatibong integer na $N$ sa binary notation, na kung minsan ay tinatawag na $\operatorname{lg}(N),$ ay ibinibigay ng sumusunod na formula.

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

Kung ipagpalagay na ginagamit natin ang binary notation para i-encode ang input sa problema ng integer factoring, ang haba ng input para sa numero na $N$ ay samakatuwid $\operatorname{lg}(N).$ Pansinin, sa partikular, na ang haba (o laki) ng input na $N$ ay hindi $N$ mismo; kapag malaki ang $N$, hindi natin kailangan ng ganito kadaming mga bit para ipahayag ang $N$ sa binary notation.

Mula sa isang mahigpit na pormal na pananaw, tuwing isinasaalang-alang natin ang isang computational na problema o gawain, dapat na maintindihan na ang isang tiyak na scheme ay napili para i-encode ang anumang mga bagay na ibinibigay bilang input o ginagawa bilang output. Nagbibigay-daan ito sa mga computation na naglulutas ng mga kawili-wiling problema na matingnan nang abstracto bilang mga transformasyon mula sa mga binary string na input patungo sa mga binary string na output.

Ang mga detalye ng kung paano ine-encode ang mga bagay bilang mga binary string ay kinakailangang mahalaga sa mga computation na ito sa isang antas. Karaniwan, gayunpaman, hindi tayo masyadong nag-aalala tungkol sa mga detalyeng ito kapag sinusuri natin ang computational cost, para maiwasan ang pag-deepdive sa mga pangalawang-antas na detalye. Ang pangunahing dahilan ay inaasahan nating ang computational cost ng pag-convert pabalik-balik sa pagitan ng mga "makatwirang" encoding scheme ay hindi gaanong mahalaga kumpara sa cost ng paglutas ng aktwal na problema. Sa mga sitwasyon na hindi ganito ang kaso, ang mga detalye ay maaari (at dapat) na linawin.

Halimbawa, ang isang napakasimpleng computation ay nagko-convert sa pagitan ng binary representation ng isang non-negatibong integer at ng lexicographic encoding nito (na hindi natin ipinaliwanag nang detalyado, ngunit maaaring ipahiwatig mula sa talahanayan sa itaas). Dahil dito, ang computational cost ng integer factoring ay hindi nangangailangan ng malaking pagbabago kung magpasya tayong lumipat mula sa paggamit ng isa sa mga encoding na ito sa isa pa para sa input na $N.$ Sa kabilang banda, ang pag-encode ng mga non-negatibong integer sa unary notation ay nagdudulot ng exponential na pagtaas sa kabuuang bilang ng mga simbolong kailangan, at hindi natin ito itinuturing na "makatwirang" encoding scheme dahil dito.

Mga elementary na operasyon

Ngayon tingnan natin ang computation mismo, na kinakatawan ng asul na parihaba sa figure sa itaas. Ang paraang susukatin natin ang computational cost ay ang pagbibilang ng bilang ng mga elementary na operasyon na kailangan ng bawat computation. Sa simpleng pagsasalita, ang isang elementary na operasyon ay isa na kinabibilangan ng maliit at nakapirming bilang ng mga bit o qubit, na maaaring isagawa nang mabilis at madali — tulad ng pag-compute ng AND ng dalawang bit. Sa kaibahan, ang pagpapatakbo ng function na factorint ay hindi makatwirang tinitingnan bilang isang elementary na operasyon.

Sa pormal na pagsasalita, may iba't ibang pagpipilian para sa kung ano ang bumubuo ng isang elementary na operasyon depende sa computational model na ginagamit. Ang ating pokus ay magiging sa mga circuit model, at partikular sa quantum at Boolean na mga circuit.

Mga universal gate set

Para sa mga circuit-based na modelo ng computation, karaniwan na ang bawat gate ay tinitingnan bilang isang elementary na operasyon. Nagdudulot ito ng tanong kung aling mga gate ang pinapayagan natin sa ating mga circuit. Nakatutok sa quantum circuits sa ngayon, nakita na natin ang ilang mga gate sa seryeng ito, kabilang ang $X,$ $Y,$ $Z,$ $H,$ $S,$ at $T$ na mga gate, swap gate, mga controlled na bersyon ng mga gate (kabilang ang controlled-NOT, Toffoli, at Fredkin na mga gate), pati na rin ang mga gate na kumakatawan sa mga standard basis measurement. Sa konteksto ng laro ng CHSH, nakita rin natin ang ilang karagdagang rotation gate.

Tinalakay din natin ang mga query gate sa konteksto ng query model, at nakita rin natin na ang anumang unitary na operasyon na $U,$ na kumikilos sa anumang bilang ng mga qubit, ay maaaring tingnan bilang isang gate kung pipili tayo — ngunit hindi natin isasaalang-alang ang parehong opsyon na ito para sa layunin ng talakayan na ito. Hindi tayo magtatrabaho sa query model (kahit na ang implementasyon ng mga query gate gamit ang mga elementary na operasyon ay tatalakayin sa ibang pagkakataon sa aralin), at ang pagtingin sa mga arbitrary na unitary gate, na posibleng kumikilos sa milyun-milyong qubit, bilang mga elementary na operasyon ay hindi humahantong sa makahulugan o makatotohanang mga nosyon ng computational cost.

Sa pananatili sa mga quantum gate na nag-ooperate sa maliit na bilang ng mga qubit, isang diskarte para mapagpasyahan kung alin ang itinuturing na elementary ay ang pagbuo ng isang tiyak na pamantayan — ngunit hindi ito ang karaniwang diskarte o ang ating gagawin. Sa halip, gumagawa lang tayo ng pagpipilian.

Narito ang isang karaniwang pagpipilian, na ating gagamitin bilang default na gate set para sa mga quantum circuit:

• Mga single-qubit unitary gate mula sa listahang ito: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ at $T^{\dagger}$
• Mga Controlled-NOT gate
• Mga single-qubit standard basis measurement

Isang karaniwang alternatibo ay ang pagtingin sa Toffoli, Hadamard, at $S$ na mga gate bilang elementary, bilang karagdagan sa mga standard basis measurement. Minsan lahat ng single-qubit gate ay tinitingnan bilang elementary, bagaman nagdudulot ito ng hindi makatotohanang makapangyarihang modelo kapag ang katumpakan ng pagpapatupad ng mga gate ay hindi wastong isinasaalang-alang.

Ang mga unitary gate sa ating default na koleksyon ay bumubuo ng tinatawag na universal na gate set. Ibig sabihin, maaari tayong mag-approximate ng anumang unitary na operasyon sa anumang bilang ng mga qubit sa anumang antas ng katumpakan na gusto natin, gamit ang mga circuit na binubuo ng mga gate na ito lamang. Para maging malinaw, ang kahulugan ng universality ay walang mga kinakailangan sa cost ng mga approximation na ito, ibig sabihin ang bilang ng mga gate mula sa ating set na kailangan natin. Sa katunayan, isang medyo simpleng argumento batay sa mathematical na konsepto ng measure ay nagpapakita na karamihan sa mga unitary na operasyon ay dapat magkaroon ng napakataas na cost. Ang pagpapatunay ng universality ng mga quantum gate set ay hindi simpleng bagay at hindi ito tatalakayin sa kursong ito.

Para sa Boolean na mga circuit, iituturing nating AND, OR, NOT, at FANOUT na mga gate ang kumakatawan sa mga elementary na operasyon. Hindi natin talagang kailangan ang parehong AND at OR gate — maaari nating gamitin ang mga batas ni De Morgan para mag-convert mula sa isa patungo sa isa pa sa pamamagitan ng paglalagay ng mga NOT gate sa lahat ng tatlong input/output wire — ngunit gayunpaman ay karaniwan at maginhawa na payagan ang parehong AND at OR gate. Ang AND, OR, NOT, at FANOUT na mga gate ay bumubuo ng isang universal na set para sa mga deterministic na computation, ibig sabihin na ang anumang function mula sa anumang nakapirming bilang ng mga input bit patungo sa anumang nakapirming bilang ng mga output bit ay maaaring ipatupad gamit ang mga gate na ito.

Ang prinsipyo ng deferred measurement

Ang mga standard basis measurement gate ay maaaring lumabas sa loob ng mga quantum circuit, ngunit minsan ay maginhawa na ipagpaliban ang mga ito hanggang sa katapusan. Nagbibigay-daan ito sa atin na tingnan ang mga quantum computation bilang binubuo ng isang unitary na bahagi (na kumakatawan sa computation mismo), na sinusundan ng isang simpleng read-out phase kung saan sinusukat ang mga qubit at inilalabas ang mga resulta. Maaari itong gawin palagi, basta handa tayong magdagdag ng karagdagang qubit para sa bawat standard basis measurement. Sa sumusunod na figure, ang circuit sa kanan ay naglalarawan kung paano ito magagawa para sa gate sa kaliwa.

Sa partikular, ang classical bit sa circuit sa kaliwa ay pinapalitan ng isang qubit sa kanan (na nagsisimula sa estado na $\vert 0\rangle$), at ang standard basis measurement ay pinapalitan ng isang controlled-NOT gate, na sinusundan ng isang standard basis measurement sa ibabang qubit. Ang punto ay ang standard basis measurement sa right-hand circuit ay maaaring itulak hanggang sa dulo ng circuit. Kung ang classical bit sa circuit sa kaliwa ay gagamitin bilang control bit sa ibang pagkakataon, maaari nating gamitin ang ibabang qubit sa circuit sa kanan bilang control sa halip, at ang kabuuang epekto ay magiging kapareho. (Ipinapalagay natin na ang classical bit sa circuit sa kaliwa ay hindi nao-overwrite pagkatapos ng measurement ng isa pang measurement — ngunit kung ganon ay maaari tayong gumamit ng bagong classical bit sa halip na i-overwrite ang isang ginamit na para sa nakaraang measurement.)

Laki at lalim ng circuit

Laki ng circuit

Ang kabuuang bilang ng mga gate sa isang circuit ay tinutukoy bilang laki ng circuit na iyon. Kaya, kung ipagpalagay na ang mga gate sa ating mga circuit ay kumakatawan sa mga elementary na operasyon, ang laki ng circuit ay kumakatawan sa bilang ng mga elementary na operasyon na kailangan nito — o, sa madaling salita, ang computational cost nito. Isinusulat natin ang $\operatorname{size}(C)$ para tumukoy sa laki ng isang ibinigay na circuit na $C.$

Halimbawa, isaalang-alang ang sumusunod na Boolean circuit para sa pag-compute ng XOR ng dalawang bit.

Ang laki ng circuit na ito ay 7 dahil mayroon 7 gate sa kabuuan. (Ang mga fanout na operasyon ay hindi palaging binibilang bilang mga gate, ngunit para sa layunin ng araling ito, bibibilangin natin ang mga ito bilang mga gate.)

Oras, cost, at lalim ng circuit

Ang Oras ay isang kritikal na mahalagang resource, o isang limitasyong hadlang, para sa mga computation. Ang mga halimbawa sa itaas, tulad ng gawain ng pag-factor ng RSA1024, ay nagpapatibay ng pananaw na ito. Ang function na factorint ay hindi nabibigo sa pag-factor ng RSA1024 sa sarili nito, ito ay basta wala tayong sapat na oras para hayaan itong tapusin.

Ang nosyon ng computational cost, bilang bilang ng mga elementary na operasyon na kailangan para isagawa ang isang computation, ay inilaan upang maging isang abstract na kapalit para sa oras na kailangan para ipatupad ang isang computation. Ang bawat elementary na operasyon ay nangangailangan ng isang tiyak na halaga ng oras para maipatupad, at habang mas marami ang kailangan ng isang computation, mas matagal itong tatagal, kahit sa pangkalahatan. Para sa simplisidad, patuloy nating gagawin ang asosasyong ito sa pagitan ng computational cost at ng oras na kailangan para patakbuhin ang mga algorithm.

Ngunit pansinin na ang laki ng isang circuit ay hindi kinakailangang direktang naaayon sa gaano katagal ito tatakbo. Sa ating Boolean circuit para sa pag-compute ng XOR ng dalawang bit, halimbawa, ang dalawang FANOUT gate ay maaaring isagawa nang sabay-sabay, pati na rin ang dalawang NOT gate, at ang dalawang AND gate. Isang ibang paraan para sukatin ang kahusayan ng mga circuit, na isinasaalang-alang ang posibilidad ng parallelization na ito, ay sa pamamagitan ng kanilang lalim (depth). Ito ang minimum na bilang ng mga layer ng mga gate na kailangan sa loob ng circuit, kung saan ang mga gate sa loob ng bawat layer ay nag-ooperate sa iba't ibang wire. Katumbas nito, ang lalim ng isang circuit ay ang maximum na bilang ng mga gate na natagpuan sa anumang landas mula sa isang input wire patungo sa isang output wire. Para sa circuit sa itaas, halimbawa, ang lalim ay 4.

Ang lalim ng circuit ay isang paraan para pormalisahin ang running time ng mga parallel na computation. Ito ay isang advanced na paksa, at may mga napaka-sopistikadong circuit na konstruksiyon na kilala para mabawasan ang lalim na kinakailangan para sa ilang mga computation. Mayroon ding ilang nakakaaliw na mga hindi nasagot na tanong tungkol sa lalim ng circuit. (Halimbawa, marami pa ring hindi alam tungkol sa lalim ng circuit na kailangan para mag-compute ng GCD.) Hindi tayo magkakaroon ng masyadong marami pang sasabihin tungkol sa lalim ng circuit sa seryeng ito, maliban sa pagsasama ng ilang kawili-wiling katotohanan tungkol sa lalim ng circuit habang tayo ay nagpapatuloy, ngunit dapat na malinaw na kilalanin na ang parallelization ay isang potensyal na pinagkukunan ng mga computational na kalamangan.

Pag-aasign ng mga cost sa iba't ibang gate

Isang huling tala tungkol sa laki ng circuit at computational cost ay posible na mag-assign ng iba't ibang cost sa mga gate, sa halip na tingnan ang bawat gate bilang pantay na nag-aambag sa kabuuang cost.

Halimbawa, tulad ng nabanggit na, ang mga FANOUT gate ay madalas na tinitingnan bilang libre para sa mga Boolean circuit — ibig sabihin ay maaari tayong pumili na ang mga FANOUT gate ay may zero na cost. Bilang isa pang halimbawa, kapag nagtatrabaho tayo sa query model at binibilang natin ang bilang ng mga query na ginagawa ng isang circuit sa isang input function (sa anyo ng isang black box), epektibo nating nini-assign ang unit cost sa mga query gate at zero cost sa ibang mga gate, tulad ng mga Hadamard gate. Ang isang huling halimbawa ay ang pag-assign natin ng iba't ibang cost sa mga gate depende sa kung gaano kahirap ipatupad ang mga ito, na maaaring mag-iba depende sa hardware na isinasaalang-alang.

Kahit na ang lahat ng opsyong ito ay makatuwiran sa iba't ibang konteksto, para sa araling ito ay panatilihin nating simple ang mga bagay at manatili sa laki ng circuit bilang representasyon ng computational cost.

Cost bilang isang function ng haba ng input

Pangunahing interesado tayo sa kung paano nag-aakyat ang computational cost habang nagiging mas malalaki at malalaki ang mga input. Humahantong ito sa atin na katawanin ang mga cost ng mga algorithm bilang mga function ng haba ng input.

Mga pamilya ng circuit

Ang mga input sa isang ibinigay na computational na problema ay maaaring mag-iba sa haba, na posibleng nagiging arbitraryong malaki. Ang bawat circuit, sa kabilang banda, ay may nakapirming bilang ng mga gate at wire. Para sa kadahilanang ito, kapag inisip natin ang mga algorithm sa mga tuntunin ng mga circuit, kadalasan ay kailangan natin ng walang katapusan na malalaking pamilya ng mga circuit para katawanin ang mga algorithm. Sa isang pamilya ng mga circuit, ibig sabihin natin ay isang sequence ng mga circuit na lumalaki ang laki, na nagbibigay-daan sa mas malalaki at malalaking mga input na matugunan.

Halimbawa, isipin na mayroon tayong isang classical algorithm para sa integer factorization, tulad ng ginagamit ng factorint. Tulad ng lahat ng classical algorithm, ang algorithm na ito ay maaaring ipatupad gamit ang mga Boolean circuit — ngunit para gawin ito ay kailangan natin ng hiwalay na circuit para sa bawat posibleng haba ng input. Kung titingnan natin ang mga resultang circuit para sa iba't ibang haba ng input, makikita natin na ang kanilang mga laki ay natural na lumalaki habang lumalaki ang haba ng input — na sumasalamin sa katotohanan na ang pag-factor ng mga 4-bit integer ay mas madali at nangangailangan ng mas kaunting elementary na operasyon kaysa sa pag-factor ng mga 1024-bit integer, halimbawa.

Humahantong ito sa atin na katawanin ang computational cost ng isang algorithm sa pamamagitan ng isang function na $t,$ na tinukoy upang ang $t(n)$ ay ang bilang ng mga gate sa circuit na nagpapatupad ng algorithm para sa mga $n$-bit na input. Sa mas pormal na mga tuntunin, ang isang algorithm sa Boolean circuit model ay inilarawan ng isang sequence ng mga circuit $\{C_1, C_2, C_3,\ldots\},$ kung saan ang $C_n$ ay naglulutas ng anumang problema na pinag-uusapan natin para sa mga $n$-bit na input (o, mas pangkalahatan, para sa mga input na ang laki ay parameterized sa ilang paraan ng $n$), at ang function na $t$ na kumakatawan sa cost ng algorithm na ito ay tinukoy bilang

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

Para sa mga quantum circuit, ang sitwasyon ay katulad, kung saan ang mas malaki at malalaking mga circuit ay kailangan para matugunan ang mas mahahabang mga input string.

Halimbawa: pag-add ng mga integer

Para mas maipaliwanag, maglaan tayo ng sandali para isaalang-alang ang problema ng pag-add ng mga integer, na mas simple kaysa sa integer factoring o kahit sa pag-compute ng GCD.

Pag-add ng mga integer

Input: mga integer na $N$ at $M$
Output: $N+M$

Paano tayo mag-didisenyo ng mga Boolean circuit para malutas ang problemang ito?

Para maging simple, limitahan natin ang ating pansin sa kaso kung saan ang $N$ at $M$ ay parehong mga non-negatibong integer na kinakatawan ng mga $n$-bit na string gamit ang binary notation. Papayagan natin ang anumang bilang ng mga nangunguna (leading) na zero sa mga encoding na ito, kaya

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

Ang output ay magiging isang $(n+1)$-bit binary string na kumakatawan sa kabuuan, na siyang maximum na bilang ng mga bit na kailangan natin para ipahayag ang resulta.

Nagsisimula tayo sa isang algorithm — ang standard na algorithm para sa pag-add ng mga binary na representasyon — na siyang base $2$ na katumbas ng paraan ng pagtuturo ng pag-add sa mga primaryarya/elementaryarya paaralan sa buong mundo. Ang algorithm na ito ay maaaring ipatupad gamit ang mga Boolean circuit tulad ng sumusunod.

Simula sa mga pinaka-mababa (least significant) na bit, maaari nating i-compute ang kanilang XOR para matukoy ang pinaka-mababang bit para sa kabuuan. Pagkatapos ay ini-compute natin ang carry bit, na siyang AND ng dalawang pinaka-mababang bit ng $N$ at $M.$ Minsan ang dalawang operasyong ito nang magkasama ay kilala bilang isang half adder.

Gamit ang XOR circuit na nakita na natin nang ilang beses kasama ng isang AND gate at dalawang FANOUT gate, maaari tayong bumuo ng half adder na may 10 gate. Kung sa ilang dahilan ay nagbago ang ating isip at nagpasya na isama ang mga XOR gate sa ating set ng mga elementary na operasyon, kakailanganin natin ng 1 AND gate, 1 XOR gate, at 2 FANOUT gate para bumuo ng half adder.

Pagsulong sa mas mahahalagang (more significant) na mga bit, maaari tayong gumamit ng katulad na pamamaraan, ngunit sa pagkakataong ito ay isasama ang carry bit mula sa bawat nakaraang posisyon sa ating kalkulasyon. Sa pamamagitan ng pag-cascade ng dalawang half adder at pagkuha ng OR ng mga carry bit na kanilang ginagawa, maaari tayong lumikha ng kilala bilang full adder.

Nangangailangan ito ng 21 gate sa kabuuan: 2 AND gate, 2 XOR gate (bawat isa ay nangangailangan ng 7 gate para ipatupad), isang OR gate, at 4 FANOUT gate.

Sa wakas, sa pamamagitan ng pag-cascade ng mga full adder, nakakakuha tayo ng Boolean circuit para sa pag-add ng mga non-negatibong integer. Halimbawa, ang sumusunod na circuit ay nag-co-compute ng kabuuan ng dalawang 4-bit na integer.

Sa pangkalahatan, nangangailangan ito ng

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

mga gate. Kung nagpasya tayong isama ang mga XOR gate sa ating set ng mga elementary na operasyon, kakailanganin natin ng $2n-1$ AND gate, $2n-1$ XOR gate, $n-1$ OR gate, at $4n-2$ FANOUT gate, para sa kabuuang $9n-5$ gate. Kung bilang karagdagan ay magpasya tayong hindi bilangin ang mga FANOUT gate, ito ay $5n-3$ gate.

Asymptotic notation

Sa isang banda, mabuti na malaman nang tiyak kung gaano karaming gate ang kailangan para isagawa ang iba't ibang mga computation, tulad ng sa halimbawa ng pag-add ng integer sa itaas. Ang mga detalyeng ito ay mahalaga para sa aktwal na pagtatayo ng mga circuit.

Sa kabilang banda, kung magsasagawa tayo ng mga pagsusuri sa ganitong antas ng detalye para sa lahat ng mga computation na ating interesado, kabilang ang mga para sa mga gawain na mas kumplikado kaysa sa pag-add, mabilis tayong mababaon sa mga detalye. Para mapanatiling mapamahalaan ang mga bagay, at layuning pigilin ang mga detalye ng pangalawang kahalagahan, karaniwan tayong gumagamit ng Big-O notation kapag nagsusuri ng mga algorithm. Sa pamamagitan ng notation na ito, maaari nating ipahayag ang order kung saan lumalaki ang mga function.

Sa pormal na pagsasalita, kung mayroon tayong dalawang function na $g(n)$ at $h(n),$ isinusulat natin na $g(n) = O(h(n))$ kung mayroon positibong real number na $c > 0$ at isang positibong integer na $n_0$ na

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

para sa lahat ng $n \geq n_0.$ Karaniwan ang $h(n)$ ay pinipili para maging pinakamasinsinang posibleng ekspresyon, upang magamit ang notation para ipakita ang limitasyong gawi ng isang function sa simpleng mga tuntunin. Halimbawa, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Ang notation na ito ay maaaring palawakin sa mga function na may maraming argumento sa medyo direktang paraan. Halimbawa, kung mayroon tayong dalawang function na $g(n,m)$ at $h(n,m)$ na tinukoy sa mga positibong integer na $n$ at $m,$ isinusulat natin na $g(n,m) = O(h(n,m))$ kung mayroon positibong real number na $c > 0$ at isang positibong integer na $k_0$ na

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

tuwing $n+m \geq k_0.$

Sa pag-ugnay ng notation na ito sa halimbawa ng pag-add ng mga non-negatibong integer, naintindihan natin na mayroong isang pamilya ng mga Boolean circuit na $\{C_1, C_2,\ldots,\},$ kung saan ang $C_n$ ay nag-a-add ng dalawang $n$-bit na mga non-negatibong integer nang magkasama, na $\operatorname{size}(C_n) = O(n).$ Inilalantad nito ang pinaka-mahalagang katangian ng kung paano nagaakyat ang cost ng pag-add kasabay ng laki ng input: nagaakyat ito nang linear.

Pansinin din na hindi ito depende sa tiyak na detalye kung itinuturing natin ang mga XOR gate na may unit cost o cost na $7.$ Sa pangkalahatan, ang paggamit ng Big-O notation ay nagbibigay-daan sa atin na gumawa ng mga pahayag tungkol sa mga computational na cost na hindi sensitibo sa gayong mga mababang antas ng detalye.

Mas maraming halimbawa

Narito ang ilang karagdagang mga halimbawa ng mga problema mula sa computational number theory, simula sa multiplication.

Integer multiplication

Input: mga integer na $N$ at $M$
Output: $NM$

Ang paglikha ng mga Boolean circuit para sa problemang ito ay mas mahirap kaysa sa paglikha ng mga circuit para sa pag-add — ngunit sa pamamagitan ng pag-iisip tungkol sa standard multiplication algorithm, maaari tayong makakagawa ng mga circuit na may laki na $O(n^2)$ para sa problemang ito (kung ipagpalagay na ang $N$ at $M$ ay parehong kinakatawan ng mga $n$-bit binary na representasyon). Mas pangkalahatan, kung ang $N$ ay may $n$ bit at ang $M$ ay may $m$ bit, mayroong mga Boolean circuit na may laki na $O(nm)$ para sa pag-multiply ng $N$ at $M.$

Mayroon, sa katunayan, ibang mga paraan para mag-multiply na mas mabuting nagaakyat. Halimbawa, ang Schönhage-Strassen multiplication algorithm ay maaaring gamitin para lumikha ng mga Boolean circuit para sa pag-multiply ng dalawang $n$-bit na integer sa cost na $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Ang intricacy ng pamamaraang ito ay nagdudulot ng maraming overhead, gayunpaman, na ginagawa itong praktikal lamang para sa mga numero na may sampung libong mga bit.

Isa pang pangunahing problema ay ang division, na ating binibigyang-kahulugan bilang pag-compute ng parehong quotient at remainder na ibinibigay ang isang integer divisor at dividend.

Integer division

Input: mga integer na $N$ at $M\neq0$
Output: mga integer na $q$ at $r$ na nagbibigay ng kasiyahan sa $0\leq r < |M|$ at $N = q M + r$

Ang cost ng integer division ay katulad ng multiplication: kung ang $N$ ay may $n$ bit at ang $M$ ay may $m$ bit, mayroong mga Boolean circuit na may laki na $O(nm)$ para malutas ang problemang ito. At tulad ng multiplication, ang mga asymptotically superior na pamamaraan ay kilala.

Maaari na nating ihambing ang mga kilalang algorithm para sa pag-compute ng GCD sa mga para sa pag-add at multiplication. Ang algorithm ni Euclid para sa pag-compute ng GCD ng isang $n$-bit na numero na $N$ at isang $m$-bit na numero na $M$ ay nangangailangan ng mga Boolean circuit na may laki na $O(nm),$ katulad ng mga standard algorithm para sa multiplication at division. Katulad din ng multiplication at division, may mga asymptotically mas mabilis na GCD algorithm — kabilang ang mga nangangailangan ng $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ na mga elementary na operasyon para mag-compute ng GCD ng dalawang $n$-bit na numero.

Isang medyo mas mahal na computation na lumilitaw sa number theory ay ang modular exponentiation.

Integer modular exponentiation

Input: mga integer na $N,$ $K,$ at $M$ na may $K\geq 0$ at $M\geq 1$
Output: $N^K \hspace{1mm} (\text{mod }M)$

Sa $N^K\hspace{1mm} (\text{mod }M)$ ibig sabihin natin ang natitira kapag ang $N^K$ ay hinati ng $M,$ ibig sabihin ang natatanging integer na $r$ na nagbibigay ng kasiyahan sa $0\leq r < M$ at $N^K = q M + r$ para sa ilang integer na $q.$

Kung ang $N$ ay may $n$ bit, ang $M$ ay may $m$ bit, at ang $K$ ay may $k$ bit, ang problemang ito ay maaaring malutas ng mga Boolean circuit na may laki na $O(k m^2 + nm).$ Hindi ito halata. Ang solusyon ay hindi ang unang mag-compute ng $N^K$ at pagkatapos ay kumuha ng remainder, na mangangailangan ng paggamit ng exponentially na maraming bit para lang maiimbak ang numero na $N^K.$ Sa halip, maaari tayong gumamit ng power algorithm (kilala rin bilang binary method at repeated squaring), na gumagamit ng binary na representasyon ng $K$ para isagawa ang buong computation modulo $M.$ Kung ipagpalagay na ang $N,$ $M,$ at $K$ ay lahat $n$-bit na numero, makakakuha tayo ng isang $O(n^3)$ algorithm — o isang cubic time algorithm. At muli, may mga kilalang algorithm na mas kumplikado ngunit asymptotically mas mabilis.

Cost ng integer factorization

Sa kaibahan sa mga algorithm na tatalakayin, ang mga kilalang algorithm para sa integer factorization ay mas mahal — tulad ng inaasahan natin mula sa talakayan sa nakaraang bahagi ng aralin.

Isang simpleng diskarte sa pag-factor ay ang trial division, kung saan ang isang algorithm ay naghahanap sa listahan na $2,\ldots,\sqrt{N}$ para mahanap ang isang prime factor ng isang input number na $N.$ Nangangailangan ito ng $O(2^{n/2})$ na mga iteration sa pinakamasamang kaso kapag ang $N$ ay isang $n$-bit na numero. Ang bawat iteration ay nangangailangan ng isang trial division, na nangangahulugang $O(n^2)$ na mga elementary na operasyon para sa bawat iteration (gamit ang isang standard algorithm para sa integer division). Nakakakuha tayo ng mga circuit na may laki na $O(n^2 2^{n/2}),$ na exponential sa input size na $n.$

May mga algorithm para sa integer factorization na may mas magandang scaling. Ang number field sieve na nabanggit kanina, halimbawa, na siyang isang algorithm na gumagamit ng randomness, ay pangkalahatang pinaniniwalaan (ngunit hindi mahigpit na napatunayan) na nangangailangan ng

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

mga elementary na operasyon para ma-factor ang mga $n$-bit na integer nang may mataas na posibilidad. Bagaman mahalaga na ang $n$ ay itinaas sa kapangyarihang $1/3$ sa exponent ng expression na ito, ang katotohanan na ito ay lilitaw sa exponent ay isa pa ring problema na nagdudulot ng mahinang scaling — at nagpapaliwanag ng bahagi kung bakit ang RSA1024 ay nananatili sa labas ng saklaw ng pagiging applicable nito.

Polynomial kumpara sa exponential na cost

Ang mga classical algorithm para sa integer addition, multiplication, division, at pag-compute ng pinakadakilang karaniwang divisor ay nagbibigay-daan sa atin na malutas ang mga problemang ito sa isang kisap-mata para sa mga input na may libu-libong bit. Ang pag-add ay may linear cost habang ang tatlong pang problema ay may quadratic cost (o subquadratic cost gamit ang mga asymptotically fast algorithm). Ang modular exponentiation ay mas mahal ngunit maaari pa rin itong gawin nang medyo mahusay, na may cubic cost (o sub-cubic cost gamit ang mga asymptotically fast algorithm).

Ang lahat ng ito ay mga halimbawa ng mga algorithm na may polynomial cost, ibig sabihin ay mayroon silang cost na $O(n^c)$ para sa ilang pagpipilian ng isang nakapirming constant na $c > 0.$ Bilang isang magaspang, unang-order na approximation, ang mga algorithm na may polynomial cost ay abstracto na tinitingnan bilang kumakatawan sa mga mahusay na algorithm.

Sa kaibahan, ang mga kilalang classical algorithm para sa integer factoring ay may exponential na cost. Minsan ang cost ng number field sieve ay inilarawan bilang sub-exponential dahil ang $n$ ay itinaas sa kapangyarihang $1/3$ sa exponent, ngunit sa complexity theory ay mas karaniwan na ilaan ang terminong ito para sa mga algorithm na ang cost ay

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

para sa bawat $\varepsilon > 0.$ Ang tinatawag na mga NP-complete na problema ay isang klase ng mga problema na hindi kilala (at malawakang pinaghihinalaang wala) ng mga polynomial-cost algorithm. Isang circuit-based na formulasyon ng exponential-time hypothesis ay nagpapahiwatig ng isang bagay na mas malakas, na walang NP-complete na problema ang maaaring magkaroon ng sub-exponential cost algorithm.

Ang asosasyon ng mga polynomial-cost algorithm sa mga mahusay na algorithm ay dapat na maintindihan bilang isang maluwag na abstraksiyon. Siyempre, kung ang cost ng isang algorithm ay nagaakyat bilang $n^{1000}$ o $n^{1000000}$ para sa mga input ng laki na $n,$ ito ay medyo malayo na ilarawan ang algorithm na iyon bilang mahusay. Gayunpaman, kahit ang isang algorithm na may cost na nagaakyat bilang $n^{1000000}$ ay dapat na gumagawa ng isang bagay na matalino para maiwasan ang pagkakaroon ng exponential na cost, na sa pangkalahatan ay inaasahan natin ng mga algorithm na batay sa ilang paraan sa "brute force" o "exhaustive search." Kahit ang mga sopistikadong refinement ng number field sieve, halimbawa, ay nabibigo na maiwasan ang exponential scaling na ito sa cost. Ang mga polynomial-cost algorithm, sa kabilang banda, ay nagtagumpay na samantalahin ang istruktura ng problema sa ilang paraan na umiiwas sa exponential scaling.

Sa pagsasagawa, ang pagkilala ng isang polynomial-cost algorithm para sa isang problema ay isang unang hakbang lamang patungo sa aktwal na kahusayan. Sa pamamagitan ng mga algorithmic refinement, ang mga polynomial-cost algorithm na may malalaking exponent ay minsan ay maaaring mapabuti nang dramatiko, na nagpapababa ng cost sa isang mas "makatwirang" polynomial scaling. Minsan ang mga bagay ay nagiging mas madali kapag alam na itong posible — kaya ang pagkilala ng isang polynomial-cost algorithm para sa isang problema ay maaari ding magkaroon ng epekto ng pag-inspire ng mga bago, kahit mas mahusay na mga algorithm.

Habang isinasaalang-alang natin ang mga kalamangan ng quantum computing kumpara sa classical computing, ang ating mga mata ay karaniwang unang nakatuon sa mga exponential na kalamangan, o kahit super-polynomial na kalamangan — perpekto ay ang paghahanap ng mga polynomial-cost quantum algorithm para sa mga problema na hindi kilala na may polynomial-cost classical algorithm. Ang mga theoretical na kalamangan sa order na ito ay may pinakamalaking pagkakataon na humantong sa mga aktwal na praktikal na kalamangan — ngunit ang pagkilala ng gayong mga kalamangan ay isang napakahirap na hamon. Ilang mga halimbawa lamang ang kasalukuyang kilala, ngunit patuloy ang paghahanap.

Ang mga polynomial (ngunit hindi super-polynomial) na kalamangan sa computational cost ng quantum kumpara sa classical ay kawili-wili rin at hindi dapat balewalain — ngunit dahil sa kasalukuyang agwat sa pagitan ng quantum at classical computing technology, tila medyo hindi gaanong kaakit-akit sa kasalukuyan. Isang araw, gayunpaman, maaari silang maging mahalaga. Ang Grover's algorithm, halimbawa, na saklaw sa isang susunod na aralin, ay nag-aalok ng isang quadratic na kalamangan ng quantum kumpara sa classical para sa tinatawag na unstructured searching, at mayroon itong potensyal para sa malawak na mga aplikasyon.

Isang nakatago na cost ng circuit computation

Mayroon pang isang huling isyu na sulit na banggitin, kahit hindi natin ito alalahanin pa sa kursong ito. Mayroong isang "nakatago" na computational cost kapag nagtatrabaho tayo sa mga circuit, at ito ay tungkol sa mga detalye ng mismong mga circuit. Habang nagiging mas mahaba at mahaba ang mga input, mas malaki at malalaking mga circuit ang kailangan — ngunit kailangan nating makuha ang mga paglalarawan ng mga circuit na ito kung ipapatupad natin ang mga ito.

Para sa lahat ng mga halimbawa na ating tinalakay, o tatalakayin sa mga susunod na aralin, mayroong isang pinagbabatayan na algorithm kung saan nagmula ang mga circuit. Karaniwan, ang mga circuit sa isang pamilya ay sumusunod sa ilang pangunahing pattern na madaling i-extrapolate sa mas malalaki at malalaking mga input, tulad ng pag-cascade ng mga full adder para lumikha ng mga Boolean circuit para sa pag-add o pagsasagawa ng mga layer ng Hadamard gate at iba pang mga gate sa ilang madaling ilarawan na pattern.

Ngunit ano ang mangyayari kung may mga prohibitive na computational cost na nauugnay sa mga pattern sa mismong mga circuit? Halimbawa, ang paglalarawan ng bawat miyembro na $C_n$ sa isang circuit family ay maaaring, sa prinsipyo, matukoy ng ilang napakahirap na i-compute na function ng $n.$

Ang sagot ay ito ay talagang isang problema — kaya kailangan nating maglagay ng karagdagang mga paghihigpit sa mga pamilya ng circuit lampas sa pagkakaroon ng polynomial cost upang tunay na kumatawan sa mga mahusay na algorithm. Ang katangian ng uniformity para sa mga circuit ay gumagawa nito sa pamamagitan ng pagtatakda na, sa iba't ibang tiyak na mga formulasyon, dapat na computationally madali na makuha ang paglalarawan ng bawat circuit sa isang pamilya. Lahat ng mga circuit family na ating tatalakayin ay nagtataglay ng katangiang ito — ngunit ito ay isang mahalagang isyu na dapat na malaman sa pangkalahatan kapag pinag-aaralan ang mga circuit model ng computation mula sa isang pormal na pananaw.