Quantum Fourier transform

In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith.^[1] With small modifications to the QFT, it can also be used for performing fast integer arithmetic operations such as addition and multiplication.^[2][3][4]

The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices. The discrete Fourier transform on ${\displaystyle 2^{n}}$ amplitudes can be implemented as a quantum circuit consisting of only ${\displaystyle O(n^{2})}$Hadamard gates and controlledphase shift gates, where ${\displaystyle n}$ is the number of qubits.^[5] This can be compared with the classical discrete Fourier transform, which takes ${\displaystyle O(n2^{n})}$ gates (where ${\displaystyle n}$ is the number of bits), which is exponentially more than ${\displaystyle O(n^{2})}$.

The quantum Fourier transform acts on a quantum state vector (a quantum register), and the classical discrete Fourier transform acts on a vector. Both types of vectors can be written as lists of complex numbers. In the classical case, the vector can be represented with e.g. an array of floating-point numbers, and in the quantum case it is a sequence of probability amplitudes for all the possible outcomes upon measurement (the outcomes are the basis states, or eigenstates). Because measurement collapses the quantum state to a single basis state, not every task that uses the classical Fourier transform can take advantage of the quantum Fourier transform's exponential speedup.

The best quantum Fourier transform algorithms known (as of late 2000) require only ${\displaystyle O(n\log n)}$^{[ 6 ]} البوابات لتحقيق تقريب فعال، بشرط أن يتم تنفيذ بوابة الطور المتحكم بها كعملية أصلية.

التحويل الكمي لفورييه هو التحويل الكلاسيكي المنفصل لفورييه المطبق على متجه سعات الحالة الكمية، والذي له طول${\displaystyle N=2^{n}}$إذا تم تطبيقه على سجل${\displaystyle n}$الكيوبتات.

يعمل تحويل فورييه الكلاسيكي على متجه${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ويحولها إلى متجه ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$وفقًا للصيغة

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{N}^{-jk},\quad k=0,1,2,\ldots ,N-1,}$

أين${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$هو الجذر النوني للوحدة .

وبالمثل، فإن تحويل فورييه الكمي يؤثر على حالة كمية${\textstyle |x\rangle =\sum _{j=0}^{N-1}x_{j}|j\rangle }$ويحولها إلى حالة كمومية${\textstyle \sum _{j=0}^{N-1}y_{j}|j\rangle }$وفقًا للصيغة

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{N}^{jk},\quad k=0,1,2,\ldots ,N-1.}$

(تختلف اصطلاحات إشارة أس عامل الطور؛ هنا يكون لتحويل فورييه الكمي نفس تأثير تحويل فورييه المنفصل العكسي، والعكس صحيح.)

منذ${\displaystyle \omega _{N}^{l}}$إذا كان دورانًا، فإن تحويل فورييه الكمومي العكسي يعمل بشكل مشابه ولكن مع

${\displaystyle x_{j}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-jk},\quad j=0,1,2,\ldots ,N-1,}$

في حال${\displaystyle |x\rangle }$إذا كانت حالة أساسية، فيمكن أيضًا التعبير عن تحويل فورييه الكمي على أنه الخريطة

${\displaystyle \operatorname {QFT}$ :|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .}

بصورة مكافئة، يمكن اعتبار تحويل فورييه الكمومي بمثابة مصفوفة وحدوية (أو بوابة كمومية ) تعمل على متجهات الحالة الكمومية، حيث تكون المصفوفة الوحدوية${\displaystyle F_{N}}$هي مصفوفة DFT

${\displaystyle 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 &\ddots &\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}},}$

أين${\displaystyle \omega =\omega _{N}}$على سبيل المثال، في حالة${\displaystyle N=4=2^{2}}$والمرحلة${\displaystyle \omega =i}$مصفوفة التحويل هي

${\displaystyle F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}}$

البوابات الكمومية المستخدمة في الدائرة الكهربائية${\displaystyle n}$الكيوبتات هي بوابة هادامارد وبوابة الطور العقلاني الثنائي${\displaystyle R_{k}}$:

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{k}={\begin{pmatrix}1&0\\0&e^{i2\pi /2^{k}}\end{pmatrix}}}$

تتكون الدائرة من${\displaystyle H}$البوابات والنسخة الخاضعة للتحكم من${\displaystyle R_{k}}$:

