Măsurarea costului computațional

În continuare, vom discuta un cadru matematic prin care poate fi măsurat costul computațional, concentrat în mod special pe nevoile acestui curs. Analiza algoritmilor și complexitatea computațională sunt subiecte întregi în sine și au mult mai multe de spus despre aceste noțiuni.

Ca punct de plecare, ia în considerare figura următoare din lecția anterioară, care reprezintă o abstractizare de nivel foarte înalt a unei computații.

Computația în sine poate fi modelată sau descrisă în diverse moduri, cum ar fi printr-un program de calculator scris în Python, o mașină Turing, un circuit Boolean sau un circuit cuantic. Ne vom concentra pe circuite (atât Boolean cât și cuantice).

Codificări și lungimea intrării

Să începem cu intrarea și ieșirea unei probleme computaționale, pe care le vom presupune a fi șiruri binare. Am putea folosi și alte simboluri, dar vom menține lucrurile simple în scopul acestei discuții, limitând atenția la intrări și ieșiri de tip șir binar. Prin șiruri binare, putem codifica o varietate de obiecte interesante cu care se ocupă problemele pe care dorim să le rezolvăm, cum ar fi numere, vectori, matrice și grafuri, precum și liste ale acestora și alte obiecte.

De exemplu, pentru a codifica numerele întregi nenegative, putem folosi notația binară. Tabelul următor listează codificarea binară a primelor nouă numere întregi nenegative, împreună cu lungimea (adică numărul total de biți) al fiecărei codificări.

Număr	Codificare binară	Lungime
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

Putem extinde cu ușurință această codificare pentru a gestiona atât numere întregi pozitive cât și negative, adăugând un bit de semn la reprezentări, dacă alegem. Uneori este, de asemenea, convenabil să permitem reprezentărilor binare ale numerelor întregi nenegative să aibă zerouri de început, care nu schimbă valoarea codificată, dar pot permite reprezentărilor să umple un șir sau un cuvânt de dimensiune fixă.

Folosirea notației binare pentru a reprezenta numerele întregi nenegative este atât frecventă cât și eficientă, dar dacă am dori, am putea alege o altă modalitate de a reprezenta numerele întregi nenegative folosind șiruri binare, cum ar fi cele sugerate în tabelul următor. Specificul acestor alternative nu este important pentru această discuție — ideea este doar de a clarifica că avem alegeri în ceea ce privește codificările pe care le folosim.

Număr	Codificare unară	Codificare lexicografică
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

(În acest tabel, simbolul $\varepsilon$ reprezintă șirul vid, care nu conține niciun simbol și are lungimea egală cu zero. Firesc, pentru a evita o sursă evidentă de confuzie, folosim un simbol special precum $\varepsilon$ pentru a reprezenta șirul vid, în loc să scriem literalmente nimic.)

Alte tipuri de intrări, cum ar fi vectorii și matricele, sau obiecte mai complexe precum descrierile moleculelor, pot fi, de asemenea, codificate ca șiruri binare. La fel cum am procedat pentru numerele întregi nenegative, pot fi selectate sau inventate diverse scheme de codificare. Pentru orice schemă la care ajungem pentru a codifica intrările unei probleme date, interpretăm lungimea unui șir de intrare ca reprezentând dimensiunea instanței problemei care este rezolvate.

De exemplu, numărul de biți necesari pentru a exprima un număr întreg nenegativ $N$ în notație binară, uneori notat $\operatorname{lg}(N),$ este dat de formula următoare.

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

Presupunând că folosim notația binară pentru a codifica intrarea în problema factorizării întregi, lungimea intrării pentru numărul $N$ este deci $\operatorname{lg}(N).$ Observă, în special, că lungimea (sau dimensiunea) intrării $N$ nu este $N$ în sine; când $N$ este mare, nu avem nevoie nici pe departe de atâția biți pentru a exprima $N$ în notație binară.

Dintr-un punct de vedere strict formal, ori de câte ori considerăm o problemă sau sarcină computațională, trebuie înțeles că a fost selectată o schemă specifică pentru codificarea oricăror obiecte furnizate ca intrare sau produse ca ieșire. Aceasta permite vizualizarea abstractă a computațiilor care rezolvă probleme interesante ca transformări de la intrări cu șiruri binare la ieșiri cu șiruri binare.

