25. الگوریتم گروور (Grover)

25.1جست‌وجوی بدون ساختار

مسئله: با گزارهٔ بولی P روی N = 2ⁿ آیتم که M آیتم آن را ارضا می‌کنند، یکی را پیدا کنید — با P فقط به‌صورت جعبه‌سیاه. واژهٔ کلیدی «بدون ساختار» است: نه ترتیبی، نه گرادیانی، نه همسایگی برای بهره‌برداری؛ تنها عملیات «آزمودن x» است. مدل درست برای وارونه‌کردن توابع هش، برای فضاهای جست‌وجویی که آزمودنشان ارزان اما ساختنشان ناممکن است، و به‌عنوان ستون بدبینانه‌ترین حالت برای مسائل ارضا محدودیت. آگاهانه بدبینانه‌ترین مدل جست‌وجوست — و همین به شتاب درجهٔ دو اعتبار می‌دهد: اگر این‌جا نتوان √N را شکست، هیچ هوشمندی فرض نشده بود.

25.2پیچیدگی کلاسیک

کلاسیکاً، آزمودن آیتم‌ها یکی‌یکی برای یافتن آیتم نشانه‌گذاری‌شده به‌طور متوسط N/2 پرس‌وجو می‌خواهد (بدترین حالت N) و هیچ الگوریتم کلاسیکی بهتر نمی‌شود — در جست‌وجوی بدون ساختار، ترفندهای از نوع روز تولد جواب نمی‌دهند چون پاسخ‌ها بیت‌های مستقل‌اند. گروور (Grover) در ۱۹۹۶ به Θ(√N) پرس‌وجوی کوانتومی رسید و بنت–برنشتاین–براسار–وازیرانی (Bennett–Bernstein–Brassard–Vazirani) در ۱۹۹۷ اثبات کرد که این بهینه است: هیچ الگوریتم کوانتومی ضریب درجهٔ دو را در جست‌وجوی جعبه‌سیاه شکست نمی‌دهد. دو نتیجه برای درونی‌کردن: شتاب درجهٔ دو است، هرگز نمایی — کلید ۱۲۸ بیتی زیر گروور مثل کلید ۶۴ بیتی زیر جست‌وجوی فراگیر کلاسیک می‌ماند — و مسئله‌های NP-کامل فقط همین بهبود درجهٔ دو را به ارث می‌برند (بخش هشتم).

25.3اورکل

جعبه‌سیاه به‌صورت اورکل فازی وارد می‌شود: O|x⟩ = (−1)^{P(x)}|x⟩ — علامت حالت‌های نشانه‌گذاری‌شده را وارونه کن، بقیه را رها کن. ساختنش از مدار کلاسیک P مکانیکی است: P(x) را در کیوبیت کمکی حساب و حسابِ معکوس کن، با کمکیِ آماده‌شده در |−⟩ تا CNOTها فاز پس بزنند (۲۱.۲). این ساخت به‌ازای هر فراخوانی اورکل یک بار اجرای مدار گزاره هزینه دارد — و این ثابت پنهان گروور است: برای گزارهٔ سخت (مثلاً یک نمونهٔ کامل SAT) اورکل به اندازهٔ کل مسئله است، یک بار به‌ازای هر تکرار، √N بار. قبل از باور هر ادعای «گروور X را حل می‌کند»، بودجه‌اش را ببندید.

25.4وارونگی فاز

اورکل یک بازتاب است. برای M = 1 همان O = I − 2|w⟩⟨w| است: به زبان هندسی، هر مؤلفهٔ دامنه در راستای |w⟩ علامت برمی‌گرداند و مکمل متعامد دست‌نخورده می‌ماند — آینه‌ای عمود بر حالت نشانه‌گذاری‌شده. برای M آیتم نشانه‌گذاری‌شده I − 2·Σ_w|w⟩⟨w| است. بازتاب‌ها یکانی‌اند و ترکیب‌شان دوران است — واقعیتی که کل الگوریتم روی آن می‌سورد. یک آزمون ذهنی مفید: اورکل به‌تنهایی هیچ چیز قابل اندازه‌گیری تغییر نمی‌دهد (عملی که فقط فاز می‌دهد، روی برهم‌نهی حقیقی فقط فاز عوض می‌کند) و دقیقاً برای همین پیش از هر خوانشی به یک عملیات دوم نیاز است.

