Un nuovo algoritmo quantistico per i numeri primi

José Latorre dell'Università di Barcellona e Germán Sierra dell'Università Autonoma di Madrid hanno messo a punto il primo algoritmo quantistico per contare i numeri primi. Sfruttando i computer quantistici i passaggi dell'algoritmo dovrebbero essere molto più rapidi, poiché hanno prestazioni molto più potenti di quelli ordinari in quanto i loro bit occupano più stati contemporaneamente e non solo lo stato "1" o "0". Ma finora i più grandi computer quantistici costruiti hanno solo una manciata di questi speciali "qubit", dunque il teorico guadagno di velocità non è ancora stato in pratica realizzato.

Per utilizzare in maniera efficace l'algoritmo di Latorre-Sierra sarebbe necessario un computer di 80 qubit, assai più grande di quelli ad oggi esistenti ma molto più piccolo di quello richiesto dal precedente algoritmo quantistico di Shor (1994). Secondo il fisico-informatico Seth Lloyd del Massachusetts Institute of Technology: "L'idea è semplice, elegante e sorprendentemente potente. Sarebbe una buona cosa da fare con un piccolo computer quantistico, se solo ce ne fosse uno".