Shor algoritması

Teorik derinlik · neden tarihî?

Shor algoritması, bileşik bir tamsayıyı asal çarpanlarına ayırma (integer factorization) problemini polinom zamanda kuantum çözülebilir gösteren yapılardan biridir; 1994’te Peter Shor’un önerisiyle bilinir. Klasik tarafta bu problem, bilinen genel yöntemler için giriş boyutu arttıkça fiilen üstel süreye yaklaşan bir maliyet profiline sahiptir; bu asimetri “çarpmanın kolay, çarpanlarına ayırmanın zor olduğu” düşüncesine dayanan RSA gibi pek çok kriptosistemde güvenlik omurgası olarak kullanılmıştır.

“Tarihî” sayılmasının nedeni yalnızca teknik bir hevesten ibaret değildir: Shor, çarpanlara ayırmanın kuantum polinom zamanda yapılabildiğini göstererek, kuantum hesaplamanın sınıf düzeyindeki etkisini somutlaştırdı ve kriptografi ile karmaşıklık teorisi çevrelerinde geniş bir yankı uyandırdı. Pratikte bugünün donanımıyla büyük RSA modüllerini kırmak hâlâ ölçek dışıdır; fakat “hangi problemler kuantum için yapısal olarak kolaylaşır?” sorusunun net bir örneği olarak durur.

Algoritmanın merkezindeki dönüşüm şudur: doğrudan asal adayları denemek yerine, modüler üs fonksiyonunun periyodunu bulmaya indirgeme ve bu periyodu kuantum devrede faz/girişim deseni olarak okumak. İndirgemenin cebir tarafını 2 · Matematiksel indirgeme bölümünde, devre tarafını ise mimari ve kod bölümlerinde açıyoruz.

Çarpanlama → periyot bulma

Shor’un kalbi, çarpanlara ayırma problemini şu fonksiyonun periyodunu bulmaya indirgemektir: $f(x)=a^x \bmod N$. Burada “mod $N$”, saat çevirir gibi $N$’ye bölünmekten sonra kalanı almak demektir; $x$ arttıkça üs büyür ama çıktı yalnızca $0,\ldots,N-1$ arasında döner — bu yüzden dizi bir noktadan sonra kendini tekrar eder. İşte Shor’un aradığı şey bu tekrarın uzunluğu: en küçük pozitif $r$ için $a^r \equiv 1 \pmod N$ (üslere bakınca “ne zaman tekrar 1’e dönerim?”).

Okuyucu için köprü: çarpanları doğrudan tahmin etmiyoruz; önce “üslü üste bindirilmiş üs”in mod $N$ dünyasında nasıl döngüye girdiğini buluyoruz. Bu döngünün uzunluğu bilindiğinde, aşağıdaki klasik adım çoğu zaman büyük sayıların ortak bölenini (gcd / ebob) kullanarak gerçek çarpan adayları üretir — bu yüzden kuantum tarafı “periyot”, klasik taraf “çarpana çevirme” işini paylaşır.

• Klasik adım

  $N$ çarpanlarına ayrılacak bileşik sayıdır. Rastgele bir taban $a$ seçilirken klasik olarak “aralarında asal” (paydasız / ortak böleni 1) köşeye çekilir: kısaca $\gcd(a,N)=1$. Böylece $a^x \pmod N$ dizisi “temiz” bir periyot üretir. Şans kötü giderse (örneğin $\gcd(a,N)>1$) bazen doğrudan şanslı bir çarpan yakalarsınız; değilse yeni bir $a$ ile yeniden denenir.

• Kuantum adım

  Amaç: $f(x)=a^x \pmod N$ için en küçük pozitif periyot $r$ (bazen “$a$’nın mod $N$’daki çarpım sırası” da denir) tahmin etmek. Kuantum devre (modüler üs + faz tahmini benzeri yapı) periyotla ilgili bilgiyi örnekler; sürekli kesir ve yuvarlama gibi klasik işler sayısal olarak $r$’yi kilitlemeye çalışır. Bu adım tek başına sihir değil: bazen yanlış kesir/yanlış periyot yakalanır ve akış yeniden başlar.