25.5عملگر پخش

بازتاب دوم D = 2|s⟩⟨s| − I است که |s⟩ برهم‌نهی یکنواخت است — وارونگی حول میانگین (inversion about the mean): هر دامنهٔ aᵢ به 2μ − aᵢ می‌رود (μ = میانگین دامنه‌ها) و دامنه‌های زیرمیانگین (نشانه‌گذاری‌شده‌ها که تازه علامت برگشته‌اند) بالاتر از میانگین می‌نشینند. پیاده‌سازی: D = H^{⊗n}·(2|0⟩⟨0| − I)·H^{⊗n} و قطعهٔ میانی فلیپ فاز روی |0…0⟩ است که با گیت‌های X و یک Z چندکنترلی و ترفند کیوبیت کمکی ساخته می‌شود — O(n) گیت. یک تکرار گروور G = D·O است: بازتاب دربارهٔ مکمل متعامد |w⟩، بعد دربارهٔ |s⟩.

one iteration G = D·O:

|x> ──O───H^⊗n───●───H^⊗n──      O: flip sign of marked |w>
                 Z               middle: phase flip on |0…0>

25.6تقویت دامنه

گروور از شروع یکنواخت فراتر می‌رود: با هر آماده‌سازی A که A|0⟩ = |ψ⟩ با احتمال p روی حالت‌های خوب هم‌پوشانی √p دارد، عملگر Q = (2|ψ⟩⟨ψ| − I)·A·O·A† موفقیت را در O(1/√p) اعمال به ≈ 1 می‌رساند — در برابر O(1/p) تکرار کلاسیک. این تقویت دامنه (amplitude amplification) (براسار–هویر–موسکا–تپ) است و موفقیت هر الگوریتم احتمالاتی را به بهای درجهٔ دو بهبود می‌دهد: تخمین مونت‌کارلو به تخمین دامنه می‌شود (QPE روی Q، ۲۴.۷)، جست‌وجوی بازگشتی شتاب‌های پیاده‌روی‌محور می‌گیرد. وقتی M مجهول است، QPE روی G هم‌زمان شمارنده است — شمارش کوانتومی — و برنامه‌های تصادفی BBHT جای شمار تکرار ثابت را می‌گیرند. گروور اسم است؛ تقویت دامنه فناوری.

25.7تفسیر هندسی

همهٔ گفته‌ها در یک صفحه می‌گذرند. حالت را به مؤلفه روی زیرفضای نشانه‌گذاری‌شده و مؤلفه روی بقیه بنویسید: |ψ⟩ = sin(θ)|w⟩ + cos(θ)|r⟩ با sinθ = √(M/N). حالت یکنواخت آغازین با زاویه θ می‌نشیند؛ هر تکرار گروور دقیقاً 2θ به سمت |w⟩ می‌چرخاند؛ احتمال موفقیت پس از k تکرار sin²((2k+1)θ) است.

state plane spanned by |r> (unmarked) and |w> (marked):

start:   |s> = cosθ·|r> + sinθ·|w>          angle θ above |r>
each G:  rotate by 2θ toward |w>
after k: angle (2k+1)θ,  P(success) = sin²((2k+1)θ)
stop at k ≈ π/(4θ):  angle ≈ π/2  →  all amplitude on |w>

جست‌وجو به‌مثابه مسئلهٔ دوران: اورکل کج می‌کند، پخش می‌چرخاند و وقتی دوران دامنه را روی پاسخ برد، می‌ایستید. گذر از نقطهٔ بهینه به چرخیدن ادامه می‌دهد — بعد از π/2 احتمال موفقیت دوباره می‌افتد.

25.8شمار بهینهٔ تکرارها

