Kuantum Hızlanması

Kuantum Hesaplama · Bölüm 99Kuantum Hesaplama2026-09-29Ders

Kuantum bilgisayarın “hızlı” olması saat hızıyla değil, büyüme eğrisiyle ölçülür: aynı problemi çözen iki yöntemden hangisi, problem büyüdükçe daha az kaynakla yetiniyor? Bu derste kuantum hızlanmasının ne demek olduğunu, kuadratik ve üstel biçimlerini, sayılarla bir karşılaştırmayı ve bu iddiaların nerede kanıtlı olduğunu öğreneceksin. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına göz atabilirsin.

Hızlanma Tam Olarak Neydir?

Karşılaştırmanın ölçütü sabit katsayılar değil, büyüme eğrisidir: girdi n büyürken gereken kaynak (adım, kapı ya da sorgu) sayısı ne kadar hızlı artıyor? Klasik en iyi algoritmanın maliyeti f(n), kuantumunki g(n) olsun; g(n) belirgin biçimde yavaş büyüyorsa bir kuantum hızlanmasından söz ederiz. Tek bir kuantum kapısı fiziksel olarak yavaş olsa bile, adım sayısı daha yavaş büyüyorsa kazanç n büyüdükçe sabit yavaşlığı geride bırakır.

İki ince nokta: √N gibi iddialar çoğu kez sorgu sayısını ölçer; oracle’ı kurmanın maliyeti ayrı bir hesaptır — bu ayrım Sorgu Karmaşıklığı dersiyle Oracle Modelleri dersinin konusudur. Ayrıca hızlanma, bilinen en iyi klasik algoritmaya göre mi ölçülüyor, yoksa alt sınır olarak mı kanıtlı? Aşağıda bu ayrım önemli olacak.

İki Biçim: Kuadratik ve Üstel Hızlanma

Kuadratik hızlanma. Klasik maliyet N iken kuantum maliyeti yaklaşık √N olur. Standart örnek Grover aramasıdır: N adaylı uzayda klasik arama O(N) sorgu yaparken Grover yaklaşık (π/4)·√N turda biter. Kazanç oranı N/√N = √N’dir; problem büyüdükçe oran büyür ama polinomiyal kalır. Aynı faydanın “uzayda kaç çözüm var?” sorusuna uyarlanmış hâlini önceki ünitedeki Kuantum Sayma dersinde görmüştün.

Üstel hızlanma. Klasik maliyet girdiyle üstel ya da alt-üstel büyürken kuantum maliyeti polinomda kalır. Önceki üniteden Shor Algoritması bunun bayrak örneğidir: n bitlik bir sayıyı klasikte polinomiyal olmayan, bilinen en iyi maliyetle çarpanlarına ayırmak gerekirken Shor, O(n³) mertebesinde kapı sayısıyla yetinir. Aynı ünitedeki Gizli Alt Grup Problemi dersi kazanımın ortak iskeletini göstermişti: gizli periyodik yapıyı bul, üstel kazancı kap; çarpanlara ayırma ve ayrık logaritma bu iskeletin özel hâlleridir.

Sayılarla Adım Adım

Kuadratik taraf. N = 2⁴⁰ ≈ 1,1 trilyon adaylı bir arama alalım. (1) Klasik: ortalama N/2 ≈ 550 milyar sorgu. (2) Grover: √N = 2²⁰ = 1.048.576 olduğundan tur sayısı (π/4)·√N ≈ 824 bin. (3) Oran: 550 milyar ÷ 824 bin ≈ 670.000 — yaklaşık 670 bin kat daha az sorgu. Problem bir bit büyüse (N = 2⁴¹) klasik ortalama ikiye katlanır; Grover turları yalnızca √2 ≈ 1,41 katı artar.

Üstel taraf. 2048 bitlik bir RSA modülünü çarpanlarına ayıralım. (1) Kuantum: Shor ile O(n³) ≈ 2048³ = 2³³ ≈ 8,6 milyar kapı işlemi mertebesi. (2) Klasik: bilinen en iyi genel yöntem olan genel sayı cisim eleği, exp(O((log n)^(1/3)·(log log n)^(2/3))) biçiminde büyüyen bir zaman ister; n = 2048 için bu, pratikte imkânsız bir ölçektir. (3) Fark “kaç kat” değil, kategoriktir: n büyüdükçe klasik eğri patlar, kuantum eğrisi düz kalır.

Hızlanma İddiasının Künyesi: Nerede Kanıtlı?

Bir hızlanma iddiasını değerlendirirken üç ayrımı yan yana koyarız:

Oracle modelinde kanıtlı: Simon problemi gibi kâhin problemlerinde klasik tarafın en az 2^(n/2) mertebesinde sorgu gerektirdiği, kuantumun O(n) sorguyla yettiği kesin olarak kanıtlanmıştır. Bennett–Bernstein–Brassard–Vazirani alt sınırına göre güvenilir arama c·√N’den az sorguyla bitmez; Grover’ın √N kazanımı sorgu modelinde optimaldir.
Bilinen en iyiye göre: Shor’un kazanımı, çarpanlara ayırmanın hızlı bir klasik algoritmasının olmadığına dair kanıt değil, bugün bilinen en iyi klasik yönteme göre bir karşılaştırmadır; klasik tarafta bir atılım olursa daralabilir.
Sınıf düzeyinde: BPP ⊆ BQP bilinir ama BQP’nin BPP’den kesin ayrı olduğu bugünkü tekniklerle kanıtlanamaz; BQP ⊆ PSPACE gibi üst sınırlar kazancı yukarıdan çerçeveler. Sınıf tanımları için Kuantum Karmaşıklık Sınıfı BQP ile Olasılıksal Karmaşıklık BPP derslerine bak.