• Sonuç (olasılıksal)

  Periyot $r$ bulunduğunda $a^r \equiv 1 \pmod N$ yazar; bu, $a^{r/2}\pm 1$ sayılarının $N$ ile ortak bölenlerinde çarpan ipuçları saklar (çarpanlara ayırma fikrinin “kare farkı” kökü). Bu yüzden $\gcd(a^{r/2}\pm 1, N)$ hesaplanır (gcd = en büyük ortak bölen / ebob). Genelde $r$ çift ve bazı ek şartlar sağlanırsa trivial olmayan çarpanlar çıkar; değilse yeni deneme gerekir — bu yüzden “olasılıksal”dır.

Shor devresi, sitede işlediğimiz birçok ileri tekniğin bir araya geldiği bir “zirve” örneğidir. Burada amaç, 2 · Matematiksel indirgeme bölümündeki cebirsel hedefi tekrar anlatmak değil: kubitlerin hangi sırada devreye girdiğini, hangi bloğun neden ağır olduğunu ve ölçüm öncesi verinin nerede toplandığını netleştirmek.

Üç blok: maliyet nerede, bilgi nereye akıyor?

• Modüler üs alma

  $x$ üst kayıtta süperpozisyondayken, altta $a^x \bmod N$ hesabını yürüten ünite. QPE şemasında üst kübitlerin her biri, altta farklı bir “kontrollü çarpma gücü” katmanına bağlanır; mod $N$ çarpımları uzun zincirler oluşturduğu için devrenin kapı sayısı ve derinliği burada şişer—oracle hissi de bundandır: tek bir sabit kutu değil, $N$ ve $a$’ya göre yeniden üretilen bir modül.

• Kuantum faz tahmini (QPE)

  Üst kayıt Hadamard ile $x$ adaylarını aynı anda taşır; modüler üs bloğu alt kayıtta doğru “referans” durumu kurdukça, kontrollü ünite fazları üst satıra geri tepki ile yazılır. Böylece alt modülün içinde saklı ritim, üstte okunabilir bir faz örüntüsüne dönüşür—burada amaç tek bir karenin tanımı değil, kuantum faz tahmini sayfasındakiyle aynı ölçüm iskeletini modüler üs için devreye sokmaktır.

• Ters QFT (IQFT)

  Üst kayıttaki fazların süperpozisyonu, spektruma bakmaya benzer: IQFT, bu süperpozisyonu belirli bir bit dizisinde güçlü bir “tepe”ye dönüştürebilir; ölçüm o tepeden bir tam sayı örneği verir. Bu sayı doğrudan “periyot” etiketi taşımak zorunda değildir; klasik tarafta sürekli kesir ve deneme ile yorumlanır (4 · QPE ile bağlantı).

Klasik yöntem, her $x$ için $f(x)$ tablosunu uzatarak periyot arar. Shor ise aynı tabloyu satır satır yazdırmaz; $x$ değerlerini süperpozisyonda üst üste bindirir ve IQFT sonrası ölçümde, periyodu hatırlatan bir girişim deseni seçilir; tek denemede her zaman doğru tepe gelmeyebileceği için akış genelde birkaç kuantum örneği + klasik doğrulama döngüsüyle tamamlanır.

Dev bir faz ölçümü sezgisi

Kuantum faz tahmini (QPE) şunu vaat eder: seçilen ünitenin fazını, üst kayıttaki bit örüntüsü üzerinden bir sayısal tahmin olarak çıkarmak. Shor’da bu “fazı okuma → bitlere dökme” ritmi aynı kalır; fark, hangi ünitenin devreye sokulduğunda ve o tahminin ardından klasik tarafın neyi aradığında ortaya çıkar.

