Kuantum yürüyüşleri: rastgele yürüyüşün kuantum hâli

Yazı-turayla sağa sola adım atan bir yürüyüşçü düşün. Kuantum yürüyüşünde girişim, yürüyüşçüyü klasik hâlinden çok daha hızlı yayar. Arama algoritmalarının arkasındaki bu fikri tanı.

Klasik rastgele yürüyüş

Bir doğru üzerinde duran bir yürüyüşçü her adımda yazı-tura atar: yazı gelirse sağa, tura gelirse sola bir adım atar. Adımlar birbirini kısmen götürdüğü için yürüyüşçü başladığı yerden yavaş uzaklaşır: t adım sonra tipik uzaklık yalnızca √t kadardır. 50 adımda bu yaklaşık 7 adımdır.

Kuantum yürüyüşü

Kuantum yürüyüşünde yazı-tura yerine bir “para kübiti” vardır ve her adımda ona H kapısı uygulanır. Ardından yürüyüşçü, para kübitinin değerine göre sağa ya da sola kayar. Ölçüm yapılmadığı için yürüyüşçü bütün yolların süperpozisyonunda ilerler ve aynı noktaya varan yollar girişim yapar.

Girişim, ortadaki noktalarda yolların birbirini söndürmesine, uçlardaki noktalarda ise güçlenmesine yol açar. Sonuçta yürüyüşçü √t yerine t ile orantılı hızda yayılır. Aşağıdaki kod 50 adımlık bir kuantum yürüyüşünü hesaplar: tipik uzaklık klasik yürüyüşteki 7 yerine yaklaşık 27 adımdır.

import numpy as np

steps = 50
size = 2 * steps + 1
psi = np.zeros((size, 2), dtype=complex)        # konum x para kübiti
psi[steps] = [1 / np.sqrt(2), 1j / np.sqrt(2)]  # ortadan, dengeli bir parayla başla
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

for _ in range(steps):
    psi = psi @ H.T                  # para kübitine H
    new = np.zeros_like(psi)
    new[:-1, 0] = psi[1:, 0]         # para 0 ise sola kay
    new[1:, 1] = psi[:-1, 1]         # para 1 ise sağa kay
    psi = new

prob = (abs(psi) ** 2).sum(axis=1)
x = np.arange(size) - steps
print(np.sqrt((prob * x**2).sum()), np.sqrt(steps))   # yaklaşık 27.1 ve 7.1

Ne işe yarar?

Kuantum yürüyüşleri birçok kuantum algoritmasının yapı taşıdır. Grover araması bir graf üzerinde kuantum yürüyüşü olarak da yazılabilir. Ambainis’in 2003’te bulduğu algoritma, bir listede iki aynı eleman olup olmadığını klasik yöntemlerden daha az sorguyla bulur. Childs ve arkadaşları da aynı yıl, özel olarak kurulmuş bir grafta kuantum yürüyüşünün klasik her yöntemden üstel olarak hızlı ilerlediğini gösterdi.

Bugün kuantum yürüyüşleri arama, graf problemleri ve fiziksel sistemlerin simülasyonu için araştırılıyor; fotonik cihazlarda deneysel olarak da gösterildi.

Kendin dene

Kuantum yürüyüşünü yayan şey girişimdir. Bu örnekte iki H kapısı arka arkaya gelir ve 1’e giden iki yol birbirini söndürür: sonuç kesin 0. Yürüyüşte de bazı noktalara giden yollar böyle söner, bazılarına gidenler güçlenir.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

Klasik rastgele yürüyüşte tipik uzaklık √t ile, kuantum yürüyüşünde t ile büyür.
Kuantum yürüyüşünde para kübiti H ile karıştırılır ve yollar girişim yapar.
50 adımda kuantum yürüyüşçü yaklaşık 27, klasik yürüyüşçü yaklaşık 7 adım uzaklaşır.
Arama ve graf algoritmalarının birçoğu kuantum yürüyüşlerine dayanır.

Kendini sına

Klasik rastgele yürüyüşte 100 adım sonra tipik uzaklık yaklaşık kaç adımdır?

Cevabı göster

10. Klasik yürüyüşte tipik uzaklık √t’dir: √100 = 10. Kuantum yürüyüşü ise t ile orantılı yayılır.

← QAOA: optimizasyon problemlerine kuantum yaklaşım · Kuantum avantajı nerede? Algoritmaların büyük resmi →