I computer quantistici e il futuro della computabilità

Nel 2007, in Australia è stata trasmessa una pubblicità televisiva. In esso, due modelle in camerino parlavano di meccanica quantistica. Secondo le due modelle, era interessante il fatto che, a differenza dell'approccio abituale in fisica, la meccanica quantistica non si occupa di materia, energia o onde, ma di informazioni, probabilità e quantità osservabili.

L'aspetto notevole di questo filmato pubblicitario non è che due manichini stiano parlando di una teoria fisica, ma piuttosto che il filmato presenti la meccanica quantistica non solo come un'interessante prospettiva di ricerca per la fisica, ma anche per l'informatica. Dodici anni fa, questa posizione scientifica non era così diffusa come oggi, dato che l'informatica quantistica si sta sviluppando rapidamente e sta guadagnando terreno anche all'ETH di Zurigo. affermati al di fuori della fisica.

Da allora, una serie di esperimenti, tra cui quelli condotti dai ricercatori dell'ETH, hanno dimostrato che è possibile, in linea di principio, costruire computer che funzionino secondo le regole della meccanica quantistica; a questo scopo sono disponibili diverse tecnologie e da qualche tempo è in corso una vera e propria gara per vedere chi riesce a costruire il primo computer quantistico (vedi Globe 2/2018).

I cervelloni e i guardiani della complessità

Scott Aaronson, professore di informatica e direttore fondatore del Quantum Information Centre dell'Università del Texas a Austin, è un informatico che presenta ripetutamente argomenti originali su come i computer quantistici potrebbero un giorno risolvere problemi troppo complessi per i computer di oggi. Il dialogo tra i modelli è un'unica citazione testuale, che si può leggere nel suo libro "Quantum Computing since Democritus".

"? tipico di Scott Aaronson pensare al di là del modello classico di computer e chiedersi in modo molto radicale quali tipi di computer possono probabilmente risolvere più problemi dei computer di oggi", afferma l'ETH Renato Renner. La fisica è specializzata nella teoria dell'informazione quantistica. Ha già intrapreso un intenso dibattito con lo stesso Aaronson sul suo blog (cfr. Lato esternoDiscussione sotto "Risposte"). Aaronson, da parte sua, è già stato ospite dell'ETH di Zurigo, ad esempio in occasione della conferenza "Paul Bernays". Colloquio di fisica di Zurigo 2009.

Scott Aaronson ha già ricevuto un "Lato esternoComplessisti" perché si avventura nei problemi più complessi per esplorare le possibilità e i limiti fondamentali dei computer - che si tratti di computer come li conosciamo oggi, di computer quantistici o di tipi di computer completamente diversi che oggi sono quasi inimmaginabili. Nel suo noto e accessibile via internet "Lato esternoLo zoo delle complessità" raggruppa diverse classi di problemi in modo tale da poter vedere quanto i computer siano in grado di calcolare e risolvere questi problemi.

In ogni caso, Scott Aaronson è un ricercatore che ama porsi domande grandi e di principio. A Zurigo, dove interverrà nell'ambito delle Bernays Lectures 2019, discuterà tre questioni chiave dell'informatica teorica e della fisica.

1. Che cosa possono calcolare i computer e in che misura le nuove scoperte della fisica quantistica estendono la potenza di calcolo dei computer?
2. Esistono problemi che i nuovi tipi di computer, come i computer quantistici, sono in grado di calcolare in modo più veloce ed efficiente rispetto ai computer di oggi? Esistono addirittura alcuni problemi particolarmente complessi che solo i computer quantistici o altri computer del futuro possono risolvere?
3. ? possibile produrre computer quantistici utili e qual è lo stato attuale dei vari approcci alla costruzione di un computer quantistico?

Le considerazioni di Aaronson partono dalle basi teoriche e dalla "tesi di Church-Turing". Questa tesi centrale dell'informatica risale ai matematici e pionieri dell'informatica Alonzo Church (1903-1995) e Alan Turing (1912-1954). In termini molto semplificati, afferma che tutti i problemi per i quali si può immaginare e formulare intuitivamente una soluzione possono essere calcolati anche su un computer. Ciò significa che, in linea di principio, tutti i problemi che i modelli informatici di oggi possono calcolare in linea di principio possono effettivamente essere risolti con i computer di oggi.

I computer quantistici possono risolvere più problemi?

Tutto? Non proprio. Ci sono anche problemi che possono essere calcolati e risolti in linea di principio, ma un computer avrebbe bisogno di troppo tempo per calcolarli. Gli informatici definiscono tali problemi, che i computer non possono risolvere in un tempo ragionevole, come non risolvibili in modo efficiente.

In genere, molti fenomeni della fisica quantistica non sono oggi calcolabili in modo efficiente. Per questo motivo, sia la fisica che l'informatica stanno studiando se i computer quantistici possano risolvere i problemi in modo più efficiente rispetto a quelli convenzionali. "Allo stato attuale delle conoscenze, quasi tutti concordano sul fatto che i computer quantistici calcolano più velocemente di quelli convenzionali. Tuttavia, nessuno è ancora riuscito a dimostrarlo. Ecco perché questa ipotesi è una delle grandi domande dell'informatica", dice Renato Renner, che presenta Scott Aaronson alle Paul Bernays Lectures.

Esistono delle controargomentazioni: La tesi di Church-Turing afferma che tutti i problemi risolvibili sono risolvibili su un computer classico. La sua estensione afferma che tutti i problemi risolvibili in modo efficiente sono risolvibili in modo efficiente anche su un computer classico. ? noto che un computer classico può simulare un computer quantistico, ma non in modo efficiente.

Se è possibile simulare in modo efficiente un computer quantistico su un computer classico, allora un computer classico potrebbe risolvere gli stessi problemi di un computer quantistico - e viceversa, nessun computer quantistico potrebbe risolvere problemi fondamentalmente diversi da uno classico. Lo stesso Aaronson sostiene la tesi opposta.

Crittografia e gravità

Un esempio ben noto, per il quale oggi non si conosce un algoritmo per computer classici in grado di calcolarlo in modo efficiente, riguarda la fattorizzazione, ossia la scomposizione di un grande numero composto in singoli divisori. "Nel caso della fattorizzazione, tuttavia, esistono algoritmi in grado di risolvere questo problema in modo efficiente. Tuttavia, questi funzionano solo su un computer quantistico", spiega Renner. Poiché le attuali tecnologie di crittografia e sicurezza su Internet si basano sul problema della fattorizzazione, Aaronson sta facendo ricerche anche sugli aspetti legati alla sicurezza. Lato esternoImplicazioni dei computer quantistici.

Guardando al futuro dei computer, Aaronson e Renner pensano ancora più in là: forse un giorno ci saranno computer che utilizzano fenomeni fisici diversi dalla meccanica quantistica? La teoria gravitazionale, ad esempio. Allora potrebbe essere possibile risolvere problemi che nemmeno i computer quantistici sono in grado di risolvere in modo efficiente?