3 · Mimari yapı bölümünde iki kayıt ve blok sırasını gördük. Burada ise QPE ile Shor arasındaki kavram köprüsünü netleştiriyoruz: modüler çarpma ünitesi QPE şemasında nereye oturur; ölçümden çıkan kesir neden doğrudan “periyot etiketi” taşımak zorunda değildir; klasik sürekli kesir adımı bu kopukluğu nasıl kapatmayı dener.

• Genel QPE ne yapıyor?

  Üniteye ait faz bilgisi, kontrollü uygulamalarla üst kayda taşınır; IQFT ise bu fazların süperpozisyonunu ölçümle yakalanabilir bir tam sayı adayına çevirir. Bu aday, “fazın kendisi” değil—fazın dijital bir yaklaşımıdır; QPE sayfasındaki hassasiyet, yuvarlama ve komşu zirveler gibi konular burada da arka planda durur.

• Shor’da ünite neyi temsil ediyor?

  Kalp, mod $N$ çarpanıdır: alt kayıtta biriken durum, üst kayıttaki fazı modüler döngünün ritmine bağlar. Uygun hazırlıkta QPE’nin ürettiği kesir yaklaşımı, 2 · Matematiksel indirgeme bölümündeki periyot arayışıyla “aynı hikâyenin” farklı yüzüdür—biri cebir diliyle, diğeri faz/kesir diliyle konuşur.

• Sürekli kesir neden devreye giriyor?

  Ölçüm tek seferde mükemmel bir kesir vermeyebilir. Sürekli kesir, yakın rasyoneller arasından paydası küçük ve anlamlı olanı seçmeye çalışan klasik bir “sıkıştırma” tekniğidir; uygun şartlarda bu payda, periyot adayı olarak ele alınır ve akış 2 · Matematiksel indirgeme’deki mantıkla birleşir. Satır satır kod ve şema adımları için 5 · Qiskit kod iskeleti, 6 · Terminal çıktısı (draw), 7 · Kod analizi ve 8 · Devre ve doğrulama bölümlerine bakın—burada amaç algoritmayı tekrar etmek değil, bu üç parçanın birbirine nasıl kenetlendiğini sözlü görmektir.

• Klasik tur: gcd nerede kapanır?

  QPE çıktısından gelen kesir / periyot adayı tek başına “çarpan etiketi” taşımak zorunda değildir; Shor’da sıradaki iş genelde yarım periyot üzerinden adaylar üretip gcd ile trivial olmayan bölen aramaktır. Bu tablo, kuantum kısmının bittiği ve masanın tamamen klasik cebire döndüğü yerdir; cebirsel ayrıntı için 2 · Matematiksel indirgeme yeterlidir— 7 · Kod analizi ise aynı hikâyeyi satır satır kod üzerinden tamamlar.

Bu yüzden Shor “QPE’yi çağırıyor” gibi düşünülebilir; fakat pratikte başarı, yalnızca devre çizilmesine değil—precision yeterliliğine, ölçüm şansına ve klasik sürekli kesir/gcd turunun iyi kapanmasına da bağlıdır. Bir parça sapınca genelde yeniden ölçüm veya yeni bir $a$ seçimi devreye girer; bu da algoritmanın neden tamamen “saf kuantum” olmadığını bir kez daha hatırlatı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

qc = shor_period_finding(15, 7)
# print(qc.draw(output="text", fold=-1))  # sayfa #temsiller ile aynı tek şerit

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