Pratikte iki bedel daha var; ikisi de asimptotiği bozmaz. Tekrar: Shor’da ölçülen periyot bazen aradığın böleni vermez, algoritma birkaç kez koşar; tekrar sayısı polinomiyal kaldıkça üstel kazanç korunur. Hata düzeltme: bir mantıksal kübit için çok sayıda fiziksel kübit gerekebilir; hızlanmanın makinede belirmesi sonraki ünitenin tabanına bağlıdır — bkz. Bit Flip ve Phase Flip Hataları ile Tekrarlama Kodları.

Sık Yapılan Yanılgılar ve Özet

En sık duyulan dört yanılgıyı düzeltelim:

“Kuantum bilgisayar tüm cevapları paralel dener, en iyisini okur.” Hayır; n kübit 2ⁿ genliği taşır ama ölçüm tek sonuç verir. Kazanç, genliklerin girişimle doğru cevapta toplanmasından gelir; girişimi ayarlayamadığın problemde paralellik tek başına işe yaramaz.
“Hızlanma, daha hızlı makine demektir.” Değil; karşılaştırma adım ya da sorgu sayısının büyüme eğrisiyle yapılır, saat hızıyla değil.
“Her problem üstel hızlanır.” Bilinen üstel hızlanmalar periyodiklik gibi özel bir yapı ister; sıralama gibi çok sayıda görev için belirgin hızlanma bilinmez. Genel amaçlı kazanç kuadratiktir ve sorgu modelinde daha iyisi mümkün değildir.
“Kuantum bilgisayar NP-tam problemleri hızla çözer.” Bunun için hiçbir kanıt yok; BQP’nin NP-tam problemleri verimli çözdüğü de beklenmez. Ayrımın neden kritik olduğu için Klasik Karmaşıklık Sınıfları P ve NP dersine bak.

Kısa özet: kuadratik hızlanma N → √N, üstel hızlanma üstel → polinom demektir; birincisi sorgu modelinde optimal, ikincisi özel yapı ister ve bugün “bilinen en iyiye göre” geçerlidir. Her iddiada kanıt statüsünü ayrıca sor. Tüm derslerin içindekiler için Konu Anlatımı sayfasına göz atabilirsin.

Sık Sorulan Sorular

Kuantum hızlanması nedir?

Aynı problemi çözen en iyi klasik algoritmanın kaynak maliyetine göre, kuantum algoritmasının belirgin biçimde daha yavaş büyüyen bir maliyetle problemi çözmesidir. Ölçüt saat hızı değil, adım ya da sorgu sayısının girdi büyüklüğüyle artış eğrisidir. İki temel biçimi vardır: kuadratik (N → √N) ve üstel (üstel → polinom).

Kuantum bilgisayarlar her problemde hızlanma sağlar mı?

Hayır. Bilinen üstel hızlanmalar problemde özel bir periyodiklik ya da gizli alt grup yapısı gerektirir; sıralama gibi birçok görev için belirgin hızlanma bilinmez. Genel amaçlı tek kazanç, Grover türü kuadratik iyileşmedir ve o bile sorgu modelinde kanıtlanmış biçimde optimaldir.

Shor algoritmasının üstel hızlanması kanıtlanmış mı?

Yarı. Shor’un çarpanlara ayırmayı polinom zamanda yaptığı kesindir; kanıtlanmamış olan, klasik tarafta hızlı bir algoritmanın var olmadığıdır. Yani üstel hızlanma “bilinen en iyi klasik algoritmaya göre” bir iddiadır. Kanıtlı ayrımlar için Simon problemi gibi oracle tabanlı problemlere bakılır.

Kuadratik ve üstel hızlanma arasındaki fark nedir?

Kuadratik hızlanma maliyeti N’den √N’e indirir; Grover araması bunun örneğidir ve büyüme eğrisinde bir kademe sayılır. Üstel hızlanmada klasik maliyet girdiyle üstel ya da alt-üstel büyürken kuantum polinomda kalır; Shor bunun örneğidir ve fark kategoriktir: n büyüdükçe klasik taraf uygulanamaz olur, kuantum eğrisi düz kalır.

Kaynaklar ve İleri Okuma

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (P. Shor) — Shor algoritmasının özgün makalesi; üstel hızlanma iddiasının kaynağı.

A fast quantum mechanical algorithm for database search (L. Grover) — kuadratik hızlanmanın standart örneğini sunan makale.

Quantum supremacy — Wikipedia — hızlanma iddialarının deneysel boyutu.

Shor’s algorithm — Wikipedia — algoritmanın adımları ve karmaşıklık karşılaştırması.

IBM Quantum Learning — Grover ve Shor devrelerini uygulamalı kuran resmî ders materyali.