23. تبدیل فوریهٔ کوانتومی

23.1تبدیل فوریهٔ کلاسیک

تبدیل فوریه سیگنال را به فرکانس‌ها تجزیه می‌کند: با N نمونه، دامنه و فاز هر یک از N مؤلفهٔ دوره‌ای ممکن را گزارش می‌دهد. بعد از FFT کولی–توکی (Cooley–Tukey) در ۱۹۶۵، هزینه O(N log N) است — پرکاربردترین الگوریتم نرم‌افزار عددی، از کدک‌های صوتی تا حل PDE تا ضرب اعداد صحیح. خاصیتی که برای این بخش مهم است: دنباله‌ای با دورهٔ r، تبدیل فوریه‌اش نزدیک مضارب N/r متمرکز است. قله‌ها در فضای فرکانس، دوره‌ها را در داده آشکار می‌کنند. این فکر را نگه دارید؛ پل کامل به الگوریتم شور همین است.

23.2تبدیل فوریهٔ گسسته

به‌طور صوری، DFT بردار v به طول N برابر V_k = Σ_j v_j·e^{−2πi jk/N} است؛ معادلاً ضرب ماتریس‌دربردار V = F·v با F_{kj} = ω^{kj}، ω = e^{−2πi/N}. F را با 1/√N نرمال کنید تا یکانی شود — تغییری پایه میان پایهٔ «مکان» و پایهٔ «فرکانس». دو خاصیت به فضای کوانتومی می‌آیند: یکایی (تبدیل برگشت‌پذیر است) و قضیهٔ کانولوشن (ساختار دوره‌ای به پشتیبانی خلوت نگاشت می‌شود). خاصیتی که نمی‌آید: کلاسیکاً هر N خروجی را می‌خوانید؛ کوانتومیاً یک نمونه از دامنه‌های تبدیل‌شده می‌گیرید.

23.3تبدیل فوریهٔ کوانتومی

آن یکانی را روی حالت کوانتومی اعمال کنید: QFT_N|j⟩ = (1/√N)·Σ_{k=0}^{N−1} e^{2πi jk/N}|k⟩، با گسترش خطی به حالت‌های دلخواه — همان ماتریس DFT است که روی دامنه‌ها عمل می‌کند. روی حالت پایهٔ محاسباتی |j⟩ خروجی برهم‌نهی یکنواختی است که فازهایش j را کد می‌کنند؛ روی حالتی با دامنه‌های دوره‌ای، خروجی همان‌جا جمع می‌شود که DFT کلاسیک جمع می‌شد. هشدارها ریزنویسی کل فصل‌اند: ورودی باید از قبل خودِ حالت کوانتومی باشد (بارگذاری دادهٔ کلاسیک اغلب هزینهٔ واقعی است، ۵۰.۶) و خروجی باید نمونه‌برداری شود نه خوانده — یک اندازه‌گیری، نه جدولی از N عدد. QFT دقیقاً وقتی توانمند است که یک نمونه از توزیعی تیزقله می‌خواهید.

23.4تجزیهٔ مدار

هیچ ماتریس جعبه‌سیاه N×N اعمال نمی‌شود؛ QFT به O(n²) گیت یک‌و-دو-کیوبیتی تجزیه می‌شود. برای n = 3 (q0 = بیت پرارزش j):

H on q0; controlled-R2 between q0,q1; controlled-R3 between q0,q2;
H on q1; controlled-R2 between q1,q2; H on q2;  then SWAP(q0,q2)

q0: |j1> ──H────●────●────────────────
                │    │
q1: |j2> ───────R2───●────H────●──────
                     │         │
q2: |j3> ────────────R3────────R2──H──

گیت‌های controlled-Rk قطری‌اند (فقط شاخهٔ |11⟩ را فاز می‌دهند) پس برچسب کنترل/هدف‌شان قراردادی است. SWAPهای آخر ترتیب کیوبیت‌ها را وارونه می‌کنند — مدار به‌طور طبیعی خروجی با ترتیب بیت وارونه تولید می‌کند و پیاده‌سازی‌ها یا SWAP می‌گذارند یا بازنام‌گذاری را دنبال می‌کنند. برای n عمومی: به‌ازای هر کیوبیت، H و بعد دوران‌های کنترل‌شده از هر کیوبیت پایین‌تر.

23.5دوران‌های کنترل‌شده