Yukarıdaki shor_period_finding(15, 7) iskeletinin Qiskit metin şeması: sekiz precision kübiti, dört state yer tutucusu, bariyer, IQFT ve klasik ölçüm. Modüler üs bloğu kodda yok; gerçek Shor’da bu katman devreyi büyütür. Tek yatay panel için qc.draw(output="text", fold=-1) kullanıldı (varsayılan print(qc) geniş devrelerde » / « bölebilir). Blok özeti için 8 · Devre ve Doğrulama şemasına bakın.

      ┌───┐ ░ ┌───────┐┌─┐                     
 q_0: ┤ H ├─░─┤0      ├┤M├─────────────────────
      ├───┤ ░ │       │└╥┘┌─┐                  
 q_1: ┤ H ├─░─┤1      ├─╫─┤M├──────────────────
      ├───┤ ░ │       │ ║ └╥┘┌─┐               
 q_2: ┤ H ├─░─┤2      ├─╫──╫─┤M├───────────────
      ├───┤ ░ │       │ ║  ║ └╥┘┌─┐            
 q_3: ┤ H ├─░─┤3      ├─╫──╫──╫─┤M├────────────
      ├───┤ ░ │  IQFT │ ║  ║  ║ └╥┘┌─┐         
 q_4: ┤ H ├─░─┤4      ├─╫──╫──╫──╫─┤M├─────────
      ├───┤ ░ │       │ ║  ║  ║  ║ └╥┘┌─┐      
 q_5: ┤ H ├─░─┤5      ├─╫──╫──╫──╫──╫─┤M├──────
      ├───┤ ░ │       │ ║  ║  ║  ║  ║ └╥┘┌─┐   
 q_6: ┤ H ├─░─┤6      ├─╫──╫──╫──╫──╫──╫─┤M├───
      ├───┤ ░ │       │ ║  ║  ║  ║  ║  ║ └╥┘┌─┐
 q_7: ┤ H ├─░─┤7      ├─╫──╫──╫──╫──╫──╫──╫─┤M├
      ├───┤ ░ └───────┘ ║  ║  ║  ║  ║  ║  ║ └╥┘
 q_8: ┤ X ├─░───────────╫──╫──╫──╫──╫──╫──╫──╫─
      └───┘ ░           ║  ║  ║  ║  ║  ║  ║  ║ 
 q_9: ──────░───────────╫──╫──╫──╫──╫──╫──╫──╫─
            ░           ║  ║  ║  ║  ║  ║  ║  ║ 
q_10: ──────░───────────╫──╫──╫──╫──╫──╫──╫──╫─
            ░           ║  ║  ║  ║  ║  ║  ║  ║ 
q_11: ──────░───────────╫──╫──╫──╫──╫──╫──╫──╫─
            ░           ║  ║  ║  ║  ║  ║  ║  ║ 
 c: 8/══════════════════╩══╩══╩══╩══╩══╩══╩══╩═
                        0  1  2  3  4  5  6  7 

İskeletin rolü

Bu bölüm, editördeki kodun akış sırasını sabitlemek için: önce hangi register’ın ne yaptığını, sonra her satırın QPE/Shor hikâyesindeki yerini okursunuz. Ayrıntılı metin şema ile eşleştirmek için 6 · Terminal çıktısı (draw) bölümündeki hat rehberine dönebilirsiniz.

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. Pratikte önce N’nin bit uzunluğunu, sonra modüler çarpanın hangi ailede seçileceğini netleştirirsiniz; iskelet bu iki tarafı da “daraltılmış oyuncak” olarak tutar ki akış kaybolmasın.

qc.h(range(8))

Üst register’a Hadamard, QPE’nin başlangıç süperpozisyonunu kurar: faz bilgisini hangi kombinasyonların taşıyacağı burada belirlenir. Her üst kübit, sonradan gelecek kontrollü üs uygulamalarında farklı bir “ikili ağırlık” taşır; bu yüzden Shor’u Grover’den ayıran şey, başlangıçta tek bir yoğun hedef aramak değil, tüm indekslere eşit genlikle açılıp sonra modüler dinamikle seçici faz üretmektir.

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. Çarpan bulmada ilgilendiğiniz çoğu zaman çarpanların paydası olan periyottur; alt register’ın doğru alt uzayda başlaması, üstteki faz deseninin anlamlı kalması için şarttı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. Klasikte “üst üste çarpma” diye düşündüğünüz iş, burada kontrollü çarpma ve taşıma ağlarına yayılır; derinlik genelde N’ye bağlı polinom büyüklükte olur, fakat üst sınırı kitaplardan birebir taşımak yerine kendi donanım kısıtınızı baz alın.

