Il Quantum Computing ora ha un potente strumento di ricerca

L'algoritmo di Grover

Nel 1996, uno scienziato informatico chiamato Lov Grover presso i Bell Labs nel New Jersey ha svelato un insolito algoritmo per la ricerca in un database. Gli algoritmi di ricerca sono tra i più importanti in informatica. Rendono possibili attività banali come la ricerca negli elenchi telefonici, ma anche attività più esotiche come la rottura di codici crittografici. Questo tipo di algoritmo è onnipresente nell'informatica.

Quindi qualsiasi modo per accelerare il compito è estremamente significativo. Una ricerca standard richiede un periodo di tempo approssimativamente proporzionale al numero di elementi nella ricerca. Questo perché, nel peggiore dei casi, l'algoritmo deve cercare tra tutti gli elementi per trovarne solo uno.

Ma l'algoritmo di Grover è diverso. Il tempo impiegato è proporzionale alla radice quadrata del numero di elementi. Gli informatici lo chiamano accelerazione quadratica. E in un mondo in cui aumenti di velocità di poche frazioni di percentuale sono estremamente preziosi, un aumento di velocità quadratico è un risultato imponente.

Il trucco di Grover consisteva nell'utilizzare le idee strane ma potenti alla base della meccanica quantistica. Nel mondo classico, i bit sono solo 0 e 1. Ma nel mondo quantistico, un singolo bit quantistico, o qubit, può essere uno 0 e 1 allo stesso tempo. I fisici dicono che il qubit è in una sovrapposizione di stati.

La sovrapposizione è la chiave. In questo stato, un algoritmo può cercare sia lo 0 che l'1 nello stesso istante. Poiché può cercare più di un elemento contemporaneamente, un algoritmo quantistico può cercare in un elenco molto più rapidamente di un algoritmo limitato dal ritmo faticoso della fisica classica.

Gli algoritmi quantistici devono essere implementati da un computer quantistico e nel 1996, quando Grover fece il suo lavoro, questi erano poco più che un sogno lontano. Ma la svolta è arrivata rapidamente. I fisici hanno dimostrato il primo computer quantistico primitivo nel 1998 e hanno mostrato come potrebbe eseguire l'algoritmo di Grover nello stesso anno.

Ma questa particolare forma di calcolo quantistico era estremamente limitata. Ha funzionato su pochi qubit ma non di più e, anche in linea di principio, non potrebbe mai essere ridimensionato a calcoli più grandi. Questo problema di costruire e dimostrare computer quantistici scalabili ha afflitto la disciplina da allora.

Ora, circa 20 anni dopo, i fisici stanno iniziando a costruire computer quantistici che hanno il potenziale per scalare e quindi sono capaci di calcoli più potenti. E oggi, Caroline Figgatt e i suoi amici dell'Università del Maryland affermano di aver eseguito per la prima volta l'algoritmo di Grover su un computer quantistico scalabile.

Il lavoro dimostra la rapida accelerazione dei calcoli quantistici e apre la strada a un lavoro più ambizioso con l'algoritmo che potrebbe iniziare a risolvere le sfide del mondo reale come la violazione del codice.

Il computer quantistico con cui Figgatt e collabora è costituito da una stringa di cinque ioni itterbio sospesi in un campo elettromagnetico. Ogni ione è come un minuscolo magnete che può essere orientato verso l'alto o verso il basso e spostato da uno stato all'altro con un laser. In questo modo, ogni ione può memorizzare informazioni: un 1 per lo spin up e uno 0 per lo spin down, per esempio. E poiché sono oggetti quantistici, gli ioni possono esistere in una sovrapposizione di questi stati.

Gli ioni interagiscono anche tra loro tramite le forze repulsive associate alla loro carica positiva. Questa interazione consente a un qubit di interagire con un altro qubit per elaborare le informazioni. Questa è l'essenza del calcolo quantistico. L'ordine dei passaggi in questo calcolo è l'algoritmo quantistico, in questo caso l'algoritmo di Grover.

Figgatt e colleghi usano il loro sistema per creare un computer quantistico a tre qubit in grado di memorizzare fino a otto elementi in un database. Quindi eseguono l'algoritmo di Grover per dimostrare che è possibile trovare un oggetto significativamente più velocemente, in media, di un computer classico che richiederebbe almeno otto bit. Riportiamo i risultati per un algoritmo di ricerca Grover completo a tre qubit che utilizza la tecnologia di calcolo quantistico scalabile di ioni atomici intrappolati, con prestazioni migliori del classico, affermano Figgatt e co.

È un lavoro interessante con un potenziale significativo. Questo apre la strada a un uso più ampio dell'algoritmo di ricerca di Grover nella risoluzione di problemi più grandi sui computer quantistici, incluso l'uso del circuito come subroutine per altri algoritmi quantistici, afferma il team.

Ma il lavoro fornisce anche uno sguardo interessante sulla corsa alla costruzione di potenti computer quantistici. È probabile che il vincitore di questa corsa raccolga enormi ricompense finanziarie, ma nessuno è abbastanza sicuro di quale sia la tecnologia migliore.

Questo mondo è stato messo in confusione da una startup canadese chiamata D-Wave Systems che ha venduto computer quantistici apparentemente potenti ad aziende come Google e Lockheed Martin. Questi computer funzionano con 1.000 qubit, molto più di qualsiasi altra tecnologia.

Ma molti teorici affermano che le affermazioni di D-Wave sono esagerate e che le sue macchine non possono produrre neanche lontanamente il tipo di potenza di calcolo di cui dovrebbero essere capaci altri computer quantistici.

Ecco perché molti gruppi stanno cercando di commercializzare altre tecnologie quantistiche che differiscono notevolmente nel modo in cui archiviano ed elaborano le informazioni quantistiche. Questi dipendono variamente da fotoni, elettroni, atomi, ioni e molecole per eseguire le loro offerte quantistiche.

Di queste tecniche, una delle più antiche e sviluppate è l'informatica quantistica con trappola ionica e il gruppo dell'Università del Maryland è leader mondiale in questo settore. Infatti, il leader del gruppo, Chris Monroe, ha una startup chiamata IonQ che mira a commercializzare questa tecnologia.

Quindi la dimostrazione di un computer quantistico scalabile in grado di implementare l'algoritmo di Grover, anche se con soli tre qubit, può essere vista come una dichiarazione di intenti.

Nel 1998, dopo la prima implementazione dell'algoritmo di Grover, c'era una serie di opinioni su quanto tempo avrebbero impiegato i fisici per realizzare i computer scalabili del passaggio successivo. Un certo numero di startup debitamente costituite e crollate sulla base di previsioni ottimistiche. Ma, a quel tempo, 20 anni erano all'estremità pessimistica dello spettro delle previsioni. Il fatto che ci sia voluto così tanto mette in prospettiva la difficoltà del compito.

Controllare l'universo su scala quantistica è difficile. Una domanda interessante ora per tecnologi e capitalisti di rischio è se il tasso di progresso tecnologico può essere accelerato in modo significativo.

Rif: arxiv.org/abs/1703.10535 : Completa la ricerca Grover a 3 Qubit su un computer quantistico programmabile

nascondere