Kuantum Yürüyüşleri

Kuantum yürüyüşü, klasik rastgele yürüyüşün kuantum dünyadaki karşılığıdır: parçacığın konumları üstünde taşınan şey olasılık değil, girişim yapabilen genliktir. Bu derste iki temel modeli sıfırdan kuracağız — ayrık adımlı kaplımlı yürüyüş ile bir graf üstünde sürekli zamanlı evrim — ve girişimin dağılımı nasıl değiştirdiğini iki adımlık küçük bir hesapla göreceğiz. Kübit, genlik ve ölçümü henüz görmediysen önce Kuantum Hesaplama 101 dersine dönmek iyi fikirdir; serinin tamamı Kuantum Hesaplama dersleri sayfasında bir arada.

Klasik Rastgele Yürüyüş: Olasılıkla Yayılma

Bir parçacık sayı doğrusunda dursun; her adımda yazı tura atıp 1/2 olasılıkla sağa (+1), 1/2 olasılıkla sola (−1) gitsin. N adım sonundaki konum X olsun. Adımlar bağımsız ve ortalamaları sıfır olduğundan E[X] = 0; varyans adım adım toplanır: E[X²] = N. Yani tipik uzaklık √N mertebesindedir: 100 adımda 10, 10.000 adımda 100 birim.

Kuantumda konumlar üstünde olasılık değil genlik taşınır. Durum Σₓ ψₓ|x⟩ biçiminde yazılır; ölçüme kadar ψₓ karmaşık sayılardır ve iki ayrı yol aynı konuma ulaştırdığında genlikler toplanır — işaretleri zıt ise söndürür. Adım operatörleri üniteryen olduğu için toplam olasılık her adımda korunur (Σₓ|ψₓ|² = 1 kalır), ama dağılım girişimle yeniden şekillenir.

Kaplımlı Kuantum Yürüyüşü: Yazı Tura ⊗ Konum

Ayrık zamanlı modelde iki uzay birleştirilir: konum uzayı ile yazı tura görevi gören iki boyutlu bir coin uzayı. Tam durum |x⟩ ⊗ |c⟩ biçimindedir; c = 0 sağa, c = 1 sola hareketi kodlar. Bir adım iki kapının ardışık uygulanmasından oluşur:

• Coin kapısı: yalnız coin kübitine etkiyen Hadamard; H|0⟩ = (|0⟩+|1⟩)/√2, H|1⟩ = (|0⟩−|1⟩)/√2.
• Kaydırma kapısı: coin'e bakarak taşır: S|x, 0⟩ = |x+1, 0⟩, S|x, 1⟩ = |x−1, 1⟩.

Bir tam adım U = S·(I ⊗ H) operatörüdür; H ve S üniteryen olduğundan U da üniteryendir, norm korunur. Başlangıcı |0⟩ ⊗ |0⟩ seçip iki adımı elle hesaplayalım:

1. Coin, |0⟩'yu (|0⟩+|1⟩)/√2'ye çevirir; kaydırma sonrası durum (1/√2)(|1⟩|0⟩ + |−1⟩|1⟩) olur. Ölçseydin ±1'i 1/2 olasılıkla görürdün — klasik bir adımla aynı.
2. İkinci turda coin her bileşene ayrı uygulanır, kaydırma işi bitirir: (1/2)(|2⟩|0⟩ + |0⟩|1⟩ + |0⟩|0⟩ − |−2⟩|1⟩).

İki adım sonunda P(0) = 1/2, P(±2) = 1/4'er; toplam 1'dir, normalizasyon yerindedir ve klasik iki adımla çakışır — fark üçüncü adımda patlar. Üç adımda (x = 1, coin 0)'a iki ayrı yol ulaşır ve genlikler toplanır: P(1) = 5/8, P(−1) = 1/8, P(±3) = 1/8 (klasikte 3/8, 3/8, 1/8, 1/8). Dağılım başlangıç coin'i |0⟩ olduğu için sağa yatıktır; simetrik coin (|0⟩ + i|1⟩)/√2 seçilirse dengelenir. Sonuç: varyans klasikteki ~t yerine ~(1 − 1/√2)t² ≈ 0,29t² gibi karesel büyür; standart sapma ~0,54t ile doğrusaldır.

Sürekli Zamanlı Kuantum Yürüyüşü: Graf Üzerinde Evrim

