Il lavoro del team è pubblicato sulla rivista Science Advances .

I computer quantistici utilizzano i cosiddetti qubit, che non sono né zero né uno come nei circuiti logici convenzionali, ma possono assumere qualsiasi valore intermedio. Questi qubit sono realizzati da atomi, ioni o circuiti superconduttori altamente raffreddati, ed è ancora fisicamente molto complesso costruire un computer quantistico con molti qubit. Tuttavia, i metodi matematici possono già essere utilizzati per esplorare ciò che i computer quantistici tolleranti agli errori potrebbero ottenere in futuro.

"Ci sono molti miti a riguardo, e talvolta una certa quantità di aria fritta e di esagerazione. Ma noi abbiamo affrontato la questione in modo rigoroso, utilizzando metodi matematici, e abbiamo fornito risultati concreti sull'argomento. Soprattutto, abbiamo chiarito in che senso ci possono essere dei vantaggi", afferma il Prof. Dr. Eisert, che dirige un gruppo di ricerca congiunto presso la Freie Universität Berlin e l'Helmholtz-Zentrum Berlin.

Un esempio lampante è il noto problema del commesso viaggiatore:un viaggiatore deve visitare diverse città e poi tornare nella sua città natale. Qual è il percorso più breve? Sebbene questo problema sia facile da comprendere, diventa sempre più complesso man mano che il numero delle città aumenta e il tempo di calcolo aumenta. Il problema del commesso viaggiatore rappresenta un gruppo di problemi di ottimizzazione di enorme importanza economica, sia che coinvolgano le reti ferroviarie, la logistica o l'ottimizzazione delle risorse. Soluzioni sufficientemente buone possono essere trovate utilizzando metodi di approssimazione.

Il team guidato da Eisert e dal suo collega Jean-Pierre Seifert ha ora utilizzato metodi puramente analitici per valutare come un computer quantistico con qubit potrebbe risolvere questa classe di problemi, un classico esperimento mentale con carta e penna e molta esperienza.

"Partiamo semplicemente dal presupposto, indipendentemente dalla realizzazione fisica, che ci siano abbastanza qubit e esaminiamo le possibilità di eseguire operazioni di calcolo con essi", spiega Vincent Ulitzsch, Ph.D. studente presso l'Università Tecnica di Berlino.

In tal modo, il team ha svelato somiglianze con un noto problema della crittografia, ovvero la crittografia dei dati.

"Ci siamo resi conto che potevamo utilizzare l'algoritmo Shor per risolvere una sottoclasse di questi problemi di ottimizzazione", afferma Ulitzsch. Ciò significa che il tempo di calcolo non "esplode" più con il numero di città (esponenziale, 2 ^N ), ma aumenta solo polinomialmente, cioè con N ^x , dove x è una costante. La soluzione così ottenuta è anche qualitativamente molto migliore della soluzione approssimata utilizzando l'algoritmo convenzionale.

"Abbiamo dimostrato che per una classe specifica ma molto importante e praticamente rilevante di problemi di ottimizzazione combinatoria, i computer quantistici presentano un vantaggio fondamentale rispetto ai computer classici per alcuni casi del problema", afferma Eisert.