ابزار کار Rk = diag(1, e^{2πi/2^k}) است — دوران فازی به اندازهٔ 2π/2^k، پس هر k بعدی زاویه را نصف می‌کند. میان H روی کیوبیت i و بعدی، کیوبیت i دوران‌های کنترل‌شدهٔ R2, R3, … را از همهٔ کیوبیت‌های مرتبهٔ پایین‌تر جمع می‌کند: فاز انباشته روی شاخهٔ |1⟩ می‌شود e^{2πi·0.jᵢjᵢ₊₁…} — کسر دودویی j از موقعیت i. شمار کل: n هادامارد، n(n+1)/2 دوران کنترل‌شده، ⌊n/2⌋ SWAP — O(n²) گیت که جز هاداماردها همه قطری‌اند. روی سخت‌افزار هر دوران کنترل‌شده یک برهم‌کنش دوکیوبیتی بومی است (یا دنباله‌ای تقریبی — سنتز روی Clifford+T به‌ازای هر دوران O(log(1/ε)) گیت T هزینه دارد) و همین است که مدارهای پر از QFT را به شمار دوران مقید می‌کند.

23.6QFT تقریبی

دوران‌هایی با k کوچک زاویه‌های ناچیز دارند — R20 کمتر از یک میلی‌رادیان می‌چرخاند. همهٔ controlled-Rk با k > m را حذف کنید: هر فاز حذف‌شده حداکثر 2π/2^{m+1} است و با حداکثر n² حذف، خطای فازی انباشتهٔ بدترین حالت حدود πn²/2^{m+1} است. انتخاب m ≈ log₂(n²/ε) خطا را به ε محدود می‌کند و شمار گیت را از O(n²) به O(n log n) می‌برد. روی سخت‌افزارِ تصحیح‌خطاشده دوران‌ها گیت T واقعی هزینه دارند، پس QFT تقریبی همان چیزی است که پیاده‌سازی‌های جدیِ شور/QPE واقعاً کامپایل می‌کنند. درس عمومی می‌شود: فازهای با دقت بالا نخستین جا برای خرج‌کردن بودجهٔ دقت‌اند — و نخستین جا برای پس‌گرفتنش.

23.7پیچیدگی

مقایسهٔ صادقانه. FFT کلاسیک: O(N log N) = O(n·2ⁿ) عملیات حسابی روی برداری از N = 2ⁿ عدد که از قبل در حافظه دارید. QFT کوانتومی: O(n²) گیت — نمایی کمتر از نظر گیت — اما روی حالتی که (الف) آماده‌کردنش کار دیگری می‌برد و (ب) یک نمونه می‌دهد، نه N ضریب. اگر تکلیفتان «تبدیل این آرایهٔ داده» باشد، FFT می‌برد، برای همیشه. اگر تکلیفتان «حالت کوانتومی با ساختار دوره‌ای دارم و می‌خواهم محتوای فرکانسی‌اش را نمونه‌برداری کنم»، QFT تقریباً مجانی است. هر ادعای شتاب QFT باید بگوید کدام سوی آن خط است — همان انضباط ۱.۹.

23.8کاربردها

چهار کاربرد، با عمق فزاینده. یافتن دوره: به سبک سایمون و به سبک شور — حالت دوره‌ای می‌رود، قله می‌آید (۲۶.۶). تخمین فاز: QFT وارونه، خوانش QPE و اسب‌بارکار شیمی و خودِ شور است (۲۴). حساب: جمع‌کنندهٔ Draper با انباشت فاز جمع می‌کند و چند خط لولهٔ جبر پیمانه‌ای بر ضرب مبتنی بر QFT استوارند. نمونه‌برداری فوریه به‌عنوان Primitive: هر مسئله‌ای با بوی زیرگروه پنهان از این‌جا شروع می‌شود. الگو را ببینید: QFT هرگز خودِ الگوریتم نیست؛ لایهٔ خوانشِ الگوریتمی است که کار واقعی‌اش در آماده‌سازی حالت و پس‌پردازش کلاسیک می‌گذرد.

import numpy as np
n, N = 3, 8
j = np.arange(N)
F = np.exp(2j * np.pi * np.outer(j, j) / N) / np.sqrt(N)   # ماتریس QFT
print("unitary:", np.allclose(F @ F.conj().T, np.eye(N)))  # True
v = np.array([1, 1, 0, 0, 0, 0, 0, 0], dtype=complex)      # |0> + |1>
print("matches np.fft.ifft * sqrt(N):",
      np.allclose(F @ v, np.sqrt(N) * np.fft.ifft(v)))     # True