Misurare il costo computazionale

Di seguito discuteremo un framework matematico attraverso il quale è possibile misurare il costo computazionale, focalizzandoci strettamente sulle esigenze di questo corso. L'analisi degli algoritmi e la complessità computazionale sono discipline a sé stanti, e hanno molto più da dire su questi concetti.

Come punto di partenza, considera la seguente figura dalla lezione precedente, che rappresenta un'astrazione ad alto livello di un calcolo.

Il calcolo stesso può essere modellato o descritto in vari modi, ad esempio tramite un programma Python, una macchina di Turing, un circuito Booleano o un circuito quantistico. La nostra attenzione si concentrerà sui circuiti (sia Booleani che quantistici).

Codifiche e lunghezza dell'input

Iniziamo dall'input e dall'output di un problema computazionale, che assumeremo siano stringhe binarie. Si potrebbero usare simboli diversi, ma per semplicità in questa discussione ci limiteremo a input e output sotto forma di stringhe binarie. Tramite le stringhe binarie possiamo codificare una varietà di oggetti interessanti su cui i problemi che vogliamo risolvere potrebbero vertere, come numeri, vettori, matrici e grafi, oltre a liste di questi e altri oggetti.

Ad esempio, per codificare gli interi non negativi possiamo usare la notazione binaria. La tabella seguente elenca la codifica binaria dei primi nove interi non negativi, insieme alla lunghezza (ovvero il numero totale di bit) di ciascuna codifica.

Numero	Codifica binaria	Lunghezza
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

Possiamo facilmente estendere questa codifica per gestire sia interi positivi che negativi aggiungendo un bit di segno alle rappresentazioni, se lo desideriamo. A volte è anche comodo consentire che le rappresentazioni binarie degli interi non negativi abbiano zeri iniziali, che non modificano il valore codificato ma possono permettere alle rappresentazioni di riempire una stringa o una parola di dimensione fissa.

Usare la notazione binaria per rappresentare gli interi non negativi è comune ed efficiente, ma volendo potremmo scegliere un modo diverso per rappresentarli tramite stringhe binarie, come quelli suggeriti nella tabella seguente. I dettagli specifici di queste alternative non sono importanti per questa discussione — il punto è solo chiarire che abbiamo delle scelte riguardo alle codifiche da utilizzare.

Numero	Codifica unaria	Codifica lessicografica
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

(In questa tabella, il simbolo $\varepsilon$ rappresenta la stringa vuota, che non contiene simboli e ha lunghezza pari a zero. Naturalmente, per evitare una ovvia fonte di confusione, usiamo un simbolo speciale come $\varepsilon$ per rappresentare la stringa vuota invece di scrivere letteralmente nulla.)

Altri tipi di input, come vettori e matrici, o oggetti più complessi come descrizioni di molecole, possono anch'essi essere codificati come stringhe binarie. Proprio come abbiamo fatto per gli interi non negativi, si possono scegliere o inventare vari schemi di codifica diversi. Qualunque schema adottiamo per codificare gli input di un dato problema, interpretiamo la lunghezza di una stringa di input come rappresentativa della dimensione dell'istanza del problema che stiamo risolvendo.

Ad esempio, il numero di bit necessari per esprimere un intero non negativo $N$ in notazione binaria, a volte indicato con $\operatorname{lg}(N),$ è dato dalla formula seguente.

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

Supponendo di usare la notazione binaria per codificare l'input del problema della fattorizzazione intera, la lunghezza dell'input per il numero $N$ è quindi $\operatorname{lg}(N).$ Nota in particolare che la lunghezza (o dimensione) dell'input $N$ non è $N$ stesso; quando $N$ è grande non ci servono quasi altrettanti bit per esprimere $N$ in notazione binaria.

Da un punto di vista strettamente formale, ogni volta che consideriamo un problema o un compito computazionale, si deve intendere che sia stato selezionato uno schema specifico per codificare gli oggetti forniti come input o prodotti come output. Questo permette di vedere le computazioni che risolvono problemi interessanti in modo astratto, come trasformazioni da stringhe binarie di input a stringhe binarie di output.