İkinci model adım atmaz; zaman akar. Bir graf al: köşeler konum, kenarlar komşuluk; komşuluk matrisi A'nın x, y girişi komşuysa 1, değilse 0 olsun. Sürekli zamanlı yürüyüşün Hamiltonian'ı H = γA'dır (γ yayılma katsayısı) ve durum Schrödinger evrimiyle hareket eder: |ψ(t)⟩ = e^(−iHt)|ψ(0)⟩ (ℏ = 1). H Hermitian olduğundan e^(−iHt) üniteryendir; norm yine korunur. Modeli 1998'de Farhi ve Gutmann, karar ağaçları üstünde hesaplama bağlamında önerdi.

Bu evrim özünde bir Hamiltonian simülasyonu işidir; bağlantıyı derinleştirmek için Hamiltonian Simülasyonu dersine bakabilirsin. Algoritmik taraf da çarpıcıdır: Childs ve arkadaşları 2003'te, yapıştırılmış ağaçlar (glued trees) grafinde iki işaretli köşe arasındaki geçişin kuantum yürüyüşle üstel hızlanarak çözülebileceğini gösterdi; Childs 2009'da ayrıca kuantum yürüyüşünün tek başına evrensel kuantum hesaplama için yeterli olduğunu kanıtladı.

Klasik mi Kuantum mu? Karşılaştırma ve Hızlanma

İki yürüyüşü yan yana koyalım:

• Taşınan şey: klasikte olasılık; kuantumda genlik, olasılığın işaretli ve karmaşık olabilen karekökü.
• Girişim: klasikte yollar etkileşmez; kuantumda aynı sonuca giden yolların genlikleri toplanır ya da sönümlenir.
• Varyans: klasik ~t; Hadamard yürüyüşünde ~(1 − 1/√2)t² ≈ 0,29t².
• Standart sapma: klasik ~√t; kuantum ~0,54t (doğrusal).
• L uzaklığına ulaşma: klasik ~L² adım; kuantum ~L adım — karesel ivme.

Bu ivme algoritmalara dönüşür. Szegedy'nin 2004 kuramı, Markov zincirlerinin kuantum karşılığını kurarak Grover benzeri karesel arama hızlanması sağlar. Ambainis'in eleman ayrıklığı algoritması, N sayının tümü birbirinden farklı mı sorusunu klasik O(N) sorguya karşı kuantum yürüyüşle O(N^(2/3)) sorguda yanıtlar. Graf üstünde optimizasyon için QAOA, ölçüm olasılıklarını hızlı tahmin için Genlik Tahmini derslerine göz at.

Sık Yapılan Hatalar ve Yanılgılar

En sık düşülen beş hata:

• Yürüyüşün kendisini rastgele sanmak: ölçüme kadar hiçbir şey rastgele değildir; U = S·(I ⊗ H) deterministik, üniteryen bir evrimdir. Rastgelelik yalnızca ölçümde girer.
• Coin'i ölçüm sanmak: coin, bilgiyi koruyan bir üniteryen kapıdır; süperpozisyonu çökertmez.
• Varyansla sapmayı karıştırmak: karesel büyüyen varyanstır; standart sapma doğrusal büyür. Karesel hızlanma deyince genellikle bu yayılma farkı (√t'den t'ye) kastedilir.
• Sürekli zamanlı modelde H'ı üniteryen sanmak: H = γA Hermitian'dır; üniteryen olan e^(−iHt)'dir.
• Gürültüyü hesaba katmamak: derin yürüyüş devreleri hataya açıktır; önceki ünitedeki Mantıksal Kübitler ve Hata Toleranslı Kuantum Hesaplama katmanı gerekir.

Bu devreleri bir çip üstünde koşturmak ayrı bir donanım meselesidir; ünitenin ardından gelen Süperiletken Kübitler gibi derslerde bu teknolojileri işleyeceğiz. Tüm derslerin içindekiler için Konu Anlatımı sayfasına göz atabilirsin.

Kaynaklar ve İleri Okuma

Quantum walk — Wikipedia — kaplımlı ve sürekli zamanlı modellerin tanımları ile temel yayılma sonuçlarının özeti.

Exponential algorithmic speedup by quantum walk (Childs ve ark.) — glued trees grafinde üstel hızlanmayı gösteren makalenin arXiv özeti.

Quantum walk algorithm for element distinctness (Ambainis) — eleman ayrıklığını kuantum yürüyüşle O(N^(2/3)) sorguda çözen makalenin arXiv özeti.

IBM Quantum Learning — kübit, üniteryen kapı ve ölçüm temellerini uygulamalı pekiştirmek için IBM'in resmî kurs platformu.