تحويل فورييه الكمّي
Quantum Fourier Transform (QFT)
تحويل فورييه الكمّي هو تحويل فورييه المتقطع مطبَّقاً على سعات الحالة الكمّية، ويُنفَّذ بـ $O(n^2)$ بوابة على $n$ كيوبت؛ وهو إجراء فرعي أساسي في تقدير الطور وشور.
The QFT applies the discrete Fourier transform to the amplitudes of an n-qubit state with O(n²) gates; a key subroutine of phase estimation and Shor's algorithm.
المسألة
تطبيق تحويل فورييه المتقطع على متجه سعات حالة من $n$ كيوبت.
الفكرة الأساسية
ناتج التحويل لحالة أساس حالة منتجة، كل كيوبت فيها يحمل طوراً من كسر ثنائي لـ $x$؛ فيُبنى بهادامارد وبوابات طور متحكَّم بها.
المتطلبات
بوابات $H$ و$CP(\lambda)$ بزوايا دقيقة و SWAP؛ اتصال بين كل أزواج الكيوبتات أو بوابات SWAP إضافية للتوجيه.
الخطوات
- لكل كيوبت $j$ من الأعلى إلى الأدنى: طبّق $H$.
- ثم طبّق $CP(\pi/2^{j-k})$ متحكَّماً بها من كل كيوبت أدنى $k<j$.
- في النهاية بادِل الكيوبت $j$ مع $n-1-j$ لعكس الترتيب.
- للتحويل العكسي: اعكس ترتيب البوابات واقلب إشارات الزوايا.
تحويل فورييه الكمّي (Quantum Fourier Transform) هو النسخة الكمّية من تحويل فورييه المتقطع. على حالة أساس $|x\rangle$ لـ $n$ كيوبت ($N=2^n$):
$$\mathrm{QFT}\,|x\rangle=\frac{1}{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi i\,xy/N}|y\rangle.$$
وبالخطية يُطبَّق على أي تراكب، فيحوّل متجه السعات $(a_x)$ إلى تحويل فورييه المتقطع له.
الخاصية التي تجعل التنفيذ ممكناً هي أن الناتج حالة منتجة (Product State): كل كيوبت ناتج يحمل طوراً يعتمد على كسر ثنائي من $x$:
$$\mathrm{QFT}|x\rangle=\frac{1}{\sqrt N}\bigotimes_{l=1}^{n}\big(|0\rangle+e^{2\pi i\,x/2^{l}}|1\rangle\big).$$
لذلك تُبنى الدارة من بوابة هادامارد على كل كيوبت تليها بوابات طور متحكَّم بها $CP(\pi/2^{k})$ من الكيوبتات الأقل أهمية، ثم سلسلة SWAP لعكس ترتيب الكيوبتات. المجموع $n$ بوابة هادامارد و$n(n-1)/2$ بوابة $CP$ و$\lfloor n/2\rfloor$ بوابة SWAP، أي $O(n^2)$. يمكن حذف بوابات الطور ذات الزوايا الصغيرة جداً للحصول على «تحويل فورييه التقريبي» بعدد بوابات أقل وخطأ صغير يمكن التحكم فيه (Coppersmith 1994).
المختبر يطبّق التحويل على حالة أساس $|x\rangle$ ويعرض الحالة الناتجة: كل السعات متساوية المقدار $1/\sqrt N$، فالقياس يعطي توزيعاً منتظماً تماماً، والمعلومة كلها مخزنة في الأطوار $e^{2\pi i\,xy/N}$. هذا درس مهم: تحويل فورييه الكمّي لا «يحسب» تحويل فورييه بطريقة يمكن قراءتها؛ القياس لا يكشف إلا نتيجة عشوائية واحدة.
المقارنة الصادقة: كثيراً ما يُقال إن QFT أسرع أسياً من تحويل فورييه السريع (FFT) الذي يكلّف $O(N\log N)=O(n2^n)$. هذه المقارنة مضلّلة: FFT يعطي كل المعاملات الـ $N$ صريحة، أما QFT فيعمل على سعات لا يمكن استخراجها إلا بتكرار التحضير والقياس مرات كثيرة. فائدته تظهر فقط إجراءً فرعياً داخل خوارزمية تحتاج «نمطاً دورياً» في الأطوار، كتقدير الطور وإيجاد الرتبة في شور، حيث يُستعمل التحويل العكسي $\mathrm{QFT}^\dagger$.
تجربة مقترحة: غيّر $x$ مع إبقاء $n$ ثابتاً، ولاحظ أن الاحتمالات لا تتغير إطلاقاً بينما تتغير أطوار السعات خطياً مع $y$ بميل يتناسب مع $x$. ثم حضّر في مُنشئ الدارات تراكباً دورياً مثل $\frac{1}{\sqrt2}(|0\rangle+|4\rangle)$ على ثلاثة كيوبتات وطبّق التحويل: تتركز الاحتمالات على مضاعفات $N/r=8/4=2$، أي $y\in\{0,2,4,6\}$، وهذه هي الفكرة التي يستغلها شور لاستخراج الدور.
المحاكاة التفاعلية والنتائج
المقارنة بالحل الكلاسيكي
| كلاسيكياً | $O(n2^n)$ لـ FFT على متجه صريح |
|---|---|
| كمّياً | $O(n^2)$ بوابة (أقل مع التحويل التقريبي) |
FFT يحسب $N=2^n$ معاملاً صريحاً بـ $O(n2^n)$ عملية. QFT يستعمل $O(n^2)$ بوابة لكنه لا يُخرج المعاملات؛ القياس يعطي عينة واحدة. لذلك لا يصح القول إنه «أسرع من FFT» في الاستعمال العام؛ فائدته داخل خوارزميات مثل تقدير الطور وشور.
المخرجات لا تُقرأ إلا بالقياس (عينة واحدة لكل تشغيل). الزوايا الصغيرة جداً حساسة للأخطاء على العتاد. المختبر يعرض الحالة الكاملة لأنه محاكاة كلاسيكية تملك كل السعات، وهذا غير متاح على جهاز حقيقي.
شيفرة Qiskit
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: exact statevector (no sampling)
import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit.library import QFTGate
from qiskit.quantum_info import Statevector, Operator
def qft(qc, n):
"""Textbook QFT on qubits 0..n-1 (qubit 0 least significant), with final swaps."""
for j in reversed(range(n)):
qc.h(j)
for k in reversed(range(j)):
qc.cp(np.pi / 2 ** (j - k), k, j)
for j in range(n // 2):
qc.swap(j, n - 1 - j)
n, x = 3, 5
qc = QuantumCircuit(n)
for i in range(n):
if (x >> i) & 1:
qc.x(i) # prepare |x> = |101>
qft(qc, n)
sv = Statevector(qc)
expected = np.exp(2j * np.pi * x * np.arange(2 ** n) / 2 ** n) / np.sqrt(2 ** n)
print("amplitudes * sqrt(8):", np.round(sv.data * np.sqrt(2 ** n), 3))
print("matches e^{2 pi i x y / 2^n}/sqrt(2^n):", np.allclose(sv.data, expected))
print("probabilities:", np.round(sv.probabilities(), 4))
ref = QuantumCircuit(n); qft(ref, n)
print("equals qiskit QFTGate:", Operator(ref).equiv(Operator(QFTGate(n))))المخرجات الفعلية عند التشغيل
amplitudes * sqrt(8): [ 1. +0.j -0.707-0.707j 0. +1.j 0.707-0.707j -1. +0.j
0.707+0.707j -0. -1.j -0.707+0.707j]
matches e^{2 pi i x y / 2^n}/sqrt(2^n): True
probabilities: [0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125]
equals qiskit QFTGate: Trueتُشغَّل على جهازك بعد pip install qiskit qiskit-aer؛ لا تُنفَّذ داخل ووردبريس.
اختبر فهمك
يحتاج الاختبار إلى JavaScript.
موضوعات مرتبطة
المراجع
- Don Coppersmith (1994). An approximate Fourier transform useful in quantum factoring. IBM Research Report RC19642 (arXiv:quant-ph/0201067, 2002) doi:10.48550/arXiv.quant-ph/0201067
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667المرجع الأساسي للحوسبة الكمّية؛ سجل Crossref يذكر 2012 لنسخة Cambridge Core الإلكترونية.
- John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com