Detaliile despre modul în care obiectele sunt codificate ca șiruri binare trebuie neapărat să fie importante pentru aceste computații la un anumit nivel. De obicei, totuși, nu ne preocupăm prea mult de aceste detalii când analizăm costul computațional, pentru a evita intrarea în detalii de importanță secundară. Raționamentul de bază este că ne așteptăm ca costul computațional al conversiei între scheme de codificare „rezonabile" să fie nesemnificativ în comparație cu costul rezolvării problemei actuale. În situațiile în care acesta nu este cazul, detaliile pot (și ar trebui) să fie clarificate.

De exemplu, o computație foarte simplă face conversia între reprezentarea binară a unui număr întreg nenegativ și codificarea sa lexicografică (pe care nu am explicat-o în detaliu, dar poate fi inferată din tabelul de mai sus). Din acest motiv, costul computațional al factorizării întregi nu ar diferi semnificativ dacă am decide să trecem de la una dintre aceste codificări la cealaltă pentru intrarea $N.$ Pe de altă parte, codificarea numerelor întregi nenegative în notație unară provoacă o explozie exponențială în numărul total de simboluri necesare, și nu am considera-o o schemă de codificare „rezonabilă" din acest motiv.

Operații elementare

Acum să considerăm computația în sine, reprezentată de dreptunghiul albastru din figura de mai sus. Modul în care vom măsura costul computațional este prin numărarea operațiilor elementare pe care le necesită fiecare computație. Intuitiv vorbind, o operație elementară este una implicând un număr mic și fix de biți sau Qubiți, care poate fi efectuată rapid și ușor — cum ar fi calcularea AND-ului a doi biți. În schimb, rularea funcției factorint nu poate fi privită în mod rezonabil ca o operație elementară.

Formal vorbind, există diferite alegeri pentru ceea ce constituie o operație elementară în funcție de modelul computațional utilizat. Ne vom concentra pe modele bazate pe circuite, și anume circuite cuantice și Boolean.

Seturi de Gate-uri universale

Pentru modelele de computație bazate pe circuite, este tipic ca fiecare Gate să fie privit ca o operație elementară. Aceasta ridică întrebarea despre care Gate-uri le permitem exact în circuitele noastre. Concentrându-ne pentru moment pe circuitele cuantice, am văzut mai multe Gate-uri până acum în această serie, inclusiv Gate-urile $X,$ $Y,$ $Z,$ $H,$ $S,$ și $T,$ Gate-uri de swap, versiuni controlate ale Gate-urilor (inclusiv controlled-NOT, Toffoli și Fredkin), precum și Gate-uri care reprezintă măsurători în baza standard. În contextul jocului CHSH am văzut și câteva Gate-uri suplimentare de rotație.

Am discutat, de asemenea, Gate-uri de interogare în contextul modelului de interogare, și am văzut că orice operație unitară $U,$ acționând pe orice număr de Qubiți, poate fi privită ca un Gate dacă dorim — dar vom ignora ambele opțiuni pentru scopul acestei discuții. Nu vom lucra în modelul de interogare (deși implementarea Gate-urilor de interogare folosind operații elementare este discutată mai târziu în lecție), și privirea Gate-urilor unitare arbitrare, potențial acționând pe milioane de Qubiți, ca operații elementare nu duce la noțiuni semnificative sau realiste de cost computațional.

Rămânând la Gate-urile cuantice care operează pe numere mici de Qubiți, o abordare pentru a decide care urmează să fie considerate elementare este de a identifica un criteriu precis — dar aceasta nu este abordarea standard și nici cea pe care o vom adopta. Mai degrabă, pur și simplu facem o alegere.

Iată o alegere standard, pe care o vom adopta ca setul de Gate-uri implicit pentru circuitele cuantice:

• Gate-uri unitare cu un singur Qubit din această listă: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ și $T^{\dagger}$
• Gate-uri Controlled-NOT
• Măsurători cu un singur Qubit în baza standard

O alternativă comună este să privim Gate-urile Toffoli, Hadamard și $S$ ca elementare, pe lângă măsurătorile în baza standard. Uneori toate Gate-urile cu un singur Qubit sunt privite ca elementare, deși aceasta duce la un model nerealist de puternic când acuratețea cu care Gate-urile sunt efectuate nu este luată în considerare în mod corespunzător.

Gate-urile unitare din colecția noastră implicită formează ceea ce se numește un set de Gate-uri universal. Aceasta înseamnă că putem aproxima orice operație unitară pe orice număr de Qubiți la orice grad de precizie dorim, folosind circuite compuse numai din aceste Gate-uri. Pentru a fi clar, definiția universalității nu impune cerințe asupra costului unor astfel de aproximații, adică numărul de Gate-uri din setul nostru de care avem nevoie. Într-adevăr, un argument destul de simplu bazat pe noțiunea matematică de măsură relevă că cele mai multe operații unitare trebuie să aibă un cost extrem de mare. Demonstrarea universalității seturilor de Gate-uri cuantice nu este un lucru simplu și nu va fi acoperit în acest curs.