QFT(8).inverse()

IQFT, precision’daki fazı bit desenine çevirir — Shor’da “periyot ipucu”nun klasik tarafa sızdığı adım. Hassasiyet yetersizse veya gürültü yüksekse, tek ölçümde “mükemmel” ikili kesir beklemek gerçekçi değildir; bu yüzden aşağıdaki klasik post-processing, çoğu zaman birden fazla denemenin istatistiğini de içerir.

Ö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. Başarısızlıkta tipik akış yeniden a seçmek veya precision’ı artırmaktır; “kuantum kısmı bitti” sandığınız anda aslında hikâyenin yarısı klasikte kapanır.

Ş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. Qiskit’in tam metin şeması (tüm kübit hatları) için 6 · Terminal çıktısı (draw) bölümüne bakın.

Ş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/IQFT, QPE ve Simon hatları burada aynı hikâyenin farklı yüzleri olarak bir araya gelir. Burada amaç formülleri yeniden dökmek değil; ölçek, istatistik ve neden bugün hâlâ masa başında kaldığımızı bir çerçeveye oturtmak.

Aşağıdaki kartlar, 2 · Matematiksel indirgeme ile 4 · QPE ile bağlantı bölümlerinin “özet tekrarı” değil; üretim gerçekliği ve okuma haritası düzeyinde durur.

• Kübit ihtiyacı

  Giriş sayısının ikilik uzunluğu $L$ ile ölçeklenir: kusursuz bir makinede kabaca $\mathcal{O}(L)$ kübit ve çok daha derin devreler konuşulur. RSA-2048 gibi hedefler için hatasız kübit sayısı milyonlar mertebesinde tartışılır; bugünün NISQ donanımı bu rejimden uzaktır; mesele yalnızca “az kübit” değil, gürültü ve hata birikimidir.

• Girişim filtresi

  IQFT, fazların süperpozisyonunu ölçülebilir bir kalıba çevirir; periyoda uygun “tepe” genelde öne çıkar, ama gerçek dünyada tek ölçümde tek bir net frekans garantisi yoktur—çoğu deneyde dağılım birikir. Bu yüzden Shor pratikte “bir kez çalıştır ve bitti” değil, örnekleyip klasik tarafta doğrulayan bir döngüdür (3 · Mimari yapı ile uyumlu).

• Hibrit doğa

  Kuantum tarafı periyotla ilgili faz bilgisini örnekler; çarpan adaylarını kilitleyen sürekli kesir ve $\gcd$ işi klasiktir. İş akışının iskeleti 4 · QPE ile bağlantı ve 5 · Qiskit kod iskeleti bölümlerinde; burada yalnızca hatırlatma: Shor, Simon örneğinde olduğu gibi hibrit bir boru hattıdır.

• PQC ekosistemi · bağlantılı okumalar

  Teoride Shor, RSA/ECC ailesine uzun vadeli bir tehdit çerçevesi çizer; pratikte ise standartlaşan kuantuma dayanıklı kriptografi (PQC) geçişi, protokol güncellemeleri ve dağıtım yılları alır. Bu kartın mesajı “yarın sabah her şey çöker” paniği değil; risk yönetimi ve yol haritası dilidir—donanım kısıtı alttaki özet kutuda, kurumsal zaman çizelgesi burada ayrışır.
  
  Teknik köprüleri tazelemek için: Kuantum Fourier (QFT) · Qiskit, Kuantum faz tahmini (QPE) · Qiskit, Simon algoritması · Qiskit.

QPE köprüsünü derinleştirmek için Kuantum faz tahmini (QPE) · Qiskit; üst karttaki QFT ve Simon bağlantıları aynı zincirin diğer halkalarıdır.