(2k+1)θ ≈ π/2 بگذارید: بهینه k* ≈ π/(4θ) − 1/2 ≈ (π/4)·√(N/M) تکرار برای M ≪ N است. برای N = 16 و M = 1: θ = arcsin(1/4) ≈ 0.2527، پس k* ≈ 2.6 — سه تکرار sin²(7θ) ≈ ۹۶٪ می‌دهد. بعد از بهینه، سینوس به نوسان ادامه می‌دهد: ۴ تکرار به ≈ ۵۸٪ و ۵ تکرار به ≈ ۱۳٪ می‌افتد. دو واقعیت مرزی: اگر M = N/2 باشد، θ = π/4 و اصلاً شتابی نیست (یک تکرار، ۵۰٪ — می‌شد حدس زد)؛ و مقیاس‌بندی √(N/M) یعنی دانستن M مهم است، پس وقتی مجهول است اول بشمارید (۲۴.۷) یا از برنامه‌های تصادفی BBHT استفاده کنید. گروور مسئلهٔ دقیق زمان‌بندی است، نه بهبود تکراری.

import numpy as np
n, N = 4, 16
w = 0b1010                                   # آیتم نشانه‌گذاری‌شده
s = np.ones(N, dtype=complex) / np.sqrt(N)   # شروع یکنواخت
O = np.eye(N); O[w, w] = -1                  # اورکل: وارونگی فاز
D = 2 * np.outer(s, s) - np.eye(N)           # پخش: وارونگی حول میانگین
for k in range(6):
    print(f"k={k}  P(find)={abs(s[w])**2:.3f}")
    s = D @ O @ s

25.9حساسیت به نویز

قرارگیری در معرض نویز را بشمارید: یک تکرار هزینه‌اش اورکل به‌علاوهٔ O(n) گیت است؛ √N تکرار یعنی مجموعاً حدود 4n·√N اعمال گیت. با نرخ خطای فیزیکی p به‌ازای هر گیت، بودجهٔ خرابی 4n·√N·p باید خیلی زیر ۱ بماند. برای n = 20 (N ≈ 10⁶): 4·20·1024·10⁻³ ≈ ۸۲ — پنج مرتبه بزرگی بالاتر از بودجه در p = 10⁻³. شتاب درجهٔ دو دو بار ضربه می‌زند: تکرار بیشتر یعنی نویز انباشتهٔ بیشتر، و قلهٔ باریک sin² یعنی خطاهای زاویه (چرخش کمتر/بیشتر از گیت‌های ناقص) نقطهٔ بهینه را جابه‌جا می‌کند. برای همین گروور روی سخت‌افزار امروز نمایشی ۳ تا ۶ کیوبیتی است و نقطهٔ عبورِ تحمل خطا نقطهٔ عطف مهندسی واقعی است، نه تشریفات.

25.10پیاده‌سازی عملی

قواعد سرانگشتی از کسانی که اجرایش می‌کنند. اول، پیش از رسیدن به گروور از ساختار کلاسیک بهره بگیرید — حل‌کننده‌های SAT واقعی روی نمونه‌های واقعی از √(2ⁿ) بهترند؛ گروور ضمانت بدترین حالت است، نه برندهٔ حالت متوسط. دوم، وقتی اجرایش می‌کنید اورکل غالب است: مدار گزاره را با پخش هم‌طراحی کنید (حذف لایه‌های H مجاور، ادغام دوران‌ها، ۴۶.۸). سوم، قاب‌بندی‌های تقویت دامنه با p معلوم را ترجیح دهید — در الگوریتم‌های بزرگ‌تر ترکیب می‌شوند. چهارم، اگر M مجهول است اول بشمارید (۲۴.۷). پنجم، برای ترکیب‌پذیری از جست‌وجوی نقطهٔ ثابت (یودر–لو–چوانگ/Yoder–Low–Chuang) استفاده کنید که نمی‌تواند از بهینه بگذرد، به بهای یک ضریب ثابت متعارف. نمایش‌های سخت‌افزاری امروز: مشتی کیوبیت؛ به‌عنوان بنچمارک سامانه معنادار — نه به‌عنوان جست‌وجو.