Calcolatori quantistici

Introduzione

1. Cos’è un calcolatore elettronico (anche detto calcolatore classico)?

   Un calcolatore classico è un dispositivo che elabora informazioni usando bit. È ciò che chiamiamo comunemente computer.

2. Cos’è un calcolatore quantistico?

   Un calcolatore quantistico è dispositivo che elabora informazioni usando qubit.

3. Cos’è un bit?

   Il bit è l’unità minima di informazione di un computer classico. Può trovarsi in soli due stati, solitamente chiamati 0 e 1.

4. Cos’è un qubit?

   Il qubit è l’unità minima di informazione di un computer quantistico. Può trovarsi in sovrapposizione di 0 e 1, cioè in uno stato intermedio tra 0 e 1. (???)

5. Un computer quantistico è più veloce di un computer classico?

   Dipende. Ci sono problemi che un computer quantistico può risolvere più velocemente rispetto a un computer classico.

6. Questo significa che un computer quantistico è sempre più veloce di un computer classico?

   Assolutamente no. Per compiti comuni come scrivere testi, navigare sul Web o fare calcoli semplici, un computer classico è altrettanto veloce o più pratico.

7. Quali sono i problemi che un computer quantistico può risolvere più velocemente?

   Ad esempio, sappiamo che un computer quantistico potrebbe essere più veloce di un computer classico nel problema della fattorizzazione, grazie all’algoritmo di Shor.

8. Altri esempi?
   • Ricerca in database non strutturati (algoritmo di Grover)
   • Simulazioni di molecole e materiali (simulazioni quantistiche)
   • Problemi di ottimizzazione complessa (logistica, intelligenza artificiale avanzata)

9. Un esempio facile, che posso capire?

   L’esempio più facile che ho trovato e l’algoritmo di Deutsch, ma anche io devo ancora capire perfettamente il suo funzionamento

10. Esistono computer quantistici?

    Sì, oggi esistono computer quantistici sperimentali e prototipi commerciali. Alcuni permettono di sperimentare algoritmi su piccola scala tramite cloud (ad esempio IBM, Rigetti, IonQ).

11. Esistono computer quantistici in grado di eseguire l’algoritmo di Shor?

    No.

L’algoritmo di Deutsch-Josza

Il problema è questo: determinare se una funzione è costante (tutti gli output uguali), oppure è bilanciata (metà 0 e metà 1).

Un algoritmo classico, nel caso pessimo, richiede di osservare la metà più uno degli output.

L’algoritmo quantistico sopra citato, invece, richiede una sola osservazione, senza calcolare singolarmente ciascun output. (!!!)

Non ho capito bene come, però un opportuno circuito quantistico permette di osservare lo XOR di tutti i possibili output in una volta sola, senza calcolarli singolarmente. Invece, in un computer classico, per conoscere lo XOR degli output devo necessariamente dapprima calcolare tali output.

Un video utile

L’algoritmo di Shor

1. Cos’è l’algoritmo di Shor?

   È un algoritmo quantistico che fattorizza grandi numeri in numeri primi in modo molto più veloce rispetto agli algoritmi classici conosciuti.

2. Chi è Shor?

   Peter Shor è un matematico e informatico statunitense che, nel 1994, ha inventato l’algoritmo che porta il suo nome.

3. Cos’è il problema di fattorizzazione?

   È il problema di trovare i numeri primi che, moltiplicati tra loro, danno un numero dato.

   Ad esempio, fattorizzare 15 significa trovare 3 e 5, perché 3 × 5 = 15.

4. “Ma prof., fattorizzare 15 è facilissimo. Perché dice che è difficile?”

   Il problema di fattorizzazione è difficile in generale.

   • Sai fattorizzare 15? Sì, a mente, in pochi secondi.
   • Sai fattorizzare 8616460799 (il numero di Jevons)? Tu no, ma un qualsiasi computer, se scrivi un buon algoritmo, ad esempio in C, piò farlo. Prova!
   • Sai fattorizzare RSA-100? Tu no, il tuo computer no, ma computer specializzati, con algoritmi specializzati, ci sono riusciti nel 1991.
   • Sai fattorizzare RSA-2048? Tu no, il tuo computer no, nessuno al mondo ci è mai riuscito. Per un potentissimo computer classico, con un ottimizzatissimo algoritmo classico, servirebbero miliardi di anni. Per un computer quantistico in grado di eseguire l’algoritmo di Shor, basterebbe qualche ora.

5. Qual è la complessità computazionale del più veloce algoritmo classico a noi noto?

   L’algoritmo classico più veloce conosciuto per fattorizzare grandi numeri è il General Number Field Sieve (GNFS).

   La sua complessità è sub-esponenziale: non polinomiale né puramente esponenziale.

6. Qual è la complessità computazionale dell’algoritmo di Shor?

   L’algoritmo di Shor ha complessità polinomiale. Questo è ciò che lo rende teoricamente molto più veloce di un algoritmo classico per grandi numeri.