أساس متعامد${\displaystyle S}$يتكون من حالات أساسية

${\displaystyle S=\{|0\rangle ,\ldots ,|2^{n}-1\rangle \}}$

تشمل هذه الحالات الأساسية جميع الحالات الممكنة للكيوبتات. بمعنى آخر، كل${\displaystyle |x\rangle \in S}$يكون:

${\displaystyle |x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle }$

حيث، باستخدام تدوين الضرب الموتري${\displaystyle \otimes }$،${\displaystyle |x_{j}\rangle }$يشير إلى أن الكيوبت${\displaystyle j}$هو في الولاية${\displaystyle x_{j}}$، مع${\displaystyle x_{j}}$إما 0 أو 1. اصطلاحًا، مؤشر حالة الأساس${\displaystyle x}$هو العدد الثنائي المشفر بواسطة${\displaystyle x_{j}}$، مع${\displaystyle x_{1}}$الجزء الأكثر أهمية.

آلية عمل بوابة هادامارد هي${\displaystyle H|x_{j}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{j}2^{-1}}|1\rangle \right)}$، حيث تعتمد الإشارة على${\displaystyle x_{j}}$.

يمكن كتابة تحويل فورييه الكمي على شكل حاصل ضرب موتر لسلسلة من الحدود:

${\displaystyle {\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).}$

باستخدام الترميز الثنائي الكسري

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k},}$

يمكن التعبير عن تأثير تحويل فورييه الكمي بطريقة مختصرة:

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right).}$

للحصول على هذه الحالة من الدائرة الموضحة أعلاه، يجب إجراء عملية تبديل للكيوبتات لعكس ترتيبها. على الأكثر${\displaystyle n/2}$يلزم إجراء عمليات تبديل. ^{[ 5 ]}

نظرًا لأن تحويل فورييه المنفصل، وهو عملية على n كيوبت، يمكن تحليله إلى حاصل ضرب موتر لـ n عملية على كيوبت واحد، فإنه يُمثل بسهولة كدائرة كمومية (حتى عكس ترتيب المخرج). يمكن تنفيذ كل عملية من عمليات الكيوبت الواحد هذه بكفاءة باستخدام بوابة هادامارد واحدة وعدد خطي من بوابات الطور المتحكم بها . يتطلب الحد الأول بوابة هادامارد واحدة و${\displaystyle (n-1)}$تتطلب البوابات ذات الطور المتحكم به، في الحد التالي، بوابة هادامارد واحدة و${\displaystyle (n-2)}$بوابة طور متحكم بها، وكل حد لاحق يتطلب بوابة طور متحكم بها أقل. بجمع عدد البوابات، باستثناء تلك اللازمة لعكس الإخراج، نحصل على${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})}$البوابات، وهي دالة تربيعية في عدد الكيوبتات. هذه القيمة أصغر بكثير من قيمة تحويل فورييه الكلاسيكي. ^{[ 7 ]}

تمت دراسة تنفيذ تحويل فورييه الكمومي على مستوى الدوائر في بنية الجوار الأقرب الخطية سابقًا. ^{[ 8 ] [ 9 ]} عمق الدائرة خطي بالنسبة لعدد الكيوبتات.

التحويل الكمي لفورييه على ثلاثة كيوبتات،${\displaystyle F_{8}}$مع${\displaystyle n=3,N=8=2^{3}}$، ويتم تمثيلها بالتحويل التالي:

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {8}}}\sum _{k=0}^{7}\omega ^{xk}|k\rangle ,}$

أين${\displaystyle \omega =\omega _{8}}$هو الجذر الثامن للوحدة الذي يحقق${\displaystyle \omega ^{8}=\left(e^{\frac {i2\pi }{8}}\right)^{8}=1}$.

التمثيل المصفوفي لتحويل فورييه على ثلاثة كيوبتات هو:

${\displaystyle F_{8}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.}$

يمكن إعادة كتابة تحويل فورييه الكمي لثلاثة كيوبتات على النحو التالي:

${\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {8}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right).}$

يوضح الرسم التخطيطي التالي الدائرة الكهربائية الخاصة بـ${\displaystyle n=3}$(مع عكس ترتيب الكيوبتات الناتجة بالنسبة إلى تحويل فورييه الكمومي الصحيح):

