خوارزمية تقدير الطور الكمومي

الحالة الابتدائية للنظام هي:

${\displaystyle |\Psi _{0}\rangle =|0\rangle ^{\otimes n}|\psi \rangle ,}$

أين${\displaystyle |\psi \rangle }$هو${\displaystyle m}$حالة الكيوبت التي تتطور من خلال${\displaystyle U}$نطبق أولاً عملية بوابة هادامارد ذات n كيوبت${\displaystyle H^{\otimes n}}$في السجل الأول، الذي ينتج الحالة:$${\displaystyle |\Psi _{1}\rangle =(H^{\otimes n}\otimes I_{m})|\Psi _{0}\rangle ={\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle .}$$لاحظ أننا هنا ننتقل بين النظام الثنائي و${\displaystyle n}$التمثيل -ary لـ${\displaystyle n}$- سجل الكيوبت: الكيت${\displaystyle |j\rangle }$على الجانب الأيمن يوجد اختصار لـ${\displaystyle n}$حالة الكيوبت${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$، أين${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$هو التحلل الثنائي لـ${\displaystyle j}$.

هذه الولاية${\displaystyle |\Psi _{1}\rangle }$ثم يتطور من خلال التطور الوحدوي المتحكم فيه${\displaystyle U_{C}}$الذي يمكن كتابة فعله على النحو التالي$${\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),}$$للجميع${\displaystyle k=0,...,2^{n}-1}$ويمكن كتابة هذا التطور بإيجاز على النحو التالي:$${\displaystyle U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},}$$مما يسلط الضوء على طبيعته الخاضعة للرقابة: فهو ينطبق${\displaystyle U^{k}}$إلى السجل الثاني بشرط أن يكون السجل الأول${\displaystyle |k\rangle }$مع الأخذ في الاعتبار شرط القيمة الذاتية الذي ينطبق على${\displaystyle |\psi \rangle }$تطبيق${\displaystyle U_{C}}$ل${\displaystyle |\Psi _{1}\rangle }$وهذا يعطي$${\displaystyle |\Psi _{2}\rangle \equiv U_{C}|\Psi _{1}\rangle =\left({\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle \right)\otimes |\psi \rangle ,}$$حيث استخدمنا${\displaystyle U^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$.

لإثبات ذلك${\displaystyle U_{C}}$ويمكن أيضًا تنفيذه بكفاءة، لاحظ أنه يمكننا كتابة${\displaystyle U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})}$، أين${\displaystyle C_{\ell }(U^{2^{\ell }})}$يشير إلى عملية التطبيق${\displaystyle U^{2^{\ell }}}$إلى السجل الثاني بشرط أن${\displaystyle \ell }$الكيوبت رقم - من السجل الأول هو${\displaystyle |1\rangle }$. رسميًا، يمكن وصف هذه البوابات من خلال عملها على النحو التالي:$${\displaystyle C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \rangle ).}$$يمكن تفسير هذه المعادلة على أنها تعني أن الحالة تبقى دون تغيير عندما${\displaystyle j_{\ell }=0}$أي عندما${\displaystyle \ell }$الكيوبت رقم - هو${\displaystyle |0\rangle }$بينما البوابة${\displaystyle U^{k}}$يتم تطبيق ذلك على السجل الثاني عندما${\displaystyle \ell }$الكيوبت رقم - هو${\displaystyle |1\rangle }$وبالتالي فإن تركيب هذه البوابات المتحكم بها يعطي$${\displaystyle \prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes \left(U^{\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}|\psi \rangle \right)=U_{C}\left(|j\rangle \otimes |\psi \rangle \right),}$$وتأتي الخطوة الأخيرة مباشرة بعد التفكيك الثنائي${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$.

من هذه النقطة فصاعدًا، يُترك السجل الثاني دون تغيير، وبالتالي يصبح من الملائم كتابة${\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle }$، مع${\displaystyle |{\tilde {\Psi }}_{2}\rangle }$حالة${\displaystyle n}$سجل الكيوبت، وهو السجل الوحيد الذي نحتاج إلى مراعاته لبقية الخوارزمية.

يتضمن الجزء الأخير من الدائرة تطبيق تحويل فورييه الكمي العكسي (QFT).${\displaystyle {\mathcal {QFT}}}$في السجل الأول لـ${\displaystyle |\Psi _{2}\rangle }$:$${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\tilde {\Psi }}_{2}\rangle .}$$تتميز نظرية الحقل الكمومي وعكسها بتأثيرهما على حالات الأساس كما يلي:$${\displaystyle {\begin{aligned}{\mathcal {QFT}}_{N}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{{\frac {2\pi i}{N}}jk}|j\rangle ,\\{\mathcal {QFT}}_{N}^{-1}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{-{\frac {2\pi i}{N}}jk}|j\rangle .\end{aligned}}}$$ويترتب على ذلك أن

${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .}$

تحليل الحالة في الأساس الحسابي على النحو التالي:${\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$وبالتالي فإن المعاملات تساوي$${\displaystyle c_{x}\equiv {\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}(x-2^{n}\theta )}={\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k},}$$حيث كتبنا${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$مع${\displaystyle a}$هو أقرب عدد صحيح إلى${\displaystyle 2^{n}\theta }$الفرق${\displaystyle 2^{n}\delta }$ يجب أن يفي بالتعريف${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$وهذا يعادل تقريبًا قيمة${\displaystyle \theta \in [0,1]}$عن طريق التقريب${\displaystyle 2^{n}\theta }$إلى أقرب عدد صحيح.

تتضمن الخطوة الأخيرة إجراء قياس في قاعدة البيانات الحسابية على السجل الأول. وهذا ينتج عنه النتيجة${\displaystyle |y\rangle }$باحتمال$${\displaystyle \Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.}$$ويترتب على ذلك أن${\displaystyle \operatorname {Pr} (a)=1}$لو${\displaystyle \delta =0}$أي عندما${\displaystyle \theta }$يمكن كتابتها على النحو التالي${\displaystyle \theta =a/2^{n}}$يجد المرء دائماً النتيجة${\displaystyle y=a}$من ناحية أخرى، إذا${\displaystyle \delta \neq 0}$، والاحتمالية هي$${\displaystyle \operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.}$$من هذا التعبير يمكننا أن نرى أن${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$متى${\displaystyle \delta \neq 0}$ولتوضيح ذلك، نلاحظ أنه من تعريف${\displaystyle \delta }$لدينا عدم المساواة${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$وبالتالي: ^{[ 4 ] : ​​157 [ 5 ] : 348}$${\displaystyle {\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |\\&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}}$$

نستنتج أن الخوارزمية توفر الأفضل${\displaystyle n}$تقدير بت واحد (أي، واحد ضمن${\displaystyle 1/2^{n}}$(من الإجابة الصحيحة) من${\displaystyle \theta }$باحتمالية لا تقل عن${\displaystyle 4/\pi ^{2}}$بإضافة عدد من الكيوبتات الإضافية من رتبة${\displaystyle O(\log(1/\epsilon ))}$وبحذف الكيوبتات الإضافية، يمكن أن تزداد الاحتمالية إلى${\displaystyle 1-\epsilon }$[ ^{5 ]​}