I dettagli su come gli oggetti vengono codificati come stringhe binarie devono necessariamente essere importanti per queste computazioni a un certo livello. Di solito, però, non ci preoccupiamo troppo di questi dettagli quando analizziamo il costo computazionale, in modo da evitare di entrare in dettagli di importanza secondaria. Il ragionamento di fondo è che ci aspettiamo che il costo computazionale della conversione tra schemi di codifica "ragionevoli" sia trascurabile rispetto al costo di risoluzione del problema effettivo. Nelle situazioni in cui ciò non è il caso, i dettagli possono (e devono) essere chiariti.

Ad esempio, una computazione molto semplice converte tra la rappresentazione binaria di un intero non negativo e la sua codifica lessicografica (che non abbiamo spiegato in dettaglio, ma può essere dedotta dalla tabella sopra). Per questa ragione, il costo computazionale della fattorizzazione intera non diferirebbe significativamente se decidessimo di passare dall'uso di una di queste codifiche all'altra per l'input $N.$ D'altra parte, codificare gli interi non negativi in notazione unaria comporta un'esplosione esponenziale nel numero totale di simboli richiesti, e per questo motivo non la consideriamo uno schema di codifica "ragionevole".

Operazioni elementari

Consideriamo ora la computazione stessa, rappresentata dal rettangolo blu nella figura sopra. Il modo in cui misureremo il costo computazionale consiste nel contare il numero di operazioni elementari richieste da ciascuna computazione. Intuitivamente, un'operazione elementare è un'operazione che coinvolge un numero piccolo e fisso di bit o qubit, che può essere eseguita in modo rapido e semplice — come calcolare l'AND di due bit. Al contrario, eseguire la funzione factorint non può ragionevolmente essere considerata un'operazione elementare.

Formalmente, esistono diverse scelte riguardo a cosa costituisce un'operazione elementare, a seconda del modello computazionale utilizzato. La nostra attenzione si concentrerà sui modelli a circuito, e specificamente sui circuiti quantistici e Booleani.

Insiemi di gate universali

Per i modelli di calcolo basati su circuiti, è tipico che ogni gate venga considerato un'operazione elementare. Ciò porta alla domanda su quali gate esattamente ammettiamo nei nostri circuiti. Concentrandoci per il momento sui circuiti quantistici, abbiamo visto diversi gate finora in questa serie, tra cui i gate $X,$ $Y,$ $Z,$ $H,$ $S,$ e $T,$ i gate swap, le versioni controllate dei gate (inclusi i gate controlled-NOT, Toffoli e Fredkin), nonché i gate che rappresentano misurazioni nella base standard. Nel contesto del gioco CHSH abbiamo visto anche alcuni gate di rotazione aggiuntivi.