Pentru circuitele Boolean, vom considera Gate-urile AND, OR, NOT și FANOUT ca reprezentând operațiile elementare. De fapt nu avem nevoie atât de Gate-urile AND cât și de cele OR — putem folosi legile lui De Morgan pentru a converti de la oricare la cealaltă plasând Gate-uri NOT pe toate cele trei fire de intrare/ieșire — dar totuși este atât tipic cât și convenabil să le permitem pe ambele. Gate-urile AND, OR, NOT și FANOUT formează un set universal pentru computații deterministe, ceea ce înseamnă că orice funcție de la orice număr fix de biți de intrare la orice număr fix de biți de ieșire poate fi implementată cu aceste Gate-uri.

Principiul măsurătorii amânate

Gate-urile de măsurătoare în baza standard pot apărea în cadrul circuitelor cuantice, dar uneori este convenabil să le amâni până la final. Aceasta ne permite să privim computațiile cuantice ca constând dintr-o parte unitară (reprezentând computația în sine), urmată de o fază simplă de citire în care Qubiții sunt măsurați și rezultatele sunt produse ca ieșire. Aceasta poate fi întotdeauna realizat, cu condiția să fim dispuși să adăugăm un Qubit suplimentar pentru fiecare măsurătoare în baza standard. În figura următoare, circuitul din dreapta ilustrează cum poate fi realizat acest lucru pentru Gate-ul din stânga.

Mai specific, bitul clasic din circuitul din stânga este înlocuit de un Qubit în dreapta (inițializat în starea $\vert 0\rangle$), iar măsurătoarea în baza standard este înlocuită de un Gate Controlled-NOT, urmată de o măsurătoare în baza standard pe Qubitul din jos. Ideea este că măsurătoarea în baza standard din circuitul din dreapta poate fi împinsă până la sfârșitul circuitului. Dacă bitul clasic din circuitul din stânga este utilizat ulterior ca un bit de control, putem folosi Qubitul din jos din circuitul din dreapta ca un control în schimb, și efectul general va fi același. (Presupunem că bitul clasic din circuitul din stânga nu este suprascris după efectuarea măsurătorii printr-o altă măsurătoare — dar dacă s-ar întâmpla, am putea întotdeauna să folosim un bit clasic nou în loc să suprascriem unul care a fost folosit pentru o măsurătoare anterioară.)

Dimensiunea și adâncimea circuitului

Dimensiunea circuitului

Numărul total de Gate-uri dintr-un circuit este numit dimensiunea acelui circuit. Astfel, presupunând că Gate-urile din circuitele noastre reprezintă operații elementare, dimensiunea unui circuit reprezintă numărul de operații elementare pe care le necesită — sau, cu alte cuvinte, costul său computațional. Scriem $\operatorname{size}(C)$ pentru a se referi la dimensiunea unui circuit dat $C.$

De exemplu, consideră următorul circuit Boolean pentru calcularea XOR-ului a doi biți.

Dimensiunea acestui circuit este 7 deoarece există în total 7 Gate-uri. (Operațiile Fanout nu sunt întotdeauna contorizate ca Gate-uri, dar în scopul acestei lecții le vom conta ca Gate-uri.)

Timp, cost și adâncimea circuitului

Timpul este o resursă de importanță critică, sau o constrângere limitativă, pentru computații. Exemplele de mai sus, cum ar fi sarcina de factorizare a RSA1024, confirmă acest punct de vedere. Funcția factorint nu eșuează să factorizeze RSA1024 în sine, este doar că nu avem suficient timp să o lăsăm să termine.

Noțiunea de cost computațional, ca număr de operații elementare necesare pentru a efectua o computație, este menită să fie un proxy abstract pentru timpul necesar pentru a implementa o computație. Fiecare operație elementară necesită o anumită cantitate de timp pentru a fi efectuată, și cu cât o computație are nevoie de mai multe, cu atât va dura mai mult, cel puțin în general. În interesul simplității, vom continua să facem această asociere între costul computațional și timpul necesar pentru a rula algoritmi.

