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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در پردازش کوانتومی ٬ تبدیل فوریه کوانتومی یک نگاشت خطی روی کیوبیت‌ها است و مشابه کوانتومی تبدیل فوریه گسسته می‌باشد. تبدیل فوریه کوانتومی جزئی از بسیاری از الگوریتم‌های کوانتومی است ٬ و به خصوص در الگوریتم شر برای فاکتورگیری و محاسبه‌ی لگاریتم گسسته ٬ الگوریتم تخمین فاز کوانتومی برای تخمین ویژه‌مقدارهای یک عملگر یکانی و الگوریتم زیرگروه پنهان کاربرد دارد.

تبدیل فوریه کوانتومی با بازدهی (efficiency) بالایی بر روی یک رایانه کوانتومی قابل پیاده‌سازی است. تا به امروز ٬ بهترین الگوریتم‌های یافته شده برای تبدیل فوریه کوانتومی نیاز به O(n \log n) گیت برای دست‌یابی به یک تقریب کارا دارند.[۱]

تعریف[ویرایش]

تبدیل فوریه کوانتومی همان تبدیل فوریه گسسته کلاسیک است که به بردار دامنه‌های یک حالت کوانتومی اعمال شده‌است. تبدیل فوریه کلاسیک گسسته روی یک بردار در \mathbb{C}^N مانند (x0, ..., xN−1) عمل می کند و طبق رابطه‌ی زیر آن را به (y0, ..., yN−1) می‌برد:

y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}

که \omega = e^{\frac{2 \pi i}{N}} ریشه‌های واحد هستند.

به طور مشابه ٬تبدیل فوریه کوانتومی ٬ بر روی حالت کوانتومیِ \sum_{i=0}^{N-1} x_i |i\rangle عمل می‌کند و طبق رابطه‌ی زیر آن را به \sum_{i=0}^{N-1} y_i |i\rangle می‌برد:

y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}.

این رابطه را به صورت نگاشت زیر نیز می‌توان نشان داد:

|j\rangle \mapsto  \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega^{jk} |k\rangle.

به طور هم‌ارز ٬تبدیل فوریه کوانتومی ٬ را می‌توان به عنوان یک ماتریس یکانی که بر روی بردار حالت‌های کوانتومی عمل می‌کند نشان داد. این ماتریس ( F_N) چنین خواهد بود:


F_N = \frac{1}{\sqrt{N}} \begin{bmatrix}
1&1&1&1&\cdots &1 \\
1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\
1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\
\vdots&\vdots&\vdots&\vdots&&\vdots\\
1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)}
\end{bmatrix}.

ویژگی‌ها[ویرایش]

بیشتر خواص تبدیل فوریه کوانتومی از اینکه این تبدیل یک تبدیل یکانی (unitary transformation) است نتیجه می‌شوند. این مسئله را می‌توان با انجام ضرب ماتریسی FF^{\dagger}=F^{\dagger}F=I تحقیق کرد. به طور هم ارز می‌شود نشان داد که بردارهای با نرم ۱ به برداری با نرم ۱ نگاشته می‌شوند.

از ویژگی یکانی نتیجه می‌شود که معکوس تبدیل فوریه کوانتومی Hermitian adjoint ماتریس فوریه است ٬ یعنی F^{-1}=F^{\dagger}. از آنجایی که یک مدار کوانتومی efficient برای تبدیل فوریه کوانتومی قابل پیاده‌سازی است ٬ مدار می‌تواند به طور عکس برای انجام معکوس تبدیل فوریه کوانتومی به کار رود. هر دوی این تبدیل ها به طور efficient روی یک رایانه کوانتومی قابل پیاده‌سازی هستند.

پیاده‌سازی مداری[ویرایش]

مطالعه بیشتر[ویرایش]

  • K. R. Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
  • جان پرسکیل, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)

منابع[ویرایش]

  1. L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 515, November 12–14, 2000