Abbiamo anche discusso i gate di query nel contesto del modello di query, e abbiamo visto che qualsiasi operazione unitaria $U,$ che agisce su qualsiasi numero di qubit, può essere vista come un gate se lo si desidera — ma tralasceremo entrambe queste opzioni ai fini di questa discussione. Non lavoreremo nel modello di query (sebbene l'implementazione dei gate di query tramite operazioni elementari venga discussa più avanti nella lezione), e considerare gate unitari arbitrari, potenzialmente agenti su milioni di qubit, come operazioni elementari non porta a nozioni significative o realistiche di costo computazionale.

Restando con gate quantistici che operano su un piccolo numero di qubit, un approccio per decidere quali considerare elementari consiste nell'individuare un criterio preciso — ma questo non è l'approccio standard né quello che adotteremo. Piuttosto, facciamo semplicemente una scelta.

Ecco una scelta standard, che adotteremo come insieme di gate predefinito per i circuiti quantistici:

• gate unitari a singolo qubit da questo elenco: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ e $T^{\dagger}$
• gate Controlled-NOT
• Misurazioni a singolo qubit nella base standard

Un'alternativa comune è considerare elementari i gate Toffoli, Hadamard e $S,$ oltre alle misurazioni nella base standard. A volte tutti i gate a singolo qubit vengono considerati elementari, anche se questo porta a un modello irrealisticamente potente quando la precisione con cui i gate vengono eseguiti non viene adeguatamente considerata.

I gate unitari nella nostra raccolta predefinita formano quello che viene chiamato un insieme di gate universale. Ciò significa che possiamo approssimare qualsiasi operazione unitaria su qualsiasi numero di qubit con qualsiasi grado di accuratezza desideriamo, usando circuiti composti esclusivamente da questi gate. Per essere chiari, la definizione di universalità non pone alcun requisito sul costo di tali approssimazioni, ovvero sul numero di gate del nostro insieme che occorre. In effetti, un argomento abbastanza semplice basato sulla nozione matematica di misura rivela che la maggior parte delle operazioni unitarie deve avere un costo estremamente elevato. Dimostrare l'universalità degli insiemi di gate quantistici non è un compito semplice e non verrà trattato in questo corso.

Per i circuiti Booleani, considereremo elementari le operazioni AND, OR, NOT e FANOUT. In realtà non abbiamo bisogno sia dei gate AND che di quelli OR — possiamo usare le leggi di De Morgan per convertire dall'uno all'altro inserendo gate NOT su tutti e tre i fili di input/output — ma è comunque tipico e conveniente consentire entrambi i tipi di gate. I gate AND, OR, NOT e FANOUT formano un insieme universale per le computazioni deterministiche, nel senso che qualsiasi funzione da un numero fisso di bit di input a un numero fisso di bit di output può essere implementata con questi gate.

Il principio della misurazione differita

I gate di misurazione nella base standard possono comparire all'interno dei circuiti quantistici, ma a volte è conveniente ritardarli fino alla fine. Questo ci permette di vedere le computazioni quantistiche come composte da una parte unitaria (che rappresenta il calcolo vero e proprio), seguita da una semplice fase di lettura in cui i qubit vengono misurati e i risultati vengono prodotti in output. Questo è sempre possibile, a condizione di essere disposti ad aggiungere un qubit aggiuntivo per ogni misurazione nella base standard. Nella figura seguente, il circuito a destra illustra come ciò possa essere fatto per il gate a sinistra.

Nello specifico, il bit classico nel circuito di sinistra viene sostituito da un qubit a destra (inizializzato allo stato $\vert 0\rangle$), e la misurazione nella base standard viene sostituita da un gate Controlled-NOT, seguito da una misurazione nella base standard sul qubit in basso. Il punto è che la misurazione nella base standard nel circuito di destra può essere spostata fino alla fine del circuito. Se il bit classico nel circuito di sinistra viene successivamente usato come bit di controllo, possiamo usare il qubit in basso nel circuito di destra come controllo, e l'effetto complessivo sarà lo stesso. (Stiamo assumendo che il bit classico nel circuito di sinistra non venga sovrascritto dopo che la misurazione ha avuto luogo da un'altra misurazione — ma se ciò accadesse potremmo sempre usare un nuovo bit classico invece di sovrascriverne uno già usato per una misurazione precedente.)

Dimensione e profondità del circuito

Dimensione del circuito

Il numero totale di gate in un circuito viene chiamato dimensione del circuito. Pertanto, supponendo che i gate nei nostri circuiti rappresentino operazioni elementari, la dimensione di un circuito rappresenta il numero di operazioni elementari che richiede — o, in altre parole, il suo costo computazionale. Scriviamo $\operatorname{size}(C)$ per indicare la dimensione di un dato circuito $C.$

Ad esempio, considera il seguente circuito Booleano per calcolare lo XOR di due bit.

La dimensione di questo circuito è 7 perché ci sono 7 gate in totale. (Le operazioni Fanout non vengono sempre conteggiate come gate, ma ai fini di questa lezione le conteremo come gate.)

Tempo, costo e profondità del circuito

Il tempo è una risorsa fondamentale, o un vincolo limitante, per le computazioni. Gli esempi sopra citati, come il compito di fattorizzare RSA1024, rafforzano questo punto di vista. La funzione factorint non fallisce nel fattorizzare RSA1024 in senso stretto, è solo che non abbiamo abbastanza tempo per lasciarla terminare.

La nozione di costo computazionale, intesa come il numero di operazioni elementari necessarie per eseguire una computazione, è intesa come un proxy astratto per il tempo necessario per implementare una computazione. Ogni operazione elementare richiede una certa quantità di tempo per essere eseguita, e più operazioni richiede una computazione, più a lungo impiegherà, almeno in generale. Nell'interesse della semplicità, continueremo a fare questa associazione tra costo computazionale e il tempo necessario per eseguire gli algoritmi.

