A Grover-algoritmus egy kvantumalgoritmus, amelyet Lov Grover fejlesztett ki 1996-ban. Az algoritmus hatékony módszert biztosít egy nem rendezett adatbázisban történő kereséshez, kihasználva a kvantumszámítógépek szuperpozíció és interferencia képességeit.
Egy klasszikus számítógép (O(N)) időben tud megkeresni egy adott elemet egy (N)-elemű nem rendezett adatbázisban. A Grover-algoritmus ezt a keresést kvantumszámítógépen (O()) időre gyorsítja. Ez kvantumos sebességnövekedést jelent, különösen nagy méretű adatbázisok esetén.
A Grover-algoritmus kvantumlogikai kapuk sorozatával valósítja meg a keresést:
Kezdetben minden kvantumbitet a (|0) állapotból (|+)-be állítunk Hadamard kapukkal:
A keresett állapot ((x_0)) fázisát invertáljuk. Az új állapot:
A diffúziós lépés az összes állapot amplitúdóját egyensúlyozza, hogy az érdekes állapot amplitúdója növekedjen: ahol (|) az egyenletes szuperpozíció állapota.
A szükséges iterációk száma:
Grover(N, O_f):
1. Inicializálás:
Állítsd a qubiteket egyenletes szuperpozícióba Hadamard kapukkal.
2. Ismételd kb. √N-szer:
a. Oracle lépés: Fordítsd meg a keresett állapot fázisát.
b. Diffúziós lépés: Növeld a keresett állapot amplitúdóját.
3. Mérd meg az állapotot, és ad vissza az eredményt.
A következő példa a Grover-algoritmust valósítja meg egy egyszerű 4 elemű adatbázison.
from qiskit import Aer, QuantumCircuit, execute
from qiskit.visualization import plot_histogram
# Oracle függvény implementálása
def oracle(circuit, n):
circuit.z(n - 1) # Példa: negáljuk a legutolsó állapot fázisát
# Diffúziós lépés implementálása
def diffusion(circuit, n):
for qubit in range(n):
circuit.h(qubit)
circuit.x(qubit)
circuit.h(n - 1)
circuit.mcx(list(range(n - 1)), n - 1) # Többszörös CNOT
circuit.h(n - 1)
for qubit in range(n):
circuit.x(qubit)
circuit.h(qubit)
# Grover algoritmus
def grover(n):
circuit = QuantumCircuit(n)
# Inicializálás
circuit.h(range(n))
# Oracle és diffúziós lépés
oracle(circuit, n)
diffusion(circuit, n)
# Mérési eredmények
circuit.measure_all()
return circuit
# Példa futtatása
n_qubits = 3 # 2^3 = 8 elem az adatbázisban
qc = grover(n_qubits)
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
# Eredmények megjelenítése
print("Mérési eredmények:", counts)
plot_histogram(counts)
A szimuláció során a legnagyobb valószínűséggel a keresett elem (fázisinvertált állapot) jelenik meg a kimenetben.
A Grover-algoritmus egy fontos kvantumalgoritmus, amely nagy potenciállal bír nem rendezett keresési problémák gyors megoldásában. Bár csak kvadratikus gyorsulást kínál, bizonyos problémák esetén (pl. adatbázis-keresés) ez már jelentős előnyt jelenthet, különösen nagy méretű adathalmazokkal dolgozva.