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

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

مدلی از نظریه

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

تعریف

تبدیل فوریه کوانتومی همان تبدیل فوریه گسسته کلاسیک است که به بردار دامنه‌های یک حالت کوانتومی اعمال شده‌است. تبدیل فوریه کلاسیک گسسته روی یک بردار در $\mathbb {C} ^{N}$ مانند (x₀, … , x_N−1) عمل می‌کند و طبق رابطهٔ زیر آن را به (y₀, … , y_N−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, ژوئن ۲۰۰۱)
• جان پرسکیل، Lecture Notes for Physics 229: Quantum Information and Computation (CIT, سپتامبر ۱۹۹۸)