A Shor-algoritmus egy kvantumalgoritmus, amelyet Peter Shor fejlesztett ki 1994-ben. Ez egy hatékony módszer az egész számok faktorizálására, amely egy klasszikus számítógépen szinte lehetetlenül sokáig tartó feladatot polinomiális időben képes megoldani kvantumszámítógépen.
A Shor-algoritmus az egész számok faktorizálását (pl. (N = 15), amely (3 )) egy számelméleti probléma megoldására, az ismétlődési periódus keresésére redukálja. Az algoritmus kvantumszámítógépen a Fourier-transzformáció segítségével gyorsan megtalálja ezt a periódust, amelyből a szám faktorizálható.
Adott egy egész szám (N), amelyet (N = p q) alakban szeretnénk felbontani, ahol (p) és (q) prímszámok.
Válassz egy véletlenszerű (a) számot ((1 < a < N)).
Ha ((a, N) > 1), akkor ez egy osztó, és kész a faktorizáció.
Határozzuk meg az (f(x) = a^x N) függvény ismétlődési periódusát ((r)): Ez kvantum-számítással gyorsan megoldható.
Ha (r) páros, és (a^{r/2} N), akkor:
Ha ez nem ad megoldást, kezdjük újra egy másik (a) értékkel.
Shor(N):
1. Válassz véletlenszerű számot: 1 < a < N
2. Számítsd ki: gcd(a, N)
- Ha gcd(a, N) > 1, térj vissza osztóval.
3. Kvantumos perióduskeresés:
- Keresd meg \(r\)-t, hogy \(a^r \mod N = 1\).
4. Ha \(r\) páros és \(a^{r/2} \not\equiv -1 \mod N\):
- Számítsd ki:
p = gcd(a^{r/2} - 1, N)
q = gcd(a^{r/2} + 1, N)
- Térj vissza \(p\)-vel és \(q\)-val.
5. Ha nem sikerült, ismételd meg másik \(a\)-val.
Az alábbi kód a Shor-algoritmus klasszikus szimulációját mutatja be.
import math
import random
from sympy import gcd
def shor(N):
if N % 2 == 0:
return 2
while True:
a = random.randint(2, N - 1)
g = gcd(a, N)
if g > 1:
return g
# Kvantumos perióduskeresés szimulálva
r = find_period(a, N)
if r is None or r % 2 != 0:
continue
# Faktorizáció
x = pow(a, r // 2, N)
if x == N - 1:
continue
p = gcd(x - 1, N)
q = gcd(x + 1, N)
if p * q == N:
return p, q
def find_period(a, N):
"""Klasszikus perióduskeresés szimulálása."""
r = 1
while pow(a, r, N) != 1:
r += 1
if r > N:
return None
return r
# Példa
N = 15
result = shor(N)
print(f"A(z) {N} faktorizációja: {result}")
Kimenet:
A(z) 15 faktorizációja: (3, 5)
A Qiskit könyvtárat használva a kvantumos perióduskeresést is megvalósíthatjuk.
from qiskit import Aer, QuantumCircuit, execute
def quantum_fourier_transform(circuit, n):
for i in range(n):
for j in range(i):
circuit.cp(math.pi / (2 ** (i - j)), j, i)
circuit.h(i)
def shor_circuit(N, a):
n = math.ceil(math.log(N, 2)) * 2
circuit = QuantumCircuit(n, n)
# Inicializáció
circuit.h(range(n))
circuit.barrier()
# Oracle
for i in range(n):
circuit.cx(i, (i + a) % n)
# Kvantumos Fourier-transzformáció
quantum_fourier_transform(circuit, n)
circuit.barrier()
# Mérési eredmények
circuit.measure(range(n), range(n))
return circuit
# Példa (N = 15, a = 7)
qc = shor_circuit(15, 7)
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print("Mérési eredmények:", counts)
A Shor-algoritmus a kvantumszámítástechnika egyik legfontosabb eredménye, amely forradalmasította a kriptográfia és a számelmélet világát. Bár jelenleg a gyakorlati alkalmazások korlátozottak, a jövőbeni fejlesztések lehetővé tehetik nagy számok hatékony faktorizálását, komoly kihívást jelentve a mai titkosítási rendszerek számára.