مهندس کوانتومی›الگوریتم‌های کوانتومی›فصل 22

22. الگوریتم سایمون (Simon)

پنج سطح این فصل

شهود — دورهٔ پنهان s یک تابع دوبه‌یک را پیدا کنید؛ تداخل دقیقاً رشته‌های متعامد با s را باقی می‌گذارد.
ریاضیات — هر اندازه‌گیری y می‌دهد با y·s = 0 (به پیمانهٔ ۲)؛ n−1 نمونهٔ مستقل، s را با جبر خطی روی GF(2) معین می‌کنند.
پیاده‌سازی — شبیه‌سازی کامل ۶ کیوبیتی به‌علاوهٔ حذف گاوسی روی GF(2).
مهندسی — اورکل باید واقعاً دوبه‌یک باشد؛ پس‌پردازش پیش‌پاافتاده است؛ نویز ساختار تعامد را لکه‌دار می‌کند.
پژوهش — مسئله‌های زیرگروه پنهانِ آبلی حل شده‌اند؛ غیرآبلی‌ها (هم‌ریختی گراف) ۳۰ سال در برابر حمله مقاومت کرده‌اند.

22.1مسئلهٔ دورهٔ پنهان

سایمون (Simon) در ۱۹۹۴ مسئله‌ای را تعریف کرد که جدایی نمایی را سرانجام عینی کرد. با جعبه‌سیاه f: {0,1}ⁿ → {0,1}ⁿ موعودشده که دوبه‌یک با دورهٔ پنهان s ≠ 0 است — یعنی f(x) = f(y) اگر و فقط اگر y = x ⊕ s — پیدا کنید s. هیچ موعود خطی یا متوازن یا چیز دیگری در کار نیست؛ کل فضای ورودی با XOR با s جفت‌جفت شده. به‌طور کلاسیک این سخت به نظر می‌رسد: برای یافتن s عملاً باید برخورد پیدا کنید، دو ورودی که به یک مقدار می‌روند.

22.2چرا مسئله اهمیت دارد

سه دلیل. جدایی در برابر کلاسیکِ خطای محدود نمایی است: یافتن برخورد میان 2ⁿ مقدار با کران پایین Θ(2^{n/2}) پرس‌وجو (کران روز تولد) همراه است — در برابر O(n) پرس‌وجوی کوانتومی. ماشهٔ تاریخی: پیش‌چاپ سایمون در ۱۹۹۴ به پیتر شور (Peter Shor) رسید و مستقیماً قالب تجزیه شد؛ بدون سایمون احتمال خوبی هست که الگوریتم شور یک دهه بعد کشف می‌شد. قالب: سایمون نخستین نمونه از مسئلهٔ زیرگروه پنهان است — بازیابی زیرگروه H از تابعی که روی هم‌مجموعه‌های H ثابت و متمایز است — و الگوی حلش (برهم‌نهی، اورکل، نمونه‌برداری فوریه، جبر کلاسیک) دقیقاً الگوی شور است.

22.3تداخل کوانتومی

برهم‌نهی یکنواخت را آماده کنید، اورکل را بزنید و ثبات ورودی به جفت‌ها درهم‌تنیده می‌شود: (1/√2ⁿ)·Σ_x |x⟩|f(x)⟩ = (1/√2ⁿ)·Σ_c (|c⟩ + |c⊕s⟩)|f(c)⟩. H^{⊗n} را روی ثبات ورودی اعمال کنید. دامنهٔ خروجی y ضریب 1 + (−1)^{s·y} را حمل می‌کند — دو جملهٔ هر جفت وقتی s·y = 0 (به پیمانهٔ ۲) سازنده و در غیر این صورت کامل حذف‌اند. پس توزیع اندازه‌گیری یکنواخت روی زیرفضای {y : y·s = 0} با اندازهٔ 2^{n−1} است و بیرونش صفر. یک پرس‌وجو دورهٔ پنهان را به دستگاه معادلات خطی روی GF(2) تبدیل کرده است — هر y نمونه‌برداری‌شده یک معادلهٔ s·y = 0 است.

22.4استخراج جبر خطی

خروجی‌های y₁, …, y_k را جمع کنید؛ هر یک s·yᵢ = 0 (پیمانهٔ ۲) را ارضا می‌کند. آن‌ها را در ماتریس بیتی k×n بچینید و فضای پوچی (kernel) را با حذف گاوسی روی GF(2) حل کنید — جابه‌جایی سطرها و XOR سطرها، حساب به پیمانهٔ ۲. وقتی معادلات جمع‌شده رتبهٔ n−1 داشته باشند، فضای پوچی دقیقاً {0, s} است و s بازیابی می‌شود. برداشتن n−1 نمونه با احتمال Π_{j=1}^{n−1}(1−2^{−j}) ≈ 0.29 رتبهٔ کامل می‌دهد؛ چند نمونهٔ اضافه آن را نزدیک ۱ می‌برد، پس راهبرد استاندارد «دسته بگیر و تکرار کن» است. مجموعاً: O(n) پرس‌وجوی اورکل، O(n³) پس‌پردازش کلاسیک — در برابر Θ(2^{n/2}) پرس‌وجوی کلاسیک. پس‌پردازش همان بخشی است که باید با دقت پیاده‌سازی کنید؛ جایی است که بیشتر پیاده‌سازی‌های خانگی سایمون شکست می‌خورند.