كما هو موضح أعلاه، فإن عدد البوابات المستخدمة هو${\displaystyle n(n+1)/2}$وهو ما يساوي${\displaystyle 6}$، ل${\displaystyle n=3}$.

باستخدام تحويل فورييه المعمم على الزمر المنتهية (الأبيلية) ، توجد في الواقع طريقتان طبيعيتان لتعريف تحويل فورييه الكمومي على سجل كمومي مكون من n كيوبت . يُكافئ تحويل فورييه الكمومي، كما هو مُعرّف أعلاه، تحويل فورييه المنفصل، الذي يعتبر هذه الكيوبتات n مُفهرسة بواسطة الزمرة الدورية.${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$ومع ذلك، من المنطقي أيضًا اعتبار الكيوبتات مفهرسة بواسطة المجموعة البوليانية .${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$وفي هذه الحالة، يكون تحويل فورييه هو تحويل هادامارد . ويتحقق ذلك بتطبيق بوابة هادامارد على كل كيوبت من الكيوبتات n بالتوازي. ^{[ 10 ] [ 11 ]} تستخدم خوارزمية شور كلا نوعي تحويل فورييه، تحويل هادامارد الأولي بالإضافة إلى تحويل فورييه الكمومي.

يمكن صياغة تحويل فورييه لمجموعات أخرى غير المجموعة الدورية ، وتوسيعه ليشمل الإطار الكمومي. ^{[ 12 ]} على سبيل المثال، لنأخذ المجموعة المتناظرة${\displaystyle S_{n}}$[ ^{13 ] [ 14 ]} يمكن التعبير عن تحويل فورييه في شكل ^مصفوفة

${\displaystyle {\mathfrak {F}}_{n}=\sum _{\lambda \in \Lambda _{n}}\sum _{p,q\in {\mathcal {P}}(\lambda )}\sum _{g\in S_{n}}{\sqrt {\frac {d_{\lambda }}{n!}}}[\lambda (g)]_{q,p}|\lambda ,p,q\rangle \langle g|,}$

أين${\displaystyle [\lambda (g)]_{q,p}}$هو${\displaystyle (q,p)}$عنصر من عناصر التمثيل المصفوفي لـ${\displaystyle \lambda (g)}$،${\displaystyle {\mathcal {P}}(\lambda )}$هي مجموعة المسارات من العقدة الجذرية إلى${\displaystyle \lambda }$في مخطط براتلي لـ${\displaystyle S_{n}}$،${\displaystyle \Lambda _{n}}$هي مجموعة تمثيلات${\displaystyle S_{n}}$مُفهرسة بواسطة مخططات يونغ ، و${\displaystyle g}$هو تبديل.

يمكن أيضًا صياغة تحويل فورييه المنفصل على حقل منتهٍ${\displaystyle F_{q}}$ويمكن تعريف نسخة كمومية. ^{[ 15 ]} لنفترض${\displaystyle N=q=p^{n}}$. يترك${\displaystyle \phi :GF(q)\to GF(p)}$لتكن دالة خطية اختيارية (الأثر، على سبيل المثال). عندئذٍ لكل${\displaystyle x\in GF(q)}$يُعرِّف

${\displaystyle F_{q,\phi }:|x\rangle \mapsto {\frac {1}{\sqrt {q}}}\sum _{y\in GF(q)}\omega ^{\phi (xy)}|y\rangle }$

ل${\displaystyle \omega =e^{2\pi i/p}}$وتوسيع${\displaystyle F_{q,\phi }}$بشكل خطي.

• بارثاساراثي، كيه آر (2006). محاضرات في الحوسبة الكمومية، ورموز تصحيح الأخطاء الكمومية، ونظرية المعلومات . معهد تاتا للأبحاث الأساسية. ISBN 978-81-7319-688-1.
• بريسكيل، جون (سبتمبر 1998). "ملاحظات المحاضرة لفيزياء 229: المعلومات الكمومية والحوسبة" (PDF) .

• مشروع توضيحي من وولفرام: دارة كمومية تُنفذ خوارزمية بحث جروفر
• مشروع وولفرام التجريبي: دارة كمومية تُنفذ تحويل فورييه الكمومي
• تحويل فورييه الكمي للحياة على الإنترنت