Dar observă că dimensiunea unui circuit nu corespunde neapărat direct cu cât durează rularea lui. În circuitul nostru Boolean pentru calcularea XOR-ului a doi biți, de exemplu, cele două Gate-uri FANOUT ar putea fi efectuate simultan, la fel și cele două Gate-uri NOT, precum și cele două Gate-uri AND. O modalitate diferită de a măsura eficiența circuitelor, care ia în considerare această posibilitate de paralelizare, este prin adâncimea lor. Aceasta este numărul minim de straturi de Gate-uri necesare în cadrul circuitului, unde Gate-urile din fiecare strat operează pe fire diferite. Echivalent, adâncimea unui circuit este numărul maxim de Gate-uri întâlnite pe orice cale de la un fir de intrare la un fir de ieșire. Pentru circuitul de mai sus, de exemplu, adâncimea este 4.

Adâncimea circuitului este o modalitate de a formaliza timpul de execuție al computațiilor paralele. Este un subiect avansat, și există construcții de circuite foarte sofisticate cunoscute că minimizează adâncimea necesară pentru anumite computații. Există, de asemenea, câteva întrebări fascinante fără răspuns legate de adâncimea circuitului. (De exemplu, mult rămâne necunoscut despre adâncimea circuitului necesară pentru calcularea GCD-urilor.) Nu vom mai spune prea mult despre adâncimea circuitului în această serie, în afară de a include câteva fapte interesante legate de adâncimea circuitului pe parcurs, dar ar trebui să fie clar recunoscut că paralelizarea este o sursă potențială de avantaje computaționale.

Atribuirea costurilor diferitelor Gate-uri

O ultimă notă privind dimensiunea circuitului și costul computațional este că este posibil să atribui costuri diferite Gate-urilor, în loc să privim fiecare Gate ca contribuind în mod egal la costul total.

De exemplu, după cum s-a menționat deja, Gate-urile FANOUT sunt adesea privite ca gratuite pentru circuitele Boolean — ceea ce înseamnă că am putea alege ca Gate-urile FANOUT să aibă cost zero. Ca alt exemplu, când lucrăm în modelul de interogare și numărăm numărul de interogări pe care un circuit le face la o funcție de intrare (sub forma unei cutii negre), atribuim efectiv costul unitar Gate-urilor de interogare și cost zero altor Gate-uri, cum ar fi Gate-urile Hadamard. Un exemplu final este că uneori atribuim costuri diferite Gate-urilor în funcție de cât de dificil sunt de implementat, ceea ce ar putea varia în funcție de hardware-ul considerat.

Deși toate aceste opțiuni sunt sensibile în contexte diferite, pentru această lecție vom menține lucrurile simple și vom rămâne la dimensiunea circuitului ca reprezentare a costului computațional.

Costul ca funcție de lungimea intrării

Suntem interesați în primul rând de modul în care costul computațional se scalează pe măsură ce intrările devin din ce în ce mai mari. Aceasta ne conduce să reprezentăm costurile algoritmilor ca funcții de lungimea intrării.

Familii de circuite

Intrările la o problemă computațională dată pot varia în lungime, potențial devenind arbitrar de mari. Fiecare circuit, pe de altă parte, are un număr fix de Gate-uri și fire. Din acest motiv, când ne gândim la algoritmi în termeni de circuite, avem în general nevoie de familii infinit de mari de circuite pentru a reprezenta algoritmi. Printr-o familie de circuite, înțelegem o secvență de circuite care cresc în dimensiune, permițând intrări din ce în ce mai mari să fie accommodate.

De exemplu, imaginează-ți că avem un algoritm clasic pentru factorizarea întregie, cum ar fi cel folosit de factorint. Ca toți algoritmii clasici, acest algoritm poate fi implementat folosind circuite Boolean — dar pentru a face asta vom avea nevoie de un circuit separat pentru fiecare lungime de intrare posibilă. Dacă am privi circuitele rezultante pentru diferite lungimi de intrare, am vedea că dimensiunile lor cresc în mod natural pe măsură ce lungimea intrării crește — reflectând faptul că factorizarea numerelor întregi de 4 biți este mult mai ușoară și necesită mult mai puține operații elementare decât factorizarea numerelor întregi de 1024 de biți, de exemplu.

Aceasta ne conduce să reprezentăm costul computațional al unui algoritm printr-o funcție $t,$ definită astfel încât $t(n)$ este numărul de Gate-uri din circuitul care implementează algoritmul pentru intrări de $n$ biți. În termeni mai formali, un algoritm în modelul circuitului Boolean este descris de o secvență de circuite $\{C_1, C_2, C_3,\ldots\},$ unde $C_n$ rezolvă orice problemă de care ne ocupăm pentru intrări de $n$ biți (sau, mai general, pentru intrări a căror dimensiune este parametrizată cumva de $n$), și funcția $t$ reprezentând costul acestui algoritm este definită ca

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

