Introduzione

L'idea alla base dei computer quantistici è che la loro capacità di calcolo è esponenzialmente maggiore rispetto ai classici hardware. Un algoritmo quantistico in esecuzione su un computer quantistico beneficia delle cosiddette proprietà quantistiche: superposition, entanglement e interference.

La superposition è il fenomeno quantistico in cui un sistema quantistico può esistere in più stati o posti contemporaneamente.

L'entanglement è una forte correlazione esistente tra due o più particelle quantistiche.

L'interference consente la misurazione di un qubit verso uno stato o un insieme di stati desiderati.

Il fatto che il Quantum Computing sia più veloce del computing tradizionale può essere dimostrato attraverso l'algoritmo di Grover tramite Qiskit, un framework open source per il quantum development che fornisce strumenti per creare e manipolare programmi quantistici su IBM Quantum Experience (la piattaforma online che consente l'accesso pubblico ai servizi di calcolo quantistico di IBM).

Dimostrazione dell'algoritmo di Grover con Qiskit

Il secondo algoritmo quantistico più famoso che dimostra come un computer quantistico supera un computer classico è l'algoritmo di Grover, che si concentra sulla ricerca di un elemento in un elenco non ordinato, quadraticamente più veloce del miglior algoritmo classico. Puoi trovare l'esempio completo qui, ma proviamo a ricapitolare i suoi concetti principali.

Supponiamo di avere un elenco di N elementi non ordinati e di dover cercare la posizione di un elemento. Con un algoritmo classico, dovresti controllare in media N/2 elementi per trovare l'elemento che stai cercando, nel peggiore dei casi -l'elemento è l'ultimo- l'intero elenco. Questa può essere considerata una complessità O(N). Con l'amplitude amplification di Grover sarebbe √N, un aumento di velocità quadratico!

L'implementazione di Grover è una funzione in cui dato un input restituisce il suo negativo se l'input è il vincitore.

La funzione Oracle

nota: |ω⟩ è lo winning state (l'indice che stai cercando nella lista). |𝑥⟩ è la notazione Dirac per un generic input qubit.

Se consideriamo 2 qubit, in modo da poter rappresentare 4 stati di input (00, 01, 10, 11), se assumiamo 11 come winning state, l'oracle Uω restituisce -11.

Amplitude Amplification

Il risultato dell'oracle in sé non basta, bisogna applicare la riflessione per amplificare le probabilità di ottenere lo winning state.

Ecco una rappresentazione geometrica che aiuta a capire come funziona:

fonte: Wikipedia

Dove: |s⟩ è uniform superposition su tutti gli stati

Per un qubit e 2 stati: 1/√2 |0⟩ + 1/√2 |1⟩

|ω⟩ e |s⟩ non sono del tutto perpendicolari perché |ω⟩ si trova nella superposition con ampiezza 1/√N

|s'⟩ = |s⟩ - |ω⟩ è perpendicolare a |ω⟩

UₛUω |s⟩ (diffusore di Grover) = 2 |s⟩⟨s| − I

La somma di oracle più riflessione è chiamata iterazione di Grover. Per ottenere i risultati l'iterazione viene ripetuta O(√N) volte.

Come testarlo nel Quantum Computer di IBM

Per testare il circuito di Grover su IBMQ, registrati qui e ottieni un token.

Ecco il codice per 2 qubit:

La probabilità dello winning state è 0.949