Shor algoritması

Teorik derinlik · neden tarihî?

Shor algoritması, tamsayıları asal çarpanlarına ayırmak için 1994’te Peter Shor tarafından önerilmiştir. Klasik dünyada bu problem o kadar zordur ki bankacılık ve veri iletiminde RSA gibi sistemler bu zorluğa güvenir.

Algoritmanın “sihri”, doğrudan çarpan aramak yerine yapıyı periyot diline çevirmesidir; kuantum tarafı da bu periyodu bir girişim/faz deseni olarak ortaya çıkarır.

Çarpanlama → periyot bulma

Shor’un kalbi, çarpanlara ayırma problemini şu fonksiyonun periyodunu bulmaya indirgemektir: $f(x)=a^x \bmod N$.

• Klasik adım

  $N$ (çarpanlarına ayrılacak sayı) ile aralarında asal rastgele bir $a$ seçilir. Kötü seçimlerde algoritma yeniden denenir.

• Kuantum adım

  $f(x)=a^x \pmod N$ fonksiyonunun periyodu $r$ bulunur (kuantum motor + klasik son işleme).

• Sonuç (olasılıksal)

  Bulunan $r$ çift ise ve bazı ek şartlar sağlanırsa, $\gcd(a^{r/2}\pm 1, N)$ çoğu zaman $N$’in doğrudan olmayan çarpanını verir.

Shor devresi, sitede işlediğimiz birçok ileri tekniğin bir araya geldiği bir “zirve” örneğidir. Üç blok özellikle öne çıkar.

• Modüler üs alma

  $x$ süperpozisyonundayken $a^x \bmod N$ sonucunu üreten ünite; devrenin en ağır, Oracle-benzeri parçasıdır ve $N$ ile $a$’ya özel tasarlanır.

• Kuantum faz tahmini (QPE)

  Modüler üs operatörünün içindeki periyot/faz bilgisini precision register’a taşır.

• Ters QFT (IQFT)

  Faz bilgisini klasik bilgisayarın işleyebileceği bir tamsayı tahminine (periyot ipucuna) dönüştürür.

Klasik bilgisayar her $x$ için $f(x)$’i tek tek hesaplarken periyot arar; Shor ise $x$ değerlerini süperpozisyonda “tokatlayarak” periyodu bir girişim deseni olarak görünür kılar.

Dev bir faz ölçümü sezgisi

Kuantum faz tahmini (QPE) sayfasını okuduysanız, Shor’un özünde yine “üniterin fazını okuyup klasik bitlere çevirme” döngüsünün döndüğünü fark edeceksiniz.

Fark, üniterin kendisidir: burada ünite modüler üs almayı temsil eder ve okunan faz/rasyonel yaklaşımı, sürekli kesirler (continued fractions) ile periyot ve çarpanlara bağlanır.

Aşağıdaki kod eğitim amaçlı iskelettir: precision Hadamard’ları, modüler üs yer tutucusu ve IQFT gösterir. Gerçek Shor uygulamasında modüler üs bloğu $N$ ve $a$’ya göre üretilir ve kübit sayısı çok daha büyür.

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
from qiskit_aer import AerSimulator
import numpy as np

def shor_period_finding(n, a):
    # n: Sayıyı temsil eden kübitler,
    # a: Seçilen rastgele sayı (ör. a=7)

    # 2n kübit hassasiyet (toplamda genellikle 3n+ kübit gerekir)
    # Basitleştirilmiş bir gösterim:
    qc = QuantumCircuit(4 + 8, 8)

    # 1. Hazırlık
    qc.h(range(8))  # Precision register
    qc.x(8)         # State register başlangıcı |1>
    qc.barrier()

    # 2. Modüler Üs Alma (U^2^j)
    # Bu kısım her a ve N değerine özel kapı tasarımları gerektirir
    # Örnek: qc.append(modular_exp_gate, ...)

    # 3. Ters QFT
    qc.append(QFT(8).inverse(), range(8))

    # 4. Ölçüm
    qc.measure(range(8), range(8))
    return qc

# N=15, a=7 için simülasyonun mantığı
# r=4 bulunması beklenir. gcd(7^(4/2) ± 1, 15) -> 3 ve 5 çarpanlarını verir.

İskeletin rolü

QuantumCircuit boyutu · neden 4+8?

Örnekte 8 kübit precision, 4 kübit ise state tarafı için yer tutucudur — gerçek bir $N$ için hem precision hem modüler aritmetik genişler; “$2n$ precision” ve “toplamda $\mathcal{O}(n)$ kübit” tartışması teorik düzeydedir.

qc.h(range(8))

Üst register’a Hadamard, QPE’nin başlangıç süperpozisyonunu kurar: faz bilgisini hangi kombinasyonların taşıyacağı burada belirlenir.

qc.x(8)

Modüler çarpan için uygun üniterin özvektör hazırlığı genelde $|1\rangle$ ile başlar; tam devrede register yerleşimi ve endianness Qiskit ölçüm eşlemesiyle birlikte düşünülür.

Modüler üs bloğu (yorum)

Gerçek kodda burada kontrollü $a^{2^j}\bmod N$ uygulamaları gelir; bu, devrenin kalori ve derinliğinin kaynağıdır. Ortak kitaplık kapısı yerine çoğu zaman özel sentez gerekir.

QFT(8).inverse()

IQFT, precision’daki fazı bit desenine çevirir — Shor’da “periyot ipucu”nun klasik tarafa sızdığı adım.

Ölçüm ve klasik devam

Ölçülen bitlerden rasyonel yaklaşım + sürekli kesirler ile $r$ tahmini yapılır; ardından $\gcd$ adımı klasik çalışır. Bu yüzden Shor da Simon gibi hibrittir.

Şema, Shor’un “periyot bulma” çekirdeğini blok düzeyinde özetler: precision hazırlığı, modüler üs (Oracle-benzeri), IQFT ve ölçüm. Gerçek modüler üs içi kapılar özetlenmez.

Şemayı adım adım oku

1. 1

   Precision kübitleri süperpozisyona alınır; QPE’nin “ölçüm alanı” hazırlanır.

2. 2

   Modüler üs bloğu, üniteyi kontrollü kuvvetlerle uygular; periyot bilgisi fazda kodlanır (Oracle-benzeri en ağır kısım).

3. 3

   IQFT, fazı klasik olarak işlenebilir bit kalıbına çevirir.

4. 4

   Klasik sürekli kesirler ve $\gcd$ ile çarpan adayları çıkarılır; başarısızlıkta $a$ yeniden seçilir.

Grand finale · dökümantasyon tonu

Shor sayfasını “son bölüm” gibi düşünebiliriz: önceki QFT, QPE ve Simon hatları burada birleşir.

• Kübit ihtiyacı

  $L$ bitlik bir sayı için kusursuz bir makinede kabaca $\mathcal{O}(L)$ kübit ve çok daha derin devreler konuşulur; RSA-2048 gibi pratik hedefler için hatasız kübit sayısı milyonlar mertebesinde tartışılır — bugünün NISQ donanımı bu rejimden uzaktır.

• Girişim filtresi

  IQFT, periyodik olmayan bileşenleri zayıflatarak gerçek periyoda karşılık gelen frekansın genliğinin öne çıkmasına yardım eder (idealized resim).

• Hibrit doğa

  Kuantum periyot/faz bilgisini çıkarır; klasik işlemci sürekli kesirler ve $\gcd$ ile asıl çarpanlara bağlar.

QPE ile bağlantıyı pekiştirmek için Kuantum faz tahmini (QPE) · Qiskit.