Pentru circuitele cuantice situația este similară, unde circuite din ce în ce mai mari sunt necesare pentru a accommodate șiruri de intrare din ce în ce mai lungi.

Exemplu: adunarea numerelor întregi

Pentru a explica mai departe, să luăm un moment să considerăm problema adunării numerelor întregi, care este mult mai simplă decât factorizarea întregie sau chiar calcularea GCD-urilor.

Adunarea numerelor întregi

Intrare: numerele întregi $N$ și $M$
Ieșire: $N+M$

Cum am putea proiecta circuite Boolean pentru rezolvarea acestei probleme?

Pentru a menține lucrurile simple, să ne limităm atenția la cazul în care $N$ și $M$ sunt ambele numere întregi nenegative reprezentate prin șiruri de $n$ biți folosind notația binară. Vom permite orice număr de zerouri de început în aceste codificări, astfel încât

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

Ieșirea va fi un șir binar de $(n+1)$ biți reprezentând suma, care este numărul maxim de biți de care avem nevoie pentru a exprima rezultatul.

Începem cu un algoritm — algoritmul standard pentru adunarea reprezentărilor binare — care este analogul în baza $2$ al modului în care adunarea este predată în școlile primare din întreaga lume. Acest algoritm poate fi implementat cu circuite Boolean astfel.

Pornind de la biții cei mai puțin semnificativi, putem calcula XOR-ul lor pentru a determina cel mai puțin semnificativ bit al sumei. Apoi calculăm bitul de transport, care este AND-ul celor doi biți cei mai puțin semnificativi ai lui $N$ și $M.$ Uneori aceste două operații împreună sunt cunoscute sub numele de semi-sumator.

Folosind circuitul XOR pe care l-am văzut de câteva ori împreună cu un Gate AND și două Gate-uri FANOUT, putem construi un semi-sumator cu 10 Gate-uri. Dacă din anumite motive ne-am schimbat gândul și am decis să includem Gate-urile XOR în setul nostru de operații elementare, am avea nevoie de 1 Gate AND, 1 Gate XOR și 2 Gate-uri FANOUT pentru a construi un semi-sumator.

Trecând la biții mai semnificativi, putem folosi o procedură similară, dar de data aceasta incluzând bitul de transport din fiecare poziție anterioară în calculul nostru. Prin înlănțuirea a două semi-sumatoare și luând OR-ul biților de transport pe care îi produc, putem crea ceea ce este cunoscut ca un sumator complet.

Aceasta necesită în total 21 de Gate-uri: 2 Gate-uri AND, 2 Gate-uri XOR (fiecare necesitând 7 Gate-uri pentru implementare), un Gate OR și 4 Gate-uri FANOUT.

În final, prin înlănțuirea sumatoarelor complete, obținem un circuit Boolean pentru adunarea numerelor întregi nenegative. De exemplu, circuitul următor calculează suma a două numere întregi de 4 biți.

În general, aceasta necesită

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

Gate-uri. Dacă am fi decis să includem Gate-urile XOR în setul nostru de operații elementare, am fi avut nevoie de $2n-1$ Gate-uri AND, $2n-1$ Gate-uri XOR, $n-1$ Gate-uri OR și $4n-2$ Gate-uri FANOUT, pentru un total de $9n-5$ Gate-uri. Dacă în plus decidem să nu contorizăm Gate-urile FANOUT, sunt $5n-3$ Gate-uri.

Notația asimptotică

Pe de o parte, este bine să știm exact câte Gate-uri sunt necesare pentru a efectua diverse computații, ca în exemplul de adunare a numerelor întregi de mai sus. Aceste detalii sunt importante pentru construirea efectivă a circuitelor.

Pe de altă parte, dacă efectuăm analize la acest nivel de detaliu pentru toate computațiile care ne interesează, inclusiv pentru sarcini mult mai complicate decât adunarea, vom fi rapid îngropați în detalii. Pentru a menține lucrurile gestionabile și pentru a suprima intenționat detaliile de importanță secundară, folosim în mod tipic notația Big-O când analizăm algoritmi. Prin această notație putem exprima ordinul la care funcțiile cresc.

Formal vorbind, dacă avem două funcții $g(n)$ și $h(n),$ scriem că $g(n) = O(h(n))$ dacă există un număr real pozitiv $c > 0$ și un număr întreg pozitiv $n_0$ astfel încât

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

pentru toți $n \geq n_0.$ De obicei $h(n)$ este ales să fie o expresie cât mai simplă posibil, astfel încât notația să poată fi folosită pentru a dezvălui comportamentul limitativ al unei funcții în termeni simpli. De exemplu, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Această notație poate fi extinsă la funcții cu mai multe argumente într-un mod destul de simplu. De exemplu, dacă avem două funcții $g(n,m)$ și $h(n,m)$ definite pe numere întregi pozitive $n$ și $m,$ scriem că $g(n,m) = O(h(n,m))$ dacă există un număr real pozitiv $c > 0$ și un număr întreg pozitiv $k_0$ astfel încât

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

ori de câte ori $n+m \geq k_0.$

Conectând această notație la exemplul de adunare a numerelor întregi nenegative, concluzionăm că există o familie de circuite Boolean $\{C_1, C_2,\ldots,\},$ unde $C_n$ adună două numere întregi nenegative de $n$ biți, astfel încât $\operatorname{size}(C_n) = O(n).$ Aceasta dezvăluie cea mai esențială caracteristică a modului în care costul adunării se scalează cu dimensiunea intrării: se scalează liniar.

Observă, de asemenea, că nu depinde de detaliul specific dacă considerăm Gate-urile XOR ca având cost unitar sau cost $7.$ În general, folosirea notației Big-O ne permite să facem afirmații despre costurile computaționale care nu sunt sensibile la astfel de detalii de nivel scăzut.

Mai multe exemple

Iată câteva exemple suplimentare de probleme din teoria computațională a numerelor, începând cu înmulțirea.

Înmulțirea numerelor întregi

Intrare: numerele întregi $N$ și $M$
Ieșire: $NM$

Crearea circuitelor Boolean pentru această problemă este mai dificilă decât crearea circuitelor pentru adunare — dar gândindu-ne la algoritmul standard de înmulțire, putem concepe circuite de dimensiune $O(n^2)$ pentru această problemă (presupunând că $N$ și $M$ sunt ambele reprezentate prin reprezentări binare de $n$ biți). Mai general, dacă $N$ are $n$ biți și $M$ are $m$ biți, există circuite Boolean de dimensiune $O(nm)$ pentru înmulțirea lui $N$ cu $M.$

Există, de fapt, alte moduri de înmulțire care se scalează mai bine. De exemplu, algoritmul de înmulțire Schönhage-Strassen poate fi folosit pentru a crea circuite Boolean pentru înmulțirea a două numere întregi de $n$ biți la cost $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Complexitatea acestei metode cauzează mult overhead, totuși, făcând-o practică doar pentru numere cu zeci de mii de biți.

O altă problemă de bază este împărțirea, pe care o interpretăm ca însemnând calcularea atât a câtului cât și a restului dat un împărțitor și un deîmpărțit întreg.

Împărțirea numerelor întregi

Intrare: numerele întregi $N$ și $M\neq0$
Ieșire: numerele întregi $q$ și $r$ satisfăcând $0\leq r < |M|$ și $N = q M + r$

Costul împărțirii întregi este similar cu înmulțirea: dacă $N$ are $n$ biți și $M$ are $m$ biți, există circuite Boolean de dimensiune $O(nm)$ pentru rezolvarea acestei probleme. Și ca înmulțirea, sunt cunoscute metode asimptotic superioare.

Acum putem compara algoritmii cunoscuți pentru calcularea GCD-urilor cu cei pentru adunare și înmulțire. Algoritmul lui Euclid pentru calcularea GCD-ului unui număr de $n$ biți $N$ și un număr de $m$ biți $M$ necesită circuite Boolean de dimensiune $O(nm),$ similar cu algoritmii standard pentru înmulțire și împărțire. De asemenea, similar cu înmulțirea și împărțirea, există algoritmi GCD asimptotic mai rapizi — inclusiv unii care necesită $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operații elementare pentru a calcula GCD-ul a două numere de $n$ biți.

O computație ceva mai costisitoare care apare în teoria numerelor este exponențierea modulară.

Exponențierea modulară a numerelor întregi

Intrare: numerele întregi $N,$ $K,$ și $M$ cu $K\geq 0$ și $M\geq 1$
Ieșire: $N^K \hspace{1mm} (\text{mod }M)$

Prin $N^K\hspace{1mm} (\text{mod }M)$ înțelegem restul când $N^K$ este împărțit la $M,$ adică unicul număr întreg $r$ satisfăcând $0\leq r < M$ și $N^K = q M + r$ pentru un număr întreg $q.$

Dacă $N$ are $n$ biți, $M$ are $m$ biți și $K$ are $k$ biți, această problemă poate fi rezolvată de circuite Boolean de dimensiune $O(k m^2 + nm).$ Aceasta nu este deloc evident. Soluția nu este de a calcula mai întâi $N^K$ și apoi de a lua restul, ceea ce ar necesita folosirea unui număr exponențial de biți doar pentru a stoca numărul $N^K.$ Mai degrabă, putem folosi algoritmul puterii (cunoscut alternativ ca metoda binară și pătrat repetat), care folosește reprezentarea binară a lui $K$ pentru a efectua întreaga computație modulo $M.$ Presupunând că $N,$ $M,$ și $K$ sunt toate numere de $n$ biți, obținem un algoritm $O(n^3)$ — sau un algoritm de timp cubic. Și din nou, există algoritmi cunoscuți care sunt mai complecși dar asimptotic mai rapizi.

Costul factorizării numerelor întregi

Spre deosebire de algoritmii tocmai discutați, algoritmii cunoscuți pentru factorizarea numerelor întregi sunt mult mai costisitori — așa cum ne-am putea aștepta din discuția anterioară din lecție.

O abordare simplă a factorizării este împărțirea de probă, unde un algoritm caută prin lista $2,\ldots,\sqrt{N}$ pentru a găsi un factor prim al unui număr de intrare $N.$ Aceasta necesită $O(2^{n/2})$ iterații în cel mai rău caz când $N$ este un număr de $n$ biți. Fiecare iterație necesită o împărțire de probă, ceea ce înseamnă $O(n^2)$ operații elementare pentru fiecare iterație (folosind un algoritm standard pentru împărțirea întregie). Ajungem la circuite de dimensiune $O(n^2 2^{n/2}),$ care este exponențial în dimensiunea intrării $n.$

Există algoritmi pentru factorizarea numerelor întregi cu o scalare mai bună. Ciurul câmpului de numere menționat anterior, de exemplu, care este un algoritm ce folosește aleatorietatea, se crede în general (dar nu s-a dovedit riguros) că necesită

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

operații elementare pentru a factoriza numere întregi de $n$ biți cu probabilitate mare. Deși este destul de semnificativ că $n$ este ridicat la puterea $1/3$ în exponentul acestei expresii, faptul că apare în exponent este totuși o problemă care cauzează o scalare slabă — și explică în parte de ce RSA1024 rămâne în afara domeniului său de aplicabilitate.

Cost polinomial versus exponențial

Algoritmii clasici pentru adunarea numerelor întregi, înmulțire, împărțire și calcularea celui mai mare divizor comun ne permit să rezolvăm aceste probleme într-o clipă pentru intrări cu mii de biți. Adunarea are cost liniar în timp ce celelalte trei probleme au cost pătratic (sau cost subpătratic folosind algoritmi asimptotic rapizi). Exponențierea modulară este mai costisitoare dar poate fi totuși efectuată destul de eficient, cu cost cubic (sau cost sub-cubic folosind algoritmi asimptotic rapizi).

Acestea sunt toate exemple de algoritmi cu cost polinomial, ceea ce înseamnă că au cost $O(n^c)$ pentru o alegere a unei constante fixe $c > 0.$ Ca o aproximare brută, de prim ordin, algoritmii cu cost polinomial sunt priviți abstract ca reprezentând algoritmi eficienți.

În contrast, algoritmii clasici cunoscuți pentru factorizarea numerelor întregi au cost exponențial. Uneori costul ciurului câmpului de numere este descris ca sub-exponențial deoarece $n$ este ridicat la puterea $1/3$ în exponent, dar în teoria complexității este mai tipic să rezervi acest termen pentru algoritmi al căror cost este

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

pentru orice $\varepsilon > 0.$ Așa-numitele probleme NP-complete sunt o clasă de probleme despre care nu se știe că (și care sunt în general conjecturate că nu) au algoritmi cu cost polinomial. O formulare bazată pe circuite a ipotezei timpului exponențial postulează ceva și mai puternic, și anume că nicio problemă NP-completă nu poate avea un algoritm cu cost sub-exponențial.

Asocierea algoritmilor cu cost polinomial cu algoritmii eficienți trebuie înțeleasă ca o abstractizare vagă. Desigur, dacă costul unui algoritm se scalează ca $n^{1000}$ sau $n^{1000000}$ pentru intrări de dimensiune $n,$ atunci este o exagerare să descrii acel algoritm ca eficient. Cu toate acestea, chiar și un algoritm cu cost care se scalează ca $n^{1000000}$ trebuie să facă ceva inteligent pentru a evita costul exponențial, care este în general ceea ce ne așteptăm de la algoritmi bazați cumva pe „forță brută" sau „căutare exhaustivă." Chiar și rafinamentele sofisticate ale ciurului câmpului de numere, de exemplu, nu reușesc să evite această scalare exponențială a costului. Algoritmii cu cost polinomial, pe de altă parte, reușesc să profite de structura problemei într-un mod care evită o scalare exponențială.

În practică, identificarea unui algoritm cu cost polinomial pentru o problemă este doar un prim pas spre eficiența efectivă. Prin rafinamente algoritmice, algoritmii cu cost polinomial cu exponenți mari pot fi uneori îmbunătățiți dramatic, reducând costul la o scalare polinomială mai „rezonabilă". Uneori lucrurile devin mai ușoare când se știe că sunt posibile — astfel identificarea unui algoritm cu cost polinomial pentru o problemă poate de asemenea să aibă efectul de a inspira algoritmi noi, și mai eficienți.

Pe măsură ce luăm în considerare avantajele computației cuantice față de cea clasică, ochii noștri sunt îndreptați în general mai întâi spre avantaje exponențiale, sau cel puțin super-polinomiale — găsind în mod ideal algoritmi cuantici cu cost polinomial pentru probleme despre care nu se știe că au algoritmi clasici cu cost polinomial. Avantajele teoretice de acest ordin au cele mai mari șanse de a duce la avantaje practice efective — dar identificarea unor astfel de avantaje este o provocare extrem de dificilă. Sunt cunoscute doar câteva exemple în prezent, dar căutarea continuă.

Avantajele polinomiale (dar nu super-polinomiale) în costul computațional al cuanticului față de clasic sunt, de asemenea, interesante și nu ar trebui ignorate — dar dat fiind decalajul actual dintre tehnologia cuantică și cea clasică de calcul, par mai puțin convingătoare la ora actuală. Într-o zi, totuși, ar putea deveni semnificative. Algoritmul lui Grover, de exemplu, care este acoperit într-o lecție ulterioară, oferă un avantaj pătratic al cuanticului față de clasic pentru așa-numita căutare nestructurată și are potențial pentru aplicații largi.

Un cost ascuns al computației cu circuite

Există o ultimă problemă care merită menționată, deși nu ne vom mai preocupa de ea în acest curs. Există un cost computațional „ascuns" când lucrăm cu circuite, și privește specificațiile circuitelor în sine. Pe măsură ce intrările devin din ce în ce mai lungi, sunt necesare circuite din ce în ce mai mari — dar trebuie să punem mâna pe descrierile acestor circuite cumva, dacă urmează să le implementăm.

Pentru toate exemplele pe care le-am discutat, sau le vom discuta în lecțiile ulterioare, există un algoritm de bază din care sunt derivate circuitele. De obicei circuitele dintr-o familie urmează un model de bază care este ușor de extrapolat la intrări din ce în ce mai mari, cum ar fi înlănțuirea sumatoarelor complete pentru a crea circuite Boolean pentru adunare sau efectuarea de straturi de Gate-uri Hadamard și alte Gate-uri într-un model simplu de descris.

Dar ce se întâmplă dacă există costuri computaționale prohibitive asociate cu modelele din circuitele în sine? De exemplu, descrierea fiecărui membru $C_n$ dintr-o familie de circuite ar putea, în principiu, să fie determinată de o funcție $n$ extrem de dificil de calculat.

Răspunsul este că aceasta este într-adevăr o problemă — și prin urmare trebuie să impunem restricții suplimentare familiilor de circuite dincolo de a avea cost polinomial pentru ca ele să reprezinte cu adevărat algoritmi eficienți. Proprietatea de uniformitate pentru circuite face acest lucru stipulând că, în diverse formulări precise, trebuie să fie ușor din punct de vedere computațional să obții descrierea fiecărui circuit dintr-o familie. Toate familiile de circuite pe care le vom discuta au această proprietate — dar aceasta este totuși o problemă importantă de care trebuie să fii conștient în general când studiezi modele de circuite ale computației dintr-un punct de vedere formal.