Kiejtés

  • IPA: [ ˈʃhorɒlɡoritmuʃ]

Főnév

Shor-algoritmus

  1. (matematika)

Shor-algoritmus

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.



Fő ötlet

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ó.



Probléma megfogalmazása

Adott egy egész szám (N), amelyet (N = p q) alakban szeretnénk felbontani, ahol (p) és (q) prímszámok.

Klasszikus megközelítés:

  • Egy klasszikus algoritmus esetén a faktorizáció (O(e^{c })) időigényű.

Shor-algoritmus futási ideje:

  • Polinomiális idő, (O((N)^2 (N) (N))), amely drámai gyorsulás.



Működés

1. Véletlenszerű alap kiválasztása

Válassz egy véletlenszerű (a) számot ((1 < a < N)).

2. Tesztelés az oszthatóságra

Ha ((a, N) > 1), akkor ez egy osztó, és kész a faktorizáció.

3. Periódus ((r)) keresése

Határozzuk meg az (f(x) = a^x N) függvény ismétlődési periódusát ((r)): [ f(x) = f(x + r), x ] Ez kvantum-számítással gyorsan megoldható.

4. Faktorizáció periódus alapján

Ha (r) páros, és (a^{r/2} N), akkor: [ p = (a^{r/2} - 1, N), q = (a^{r/2} + 1, N) ]

Ha ez nem ad megoldást, kezdjük újra egy másik (a) értékkel.



Algoritmus lépései

  1. Klasszikus előfeldolgozás:
    • Válassz (a)-t véletlenszerűen.
    • Ellenőrizd az oszthatóságot (((a, N))).
  2. Kvantumrész: Perióduskeresés:
    • Hozz létre egy szuperpozíciót: [ _{x=0}^{Q-1} |x|f(x) ]
    • Végezze el a kvantumos Fourier-transzformációt ((QFT)) az első regiszteren: [ QFT: |x _{y=0}^{Q-1} e^{2i xy / Q} |y ]
    • Mérd meg az első regisztert, amelyből a periódus ((r)) visszafejthető.
  3. Klasszikus utófeldolgozás:
    • Ha (r) érvényes (páros, és (a^{r/2} N)), számítsd ki (p)-t és (q)-t.



Pszeudokód

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.

Python implementáció (szimuláció)

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)

Qiskit implementáció

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)

Előnyök

  1. Exponenciális gyorsítás:
    • Klasszikus algoritmusokhoz képest exponenciális gyorsulást biztosít.
  2. Kriptográfiai alkalmazások:
    • Hatékonyan támadja a RSA titkosítást.



Hátrányok

  1. Kvantumszámítógép szükségessége:
    • Nagy teljesítményű kvantumszámítógép nélkül nem használható.
  2. Zajos kvantumhardver:
    • Jelenlegi kvantumszámítógépek nem elég stabilak a nagy számok faktorizálására.



Összegzés

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.