Cerca Quàntica amb l’Algorisme de Grover
En aquest tutorial, aprendrem sobre l’algorisme de Grover, que és un algorisme quàntic per cercar en una base de dades no ordenada amb una acceleració quadràtica en comparació amb els algorismes clàssics.
Nota
Si encara no ho heu fet, pot ser útil consultar primer aquests tutorials: Quantum Basics i Quantum Circuits.
El Problema
Suposem que teniu una llista de N elements i voleu trobar un element específic que satisfaci una determinada condició. Per exemple, podríeu tenir una llista de números de telèfon i voler trobar el que pertany a una persona específica.
Aquest és el problema de cercar en una base de dades no ordenada. Clàssicament, això significaria tenir algun array i iterar-lo. La versió quàntica d’aquest problema consisteix a trobar un estat específic en una superposició d’estats que satisfaci una determinada condició.
Per exemple, podríem tenir l’estat:
\(|\psi\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle\)
i volem «trobar» l’estat \(|x\rangle\) tal que \(f(x) = 1\) per a alguna funció \(f\). Per tant, volem realitzar alguna operació per augmentar la probabilitat de mesurar \(|x\rangle\) quan mesurem el nostre estat.
La Solució
Clàssicament, hauríeu de comprovar cada element un per un, la qual cosa tardaria un temps \(O(N)\) en el pitjor cas. L’algorisme de Grover us permet trobar l’element desitjat en un temps \(O(\sqrt{N})\), la qual cosa és una millora significativa per a N gran. Va ser inventat per Lov Grover el 1996 i és un dels algorismes quàntics més coneguts.
L’algorisme consta de dues parts: l”oracle i l”operador de difusió.
L”oracle és una operació quàntica que marca l’estat desitjat invertint la seva fase, en aquest cas corresponent a la funció \(f\) que volem avaluar. Es pot representar com un operador \(O\) tal que:
\(O |x\rangle = (-1)^{f(x)} |x\rangle\)
L”operador de difusió és una operació quàntica que amplifica l’amplitud de l’estat marcat, augmentant la probabilitat de mesurar-lo. Es pot representar com un operador \(D\) tal que:
\(D = 2|\psi\rangle\langle\psi| - I\)
on \(|\psi\rangle\) és l’estat de superposició uniforme i \(I\) és l’operador identitat.
Aplicant \(O\) seguit de \(D\) repetidament, podem amplificar l’amplitud de l’estat marcat i augmentar la probabilitat de mesurar-lo. Més concretament, després de \(\text{floor}(\frac{\pi}{4} \sqrt{N})\) iteracions, la probabilitat de mesurar l’estat marcat serà propera a 1.
La Implementació
Com són en realitat aquests operadors? L’oracle depèn del problema específic que intenteu resoldre, però per a casos com la cerca d’una cadena de bits específica es pot implementar amb portes X i Z controlades. Per exemple, si volem cercar la cadena de bits «01» en un sistema de 2 qubits, podem implementar l’oracle de la manera següent:
from qilisdk.digital import Circuit, CZ, X
oracle = Circuit(2)
oracle.add(X(0))
oracle.add(CZ(0, 1))
oracle.add(X(0))
Això inverteix el bit del primer qubit (de manera que el nostre estat objectiu ara és «11»), aplica una porta Z controlada que inverteix la fase de l’estat «11» i després torna el bit del primer qubit al seu estat original.
L’operador de difusió és una mica més complicat, però es pot implementar aplicant una porta Hadamard i després X a tots els qubits, una porta Z controlada a tots els qubits i desfer les operacions anteriors:
from qilisdk.digital import Circuit, H, X, CZ
diffusion = Circuit(2)
diffusion.add(H(0))
diffusion.add(H(1))
diffusion.add(X(0))
diffusion.add(X(1))
diffusion.add(CZ(0, 1))
diffusion.add(X(1))
diffusion.add(X(0))
diffusion.add(H(1))
diffusion.add(H(0))
El nostre estat inicial serà l’estat de superposició uniforme, que es pot preparar aplicant una porta Hadamard a cada qubit:
from qilisdk.digital import Circuit, H
initial_state = Circuit(2)
initial_state.add(H(0))
initial_state.add(H(1))
Ara podem combinar aquestes operacions per implementar l’algorisme de Grover. Només necessitem una repetició perquè tenim 4 elements en el nostre estat i \(\text{floor}(\frac{\pi}{4} \sqrt{4}) = 1\).
from qilisdk.digital import Circuit
grover = initial_state
grover += oracle
grover += diffusion
Simulant el resultat amb QiliSim:
from qilisdk.backends import QiliSim
from qilisdk.functionals import DigitalPropagation
from qilisdk.readout import Readout
qilisim_backend = QiliSim()
result = qilisim_backend.execute(DigitalPropagation(grover), Readout().with_sampling(nshots=100))
print(result.get_samples())
Això ens dóna:
{'01': 100}
Aquest és el resultat esperat ja que cercàvem l’estat «01».