22.5پیاده‌سازی

گام کوانتومی کامل، شبیه‌سازی‌شدهٔ صادقانه برای n = 3 (بردار حالت ۶ کیوبیتی، ۶۴ دامنه):

import numpy as np
from functools import reduce
rng = np.random.default_rng(7)
n, s = 3, 0b101                              # رشتهٔ پنهان s = 101
lab = rng.permutation(2 ** n)                # مقدار تصادفی به‌ازای هر جفت {x, x^s}
f = np.array([lab[min(x, x ^ s)] for x in range(2 ** n)])
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
Hn = reduce(np.kron, [H] * n)                # H روی ثبات ورودی
psi = np.zeros(2 ** (2 * n), dtype=complex)
for x in range(2 ** n):
    psi[(x << n) | f[x]] = 1                 # |x>|f(x)> پس از اورکل
psi = np.kron(Hn, np.eye(2 ** n)) @ psi      # H نهایی روی ثبات ورودی
p = (np.abs(psi.reshape(2 ** n, 2 ** n)) ** 2).sum(axis=1)
sup = np.where(p > 1e-12)[0]
print("support:", sup)
print("all satisfy y·s = 0:",
      all(bin(y & s).count("1") % 2 == 0 for y in sup))

اجرااش کنید: پشتیبان {0, 2, 5, 7} است و هر عنصر y·s = 0 را ارضا می‌کند — ادعای تداخلِ ۲۲.۳، راستی‌آزمایی‌شده به‌صورت عددی نه اعتمادشده.

import numpy as np
Y = np.array([[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 1]])  # yهای نمونه‌گیری‌شده (y·s = 0)
n = 3
M, piv, r = Y.copy() % 2, [], 0
for c in range(n):
    pr = next((i for i in range(r, len(M)) if M[i, c]), None)
    if pr is None:
        continue
    M[[r, pr]] = M[[pr, r]]
    for i in range(len(M)):
        if i != r and M[i, c]:
            M[i] = (M[i] + M[r]) % 2
    piv.append(c); r += 1
basis = []
for c in range(n):
    if c not in piv:                          # ستون آزاد -> بردار فضای پوچی
        v = np.zeros(n, dtype=int); v[c] = 1
        for i, pc in enumerate(piv):
            if M[i, c]:
                v[pc] = 1
        basis.append(v)
print(basis)    # [array([1, 0, 1])]  ->  s = 101

22.6پیوند با شور

هر دو الگوریتم را مسئلهٔ زیرگروه پنهان (hidden subgroup problem) ببینید: با f که روی هم‌مجموعه‌های زیرگروه پنهان H ثابت و متمایز است، H را پیدا کنید. سایمون آن را برای H = {0, s} در گروه (Z₂)ⁿ حل می‌کند؛ نمونه‌برداری فوریه روی (Z₂)ⁿ همان نمونه‌برداری هادامارد است و گام کلاسیک، جبر خطی. شور آن را برای H = rZ (مضرب مرتبهٔ r) در گروه اعداد صحیح حل می‌کند — نمونه‌برداری فوریه همان QFT روی گروه پیمانه‌ای است و گام کلاسیک، کسر مسلسل. یک اسکلت: برهم‌نهی، یک خانواده اورکل، نمونه‌برداری فوریه، جبر. الگوریتم سایمون اکتبر ۱۹۹۴ آمد؛ الگوریتم شور، ساخته‌شده روی ستون فقراتش، چند هفته بعد.

مرز پژوهش: مسئلهٔ زیرگروه پنهان

حالت آبلی حل شده (سایمون، شور، کیتائف) و تقریباً همان‌جا تمام می‌شود. برای گروه‌های غیرآبلی — مشهورتر از همه گروه متقارن، که حل کوانتومی‌اش الگوریتم زیرنمایی برای هم‌ریختی گراف (graph isomorphism) می‌داد — نمونه‌برداری فوریه اثباتاً کافی نیست و تکنیک جایگزینی شناخته نشده. سی سال کار نتایج جزئی و شواهد قوی به‌جا گذاشته که مسئلهٔ زیرگروه پنهان غیرآبلی به ایده‌های واقعاً تازه نیاز دارد. هر ادعای صادقانه‌ای که «رایانه‌های کوانتومی هم‌ریختی گراف را می‌شکنند» باید با همین مسئلهٔ باز سنجیده شود.