Nota però che la dimensione di un circuito non corrisponde necessariamente direttamente al tempo necessario per eseguirlo. Nel nostro circuito Booleano per calcolare lo XOR di due bit, ad esempio, i due gate FANOUT potrebbero essere eseguiti simultaneamente, così come i due gate NOT e i due gate AND. Un modo diverso di misurare l'efficienza dei circuiti, che tiene conto di questa possibilità di parallelizzazione, è attraverso la loro profondità. Questa è il numero minimo di livelli di gate necessari all'interno del circuito, dove i gate all'interno di ciascun livello operano su fili diversi. Equivalentemente, la profondità di un circuito è il numero massimo di gate incontrati su qualsiasi percorso da un filo di input a un filo di output. Per il circuito sopra, ad esempio, la profondità è 4.

La profondità del circuito è un modo per formalizzare il tempo di esecuzione dei calcoli paralleli. È un argomento avanzato, ed esistono costruzioni di circuiti molto sofisticate note per minimizzare la profondità richiesta per certi calcoli. Ci sono anche alcune affascinanti domande senza risposta riguardanti la profondità dei circuiti. (Ad esempio, molto rimane sconosciuto sulla profondità del circuito necessaria per calcolare il MCD.) Non avremo molto altro da dire sulla profondità del circuito in questa serie, a parte includere alcuni fatti interessanti man mano che procediamo, ma è necessario riconoscere chiaramente che la parallelizzazione è una potenziale fonte di vantaggi computazionali.

Assegnare costi a gate diversi

Un'ultima nota riguardante la dimensione del circuito e il costo computazionale è che è possibile assegnare costi diversi ai gate, invece di considerare ogni gate come contribuente ugualmente al costo totale.

Ad esempio, come già menzionato, i gate FANOUT vengono spesso considerati gratuiti per i circuiti Booleani — il che significa che potremmo scegliere che i gate FANOUT abbiano costo zero. Come altro esempio, quando lavoriamo nel modello di query e contiamo il numero di query che un circuito effettua a una funzione di input (sotto forma di una scatola nera), stiamo effettivamente assegnando costo unitario ai gate di query e costo zero ad altri gate, come i gate Hadamard. Un ultimo esempio è che a volte assegniamo costi diversi ai gate a seconda di quanto siano difficili da implementare, il che può variare a seconda dell'hardware considerato.

Sebbene tutte queste opzioni siano ragionevoli in contesti diversi, per questa lezione manterremo le cose semplici e ci atterremo alla dimensione del circuito come rappresentazione del costo computazionale.

Costo in funzione della lunghezza dell'input

Ci interessa principalmente capire come il costo computazionale scala al crescere degli input. Questo ci porta a rappresentare i costi degli algoritmi come funzioni della lunghezza dell'input.

Famiglie di circuiti

Gli input di un dato problema computazionale possono variare in lunghezza, potenzialmente crescendo in modo illimitato. Ogni circuito, d'altra parte, ha un numero fisso di gate e fili. Per questa ragione, quando pensiamo agli algoritmi in termini di circuiti, abbiamo generalmente bisogno di famiglie di circuiti di dimensione infinita per rappresentare gli algoritmi. Per famiglia di circuiti intendiamo una sequenza di circuiti che crescono di dimensione, consentendo di gestire input sempre più grandi.

Per esempio, immagina di avere un algoritmo classico per la fattorizzazione intera, come quello usato da factorint. Come tutti gli algoritmi classici, questo algoritmo può essere implementato con circuiti booleani — ma per farlo avremo bisogno di un circuito separato per ogni possibile lunghezza di input. Se osservassi i circuiti risultanti per diverse lunghezze di input, vedresti che le loro dimensioni crescono naturalmente al crescere della lunghezza dell'input — rispecchiando il fatto che fattorizzare interi a 4 bit è molto più semplice e richiede molte meno operazioni elementari rispetto a fattorizzare interi a 1024 bit, per esempio.

Questo ci porta a rappresentare il costo computazionale di un algoritmo tramite una funzione $t,$ definita in modo che $t(n)$ sia il numero di gate nel circuito che implementa l'algoritmo per input di $n$ bit. In termini più formali, un algoritmo nel modello a circuiti booleani è descritto da una sequenza di circuiti $\{C_1, C_2, C_3,\ldots\},$ dove $C_n$ risolve il problema in questione per input a $n$ bit (o, più in generale, per input la cui dimensione è parametrizzata in qualche modo da $n$), e la funzione $t$ che rappresenta il costo di questo algoritmo è definita come

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

Per i circuiti quantistici la situazione è analoga, dove sono necessari circuiti sempre più grandi per gestire stringhe di input sempre più lunghe.

Esempio: addizione intera

Per spiegare meglio, prendiamoci un momento per considerare il problema dell'addizione intera, che è molto più semplice della fattorizzazione intera o persino del calcolo del MCD.

Addizione intera

Input: interi $N$ e $M$
Output: $N+M$

Come potremmo progettare circuiti booleani per risolvere questo problema?

Per semplicità, limitiamoci al caso in cui $N$ e $M$ sono entrambi interi non negativi rappresentati da stringhe a $n$ bit usando la notazione binaria. Ammettiamo un qualsiasi numero di zeri iniziali in queste codifiche, cosicché

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

L'output sarà una stringa binaria a $(n+1)$ bit che rappresenta la somma, che è il numero massimo di bit necessari per esprimere il risultato.

Partiamo da un algoritmo — l'algoritmo standard per l'addizione in rappresentazione binaria — che è l'analogo in base $2$ del modo in cui l'addizione viene insegnata nelle scuole elementari di tutto il mondo. Questo algoritmo può essere implementato con circuiti booleani come segue.

Partendo dai bit meno significativi, possiamo calcolarne lo XOR per determinare il bit meno significativo della somma. Poi calcoliamo il bit di riporto, che è l'AND dei due bit meno significativi di $N$ e $M.$ A volte queste due operazioni insieme sono note come half adder (semisommatore).

Usando il circuito XOR che abbiamo già visto alcune volte insieme a un gate AND e due gate FANOUT, possiamo costruire un half adder con 10 gate. Se per qualche motivo cambiassimo idea e decidessimo di includere i gate XOR nel nostro insieme di operazioni elementari, avremmo bisogno di 1 gate AND, 1 gate XOR e 2 gate FANOUT per costruire un half adder.

Passando ai bit più significativi, possiamo usare una procedura simile, ma questa volta includendo nel calcolo il bit di riporto proveniente dalla posizione precedente. Cascando due half adder e calcolando l'OR dei bit di riporto che producono, possiamo creare quello che è noto come full adder (sommatore completo).

Questo richiede 21 gate in totale: 2 gate AND, 2 gate XOR (ciascuno che richiede 7 gate per essere implementato), un gate OR e 4 gate FANOUT.

Infine, cascando i full adder, otteniamo un circuito booleano per l'addizione di interi non negativi. Per esempio, il seguente circuito calcola la somma di due interi a 4 bit.

In generale, questo richiede

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

gate. Se avessimo deciso di includere i gate XOR nel nostro insieme di operazioni elementari, avremmo bisogno di $2n-1$ gate AND, $2n-1$ gate XOR, $n-1$ gate OR e $4n-2$ gate FANOUT, per un totale di $9n-5$ gate. Se in aggiunta decidessimo di non contare i gate FANOUT, sarebbero $5n-3$ gate.

Notazione asintotica

Da un lato, è utile sapere esattamente quanti gate sono necessari per eseguire vari calcoli, come nell'esempio dell'addizione intera sopra. Questi dettagli sono importanti per costruire effettivamente i circuiti.

D'altro canto, se eseguissimo analisi a questo livello di dettaglio per tutti i calcoli che ci interessano, inclusi quelli per operazioni molto più complesse dell'addizione, saremmo ben presto sommersi dai dettagli. Per mantenere le cose gestibili, e per sopprimere intenzionalmente i dettagli di importanza secondaria, usiamo tipicamente la notazione Big-O quando analizziamo gli algoritmi. Tramite questa notazione possiamo esprimere l'ordine con cui le funzioni crescono.

Formalmente, se abbiamo due funzioni $g(n)$ e $h(n),$ scriviamo $g(n) = O(h(n))$ se esiste un numero reale positivo $c > 0$ e un intero positivo $n_0$ tali che

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

per ogni $n \geq n_0.$ Tipicamente $h(n)$ è scelta come l'espressione più semplice possibile, in modo che la notazione possa essere usata per rivelare il comportamento limite di una funzione in termini semplici. Per esempio, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Questa notazione può essere estesa a funzioni con più argomenti in modo abbastanza diretto. Per esempio, se abbiamo due funzioni $g(n,m)$ e $h(n,m)$ definite su interi positivi $n$ e $m,$ scriviamo $g(n,m) = O(h(n,m))$ se esiste un numero reale positivo $c > 0$ e un intero positivo $k_0$ tali che

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

ogniqualvolta $n+m \geq k_0.$

Collegando questa notazione all'esempio dell'addizione di interi non negativi, concludiamo che esiste una famiglia di circuiti booleani $\{C_1, C_2,\ldots,\},$ dove $C_n$ somma due interi non negativi a $n$ bit, tale che $\operatorname{size}(C_n) = O(n).$ Questo rivela la caratteristica più essenziale di come il costo dell'addizione scala con la dimensione dell'input: scala linearmente.

Nota anche che non dipende dal dettaglio specifico di se consideriamo i gate XOR con costo unitario o costo $7.$ In generale, l'uso della notazione Big-O ci permette di fare affermazioni sui costi computazionali che non sono sensibili a tali dettagli di basso livello.

Altri esempi

Ecco altri esempi di problemi dalla teoria computazionale dei numeri, a partire dalla moltiplicazione.

Moltiplicazione intera

Input: interi $N$ e $M$
Output: $NM$

Creare circuiti booleani per questo problema è più difficile che creare circuiti per l'addizione — ma ragionando sull'algoritmo di moltiplicazione standard, possiamo elaborare circuiti di dimensione $O(n^2)$ per questo problema (assumendo che $N$ e $M$ siano entrambi rappresentati da rappresentazioni binarie a $n$ bit). Più in generale, se $N$ ha $n$ bit e $M$ ha $m$ bit, esistono circuiti booleani di dimensione $O(nm)$ per moltiplicare $N$ e $M.$

Esistono, in realtà, altri modi per moltiplicare che scalano meglio. Per esempio, l'algoritmo di moltiplicazione di Schönhage-Strassen può essere usato per creare circuiti booleani per moltiplicare due interi a $n$ bit con costo $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ L'intricatezza di questo metodo causa molto overhead, tuttavia, rendendolo pratico solo per numeri con decine di migliaia di bit.

Un altro problema fondamentale è la divisione, che interpretiamo come il calcolo sia del quoziente che del resto dato un divisore e un dividendo interi.

Divisione intera

Input: interi $N$ e $M\neq0$
Output: interi $q$ e $r$ che soddisfano $0\leq r < |M|$ e $N = q M + r$

Il costo della divisione intera è simile alla moltiplicazione: se $N$ ha $n$ bit e $M$ ha $m$ bit, esistono circuiti booleani di dimensione $O(nm)$ per risolvere questo problema. E come per la moltiplicazione, sono noti metodi asintoticamente superiori.

Possiamo ora confrontare gli algoritmi noti per il calcolo del MCD con quelli per l'addizione e la moltiplicazione. L'algoritmo di Euclide per il calcolo del MCD di un numero $N$ a $n$ bit e di un numero $M$ a $m$ bit richiede circuiti booleani di dimensione $O(nm),$ simile agli algoritmi standard per la moltiplicazione e la divisione. Analogamente alla moltiplicazione e alla divisione, esistono algoritmi per il MCD asintoticamente più veloci — inclusi quelli che richiedono $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operazioni elementari per calcolare il MCD di due numeri a $n$ bit.

Un calcolo alquanto più costoso che emerge nella teoria dei numeri è l'esponenziazione modulare.

Esponenziazione modulare intera

Input: interi $N,$ $K,$ e $M$ con $K\geq 0$ e $M\geq 1$
Output: $N^K \hspace{1mm} (\text{mod }M)$

Con $N^K\hspace{1mm} (\text{mod }M)$ intendiamo il resto quando $N^K$ è diviso per $M,$ ovvero l'unico intero $r$ che soddisfa $0\leq r < M$ e $N^K = q M + r$ per qualche intero $q.$

Se $N$ ha $n$ bit, $M$ ha $m$ bit e $K$ ha $k$ bit, questo problema può essere risolto da circuiti booleani di dimensione $O(k m^2 + nm).$ Questo non è affatto ovvio. La soluzione non consiste nel calcolare prima $N^K$ e poi prendere il resto, il che richiederebbe un numero esponenziale di bit solo per memorizzare il numero $N^K.$ Piuttosto, possiamo usare l'algoritmo di esponenziazione veloce (noto anche come metodo binario e quadratura ripetuta), che sfrutta la rappresentazione binaria di $K$ per eseguire l'intero calcolo modulo $M.$ Assumendo che $N,$ $M,$ e $K$ siano tutti numeri a $n$ bit, otteniamo un algoritmo $O(n^3)$ — ovvero un algoritmo a tempo cubico. E ancora una volta, sono noti algoritmi più complessi ma asintoticamente più veloci.

Costo della fattorizzazione intera

A differenza degli algoritmi appena discussi, gli algoritmi noti per la fattorizzazione intera sono molto più costosi — come ci aspetteremmo dalla discussione precedente nella lezione.

Un approccio semplice alla fattorizzazione è la divisione per tentativi, dove un algoritmo percorre la lista $2,\ldots,\sqrt{N}$ alla ricerca di un fattore primo di un numero di input $N.$ Questo richiede $O(2^{n/2})$ iterazioni nel caso peggiore quando $N$ è un numero a $n$ bit. Ogni iterazione richiede una divisione di prova, il che significa $O(n^2)$ operazioni elementari per ogni iterazione (usando un algoritmo standard per la divisione intera). Si ottengono circuiti di dimensione $O(n^2 2^{n/2}),$ che è esponenziale nella dimensione dell'input $n.$

Esistono algoritmi per la fattorizzazione intera con una scalabilità migliore. Il crivello del campo numerico menzionato in precedenza, per esempio, che è un algoritmo che fa uso della casualità, si ritiene generalmente (ma non è stato dimostrato rigorosamente) richiedere

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

operazioni elementari per fattorizzare interi a $n$ bit con alta probabilità. Sebbene sia piuttosto significativo che $n$ sia elevato alla potenza $1/3$ nell'esponente di questa espressione, il fatto che appaia nell'esponente rimane comunque un problema che causa una scarsa scalabilità — e spiega in parte perché RSA1024 rimane al di là del suo campo di applicabilità.

Costo polinomiale versus costo esponenziale

Gli algoritmi classici per l'addizione intera, la moltiplicazione, la divisione e il calcolo del massimo comune divisore ci permettono di risolvere questi problemi in un batter d'occhio per input con migliaia di bit. L'addizione ha costo lineare mentre gli altri tre problemi hanno costo quadratico (o costo subquadratico usando algoritmi asintoticamente veloci). L'esponenziazione modulare è più costosa ma può comunque essere eseguita in modo abbastanza efficiente, con costo cubico (o costo sub-cubico usando algoritmi asintoticamente veloci).

Questi sono tutti esempi di algoritmi con costo polinomiale, ovvero con costo $O(n^c)$ per qualche scelta di una costante fissa $c > 0.$ Come approssimazione di primo ordine, gli algoritmi con costo polinomiale sono astrattamente considerati come algoritmi efficienti.

Al contrario, gli algoritmi classici noti per la fattorizzazione intera hanno costo esponenziale. A volte il costo del crivello del campo numerico è descritto come sub-esponenziale perché $n$ è elevato alla potenza $1/3$ nell'esponente, ma nella teoria della complessità è più tipico riservare questo termine agli algoritmi il cui costo è

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

per ogni $\varepsilon > 0.$ I cosiddetti problemi NP-completi sono una classe di problemi di cui non si conosce (e si congettura ampiamente che non abbiano) un algoritmo a costo polinomiale. Una formulazione a circuiti dell'ipotesi del tempo esponenziale postula qualcosa di ancora più forte, ovvero che nessun problema NP-completo possa avere un algoritmo a costo sub-esponenziale.

L'associazione degli algoritmi a costo polinomiale con gli algoritmi efficienti deve essere intesa come un'astrazione approssimativa. Naturalmente, se il costo di un algoritmo scala come $n^{1000}$ o $n^{1000000}$ per input di dimensione $n,$ è forzato descrivere quell'algoritmo come efficiente. Tuttavia, anche un algoritmo con costo che scala come $n^{1000000}$ deve fare qualcosa di ingegnoso per evitare il costo esponenziale, che è generalmente ciò che ci aspettiamo dagli algoritmi basati in qualche modo sulla "forza bruta" o sulla "ricerca esaustiva." Persino i raffinamenti sofisticati del crivello del campo numerico, per esempio, non riescono a evitare questa scalabilità esponenziale nel costo. Gli algoritmi a costo polinomiale, d'altra parte, riescono a sfruttare la struttura del problema in qualche modo che evita una scalabilità esponenziale.

In pratica, l'identificazione di un algoritmo a costo polinomiale per un problema è solo un primo passo verso l'efficienza reale. Tramite raffinamenti algoritmici, gli algoritmi a costo polinomiale con grandi esponenti possono a volte essere migliorati drasticamente, riducendo il costo a una scalabilità polinomiale più "ragionevole". A volte le cose diventano più facili quando si sa che sono possibili — quindi l'identificazione di un algoritmo a costo polinomiale per un problema può anche avere l'effetto di ispirare nuovi algoritmi, ancora più efficienti.

Mentre consideriamo i vantaggi del calcolo quantistico rispetto a quello classico, i nostri occhi si rivolgono generalmente prima ai vantaggi esponenziali, o almeno super-polinomiali — trovando idealmente algoritmi quantistici a costo polinomiale per problemi di cui non si conoscono algoritmi classici a costo polinomiale. I vantaggi teorici di questo ordine hanno le maggiori possibilità di portare a vantaggi pratici reali — ma identificare tali vantaggi è una sfida estremamente difficile. Al momento sono noti solo pochi esempi, ma la ricerca continua.

I vantaggi polinomiali (ma non super-polinomiali) nel costo computazionale del quantistico rispetto al classico sono anch'essi interessanti e non dovrebbero essere scartati — ma dato l'attuale divario tra la tecnologia informatica quantistica e quella classica, sembrano piuttosto meno convincenti al momento attuale. Un giorno, però, potrebbero diventare significativi. L'algoritmo di Grover, per esempio, che viene trattato in una lezione successiva, offre un vantaggio quadratico del quantistico sul classico per la cosiddetta ricerca non strutturata, e ha un potenziale per applicazioni ampie.

Un costo nascosto del calcolo a circuiti

C'è un ultimo aspetto che vale la pena menzionare, anche se non ce ne occuperemo ulteriormente in questo corso. C'è un costo computazionale "nascosto" quando si lavora con i circuiti, e riguarda le specifiche dei circuiti stessi. Man mano che gli input diventano sempre più lunghi, sono necessari circuiti sempre più grandi — ma dobbiamo procurarci le descrizioni di questi circuiti in qualche modo se vogliamo implementarli.

Per tutti gli esempi di cui abbiamo discusso, o di cui discuteremo nelle lezioni successive, c'è un algoritmo di base da cui i circuiti sono derivati. Di solito i circuiti in una famiglia seguono uno schema di base facile da estrapolare a input sempre più grandi, come il cascading di full adder per creare circuiti booleani per l'addizione o l'esecuzione di strati di gate Hadamard e altri gate in uno schema semplice da descrivere.

Ma cosa succede se ci sono costi computazionali proibitivi associati agli schemi nei circuiti stessi? Per esempio, la descrizione di ogni membro $C_n$ in una famiglia di circuiti potrebbe, in linea di principio, essere determinata da una funzione di $n$ estremamente difficile da calcolare.

La risposta è che questo è effettivamente un problema — e quindi dobbiamo imporre restrizioni aggiuntive alle famiglie di circuiti oltre ad avere costo polinomiale affinché rappresentino davvero algoritmi efficienti. La proprietà di uniformità per i circuiti fa proprio questo, stabilendo che, in varie formulazioni precise, deve essere computazionalmente semplice ottenere la descrizione di ogni circuito in una famiglia. Tutte le famiglie di circuiti di cui discuteremo hanno questa proprietà — ma questo rimane comunque un aspetto importante da tenere presente in generale quando si studiano i modelli a circuiti di calcolo da un punto di vista formale.