إجراء تقدير الطور

سنناقش الآن إجراء تقدير الطور، وهو خوارزمية كمومية لحل مسألة تقدير الطور.

سنبدأ بتمرين تسخيني بدقة منخفضة، يشرح بعض الحدس الأساسي وراء هذه الطريقة. ثم سنتحدث عن تحويل فورييه الكمومي، وهو عملية كمومية مهمة تُستخدم في إجراء تقدير الطور، إلى جانب تطبيقه على الدوائر الكمومية. بعد أن نفهم تحويل فورييه الكمومي، سنشرح إجراء تقدير الطور بشكل كامل ونحلل أداءه.

تمرين تسخيني: تقريب الأطوار بدقة منخفضة

سنبدأ بنسختين بسيطتين من إجراء تقدير الطور اللتين تقدمان حلولاً بدقة منخفضة لمسألة تقدير الطور. هذا مفيد لشرح الحدس وراء الإجراء العام الذي سنراه لاحقاً في الدرس.

باستخدام الركلة الطورية

نهج بسيط لمسألة تقدير الطور يتيح لنا تعلم شيء عن قيمة $\theta$ المطلوبة، يعتمد على ظاهرة الركلة الطورية. كما سنرى، هذه في الأساس نسخة أحادية الكيوبت من إجراء تقدير الطور العام الذي سنناقشه لاحقاً في الدرس.

كجزء من مدخلات مسألة تقدير الطور، لدينا دائرة كمومية أحادية للعملية $U$. يمكننا استخدام وصف هذه الدائرة لإنشاء دائرة لعملية $U$ المتحكم بها، والتي يمكن تصويرها كما يوحي هذا الشكل (مع العملية $U$ بوصفها بوابة كمومية على اليسار وعملية $U$ المتحكم بها على اليمين).

يمكننا إنشاء دائرة كمومية لعملية $U$ المتحكم بها بإضافة كيوبت تحكم إلى دائرة $U$ أولاً، ثم استبدال كل بوابة في دائرة $U$ بنسخة متحكم بها من تلك البوابة — بحيث يتحكم كيوبت التحكم الجديد الواحد فعلياً في كل بوابة في دائرة $U$. هذا يتطلب أن يكون لدينا نسخة متحكم بها من كل بوابة في دائرتنا، لكن يمكننا دائماً بناء دوائر لهذه العمليات المتحكم بها في حال لم تكن مدرجة في مجموعة بواباتنا.

الآن نعتبر الدائرة التالية، حيث الحالة المدخلة $\vert\psi\rangle$ لجميع الكيوبتات ماعدا العلوية هي متجه الحالة الذاتية الكمومي لـ $U$.

احتمالات نتائج القياس لهذه الدائرة تعتمد على القيمة الذاتية لـ $U$ المقابلة لمتجه الحالة الذاتية $\vert\psi\rangle$. سنحلل الدائرة بالتفصيل لنحدد بالضبط كيف يتم ذلك.

الحالة الابتدائية للدائرة هي

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

وبوابة هادامار الأولى تحول هذه الحالة إلى

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

بعد ذلك، تُنفَّذ عملية $U$ المتحكم بها، مما ينتج عنه الحالة

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

باستخدام افتراض أن $\vert\psi\rangle$ متجه حالة ذاتية لـ $U$ له القيمة الذاتية $\lambda = e^{2\pi i\theta}$, يمكننا التعبير عن هذه الحالة بشكل بديل كالتالي.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

هنا نلاحظ ظاهرة الركلة الطورية. هي مختلفة قليلاً هذه المرة عما كانت عليه في خوارزمية دويتش وخوارزمية دويتش-جوزسا لأننا لا نعمل مع بوابة استعلام — لكن الفكرة متشابهة.

أخيراً، تُنفَّذ بوابة هادامار الثانية. بعد تبسيط بسيط، نحصل على هذا التعبير لهذه الحالة.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

القياس بالتالي يعطي النتيجتين $0$ و $1$ بهذه الاحتمالات:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

إليك رسمًا بيانيًا لاحتمالات النتيجتين الممكنتين، $0$ و$1$، كدوال لـ$\theta$.

بشكل طبيعي، يجمع الاحتمالان دائمًا إلى $1$. لاحظ أنه عندما تكون $\theta = 0$، تكون نتيجة القياس دائمًا $0$، وعندما تكون $\theta = 1/2$، تكون نتيجة القياس دائمًا $1$. إذن، رغم أن نتيجة القياس لا تكشف بالضبط ما هي $\theta$، إلا أنها تزودنا ببعض المعلومات عنها - وإذا كنا نعلم مسبقًا أن $\theta = 0$ أو $\theta = 1/2$، يمكننا معرفة أيهما صحيح من الدائرة دون خطأ.

بصورة بديهية، يمكننا التفكير في نتيجة قياس الدائرة كتخمين لـ$\theta$ بدقة "بت واحد". بعبارة أخرى، لو كتبنا $\theta$ بالترميز الثنائي وقربناها إلى بت واحد، لحصلنا على رقم مثل هذا:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

يمكن اعتبار نتيجة القياس تخمينًا للبت $a$. عندما لا تكون $\theta$ لا $0$ ولا $1/2$، يوجد احتمال غير صفري بأن يكون التخمين خاطئًا - لكن احتمال ارتكاب خطأ يصبح أصغر فأصغر كلما اقتربنا من $0$ أو $1/2$.

من الطبيعي أن نسأل عن الدور الذي تلعبه بوابتا هادامارد في هذا الإجراء:

• بوابة هادامار الأولى تضع كيوبت التحكم في تراكب متساوٍ من $\vert 0\rangle$ و $\vert 1\rangle$, بحيث حين تحدث الركلة الطورية، تحدث لحالة $\vert 1\rangle$ دون حالة $\vert 0\rangle$, مما يخلق فارقاً طورياً نسبياً يؤثر على نتائج القياس. لو لم نفعل ذلك وأنتجت الركلة الطورية طوراً كلياً، لما كان لها أي تأثير على احتمالات الحصول على نتائج قياس مختلفة.

• بوابة هادامار الثانية تتيح لنا تعلم شيء عن العدد $\theta$ من خلال ظاهرة التداخل. قبل بوابة هادامار الثانية، حالة الكيوبت العلوي هي

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  وإذا قسنا هذه الحالة، سنحصل على $0$ و$1$ كل منهما باحتمال $1/2$, مما لا يخبرنا شيئًا عن $\theta$. لكن عند تطبيق بوابة هادامار الثانية، نجعل العدد $\theta$ يؤثر على احتمالات المخرجات.

مضاعفة الطور

الدائرة أعلاه تستخدم ظاهرة ركل الطور لتقريب $\theta$ بدقة بت واحد. قد يكفينا بت واحد في بعض الحالات — لكن للتحليل إلى عوامل سنحتاج إلى دقة أكبر بكثير. سؤال طبيعي هنا: كيف يمكننا معرفة المزيد عن $\theta?$

شيء بسيط جدًا يمكننا فعله هو استبدال عملية controlled-$U$ في دائرتنا بـنسختين من هذه العملية، كما في هذه الدائرة:

نسختان من عملية controlled-$U$ تعادل عملية controlled-$U^2$ واحدة. إذا كان $\vert\psi\rangle$ متجهًا ذاتيًا لـ$U$ بقيمة ذاتية $\lambda = e^{2\pi i \theta}$, فهذه الحالة أيضًا متجه ذاتي لـ$U^2$, لكن هذه المرة بقيمة ذاتية $\lambda^2 = e^{2\pi i (2\theta)}$.

إذن، إذا شغّلنا هذا الإصدار من الدائرة، نحن في الواقع نجري نفس الحساب السابق، إلا أن العدد $\theta$ يُستبدل بـ$2\theta$. إليك رسمًا بيانيًا يوضح احتمالات المخرجات بينما يتراوح $\theta$ من $0$ إلى $1$.

فعل هذا يمكن أن يمدنا ببعض المعلومات الإضافية عن $\theta$. إذا كان التمثيل الثنائي لـ$\theta$ هو

$$\theta = 0.a_1 a_2 a_3\cdots$$

فإن مضاعفة $\theta$ تزيح النقطة الثنائية موضعًا واحدًا إلى اليمين:

$$2\theta = a_1. a_2 a_3\cdots$$

وبما أننا نساوي $\theta = 1$ مع $\theta = 0$ بينما ندور حول دائرة الوحدة، نرى أن البت $a_1$ لا تأثير له على احتمالاتنا، وأننا نحصل فعليًا على تخمين للـبت الثاني بعد النقطة الثنائية إذا قرّبنا $\theta$ إلى بتين. مثلًا، لو علمنا مسبقًا أن $\theta$ إما $0$ أو $1/4$, يمكننا حينئذٍ الوثوق الكامل بنتيجة القياس لمعرفة أيّهما.

لكن ليس واضحًا مباشرةً كيف يُوفَّق هذا التقدير مع ما تعلمناه من دائرة ركل الطور الأصلية (غير المضاعفة) لنحصل على أدق معلومة ممكنة عن $\theta$. لذا دعنا نتراجع خطوة ونفكر في كيفية المضي قدمًا.

تقدير الطور بكيوبتين

بدلًا من النظر في الخيارين الموصوفين أعلاه بشكل منفصل، دعنا ندمجهما في دائرة واحدة كالتالي.

بوابات هادامار بعد العمليات الخاضعة للتحكم أُزيلت ولا توجد قياسات هنا بعد. سنضيف المزيد إلى الدائرة بينما نفكر في خياراتنا لتعلم أكبر قدر ممكن عن $\theta$.

إذا شغّلنا هذه الدائرة حين يكون $\vert\psi\rangle$ متجهًا ذاتيًا لـ$U$, ستظل حالة الكيوبتات السفلية $\vert\psi\rangle$ طوال الدائرة بأكملها، وستُركل الأطوار إلى حالة الكيوبتات العلويتين. دعنا نحلّل الدائرة بدقة عبر الشكل التالي.

يمكننا كتابة الحالة $\vert\pi_1\rangle$ كالتالي:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

عند تطبيق عملية controlled-$U$ الأولى، تُركل القيمة الذاتية $\lambda = e^{2\pi i\theta}$ إلى الطور حين يكون $a_0$ (الكيوبت العلوي) يساوي $1$, لكن لا شيء يحدث حين يكون $0$. إذن يمكننا التعبير عن الحالة الناتجة كالتالي:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

البوابتان controlled-$U$ الثانية والثالثة تفعلان شيئًا مشابهًا، إلا أنهما تخصّان $a_1$ بدلًا من $a_0$, ومع استبدال $\theta$ بـ$2\theta$. يمكننا التعبير عن الحالة الناتجة كالتالي:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

إذا اعتبرنا السلسلة الثنائية $a_1 a_0$ ممثِّلةً لعدد صحيح $x \in \{0,1,2,3\}$ بالنظام الثنائي، أي $x = 2 a_1 + a_0$, يمكننا بديلًا عن ذلك التعبير عن هذه الحالة كالتالي.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

هدفنا هو استخلاص أكبر قدر ممكن من المعلومات عن $\theta$ من هذه الحالة.

في هذه المرحلة سننظر في حالة خاصة، حيث يُعدنا بأن $\theta = \frac{y}{4}$ لعدد صحيح $y\in\{0,1,2,3\}.$ بعبارة أخرى، لدينا $\theta\in \{0, 1/4, 1/2, 3/4\},$ إذن يمكننا تمثيل هذا العدد تمامًا بالنظام الثنائي باستخدام بتين، كـ.$00,$ .$01,$ .$10,$ أو .$11.$ بشكل عام، قد لا يكون $\theta$ إحدى هذه القيم الأربع، لكن التفكير في هذه الحالة الخاصة سيساعدنا على معرفة كيفية استخلاص المعلومات عن $\theta$ بصورة عامة على أفضل وجه.

أولًا سنعرّف متجه حالة لكيوبتين لكل قيمة محتملة $y \in \{0, 1, 2, 3\}$.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

بعد تبسيط الأسّيات، يمكننا كتابة هذه المتجهات كالتالي.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

هذه المتجهات متعامدة: إذا اخترنا أي زوج منها وحسبنا حاصل ضربهما الداخلي، نحصل على $0$. كل منها أيضًا متجه وحدة، إذن $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ أساس متعامد معياري. لذا نعرف فورًا أن ثمة قياسًا يمكنه تمييزها تمييزًا مثاليًا — أي أنك لو أُعطيت واحدًا منها دون أن تعرف أيّها، يمكنك معرفة أيّها بلا خطأ.

لإجراء هذا التمييز بدائرة كمومية، يمكننا أولًا تعريف عملية أحادية $V$ تحوّل حالات الأساس الاعتيادي إلى الحالات الأربع المذكورة أعلاه.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

لكتابة $V$ كمصفوفة $4\times 4$, الأمر لا يعدو جعل أعمدة $V$ هي الحالات $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$.

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

هذه مصفوفة خاصة، ومن المحتمل أن يكون بعض القراء قد صادفوها من قبل: إنها المصفوفة المرتبطة بـتحويل فورييه المنفصل ذي الأربعة أبعاد. في ضوء هذه الحقيقة، لنسمّيها $\mathrm{QFT}_4$ بدلًا من $V$. الاسم $\mathrm{QFT}$ اختصار لـتحويل فورييه الكمومي - وهو في الأساس مجرد تحويل فورييه المنفصل، يُنظر إليه كعملية يونيتارية. سنناقش تحويل فورييه الكمومي بمزيد من التفصيل والعمومية قريبًا.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

يمكننا إجراء معكوس هذه العملية للانتقال في الاتجاه الآخر، لتحويل الحالات $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ إلى حالات الأساس القياسي $\vert 0\rangle,\ldots,\vert 3\rangle$. إذا فعلنا هذا، فيمكننا القياس لمعرفة أي قيمة $y\in\{0,1,2,3\}$ تصف $\theta$ بحيث $\theta = y/4$. إليك رسمًا تخطيطيًا لدائرة كمومية تفعل ذلك.

باختصار، إذا شغّلنا هذه الدائرة عندما $\theta = y/4$ لـ$y\in\{0,1,2,3\}$، فإن الحالة مباشرةً قبل إجراء القياسات ستكون $\vert \psi\rangle \vert y\rangle$ (بالنسبة لـ$y$ المشفّرة كسلسلة ثنائية من بتين)، لذا فإن القياسات ستكشف القيمة $y$ دون خطأ.

هذه الدائرة مستوحاة من الحالة الخاصة حيث $\theta \in \{0,1/4,1/2,3/4\}$ — لكن يمكننا تشغيلها لأي اختيار لـ$U$ و$\vert \psi\rangle$، وبالتالي أي قيمة لـ$\theta$، كما نشاء. إليك رسمًا بيانيًا لاحتمالات المخرجات التي تنتجها الدائرة لاختيارات اعتباطية لـ$\theta$.

هذا تحسّن واضح مقارنةً بالنسخة أحادية الـQubit الموصوفة سابقًا في الدرس. إنه ليس مثاليًا - فقد يعطينا الإجابة الخاطئة - لكن الإجابة تميل بشدة نحو قيم $y$ التي تكون فيها $y/4$ قريبة من $\theta$. على وجه الخصوص، تقابل النتيجة الأكثر احتمالًا دائمًا أقرب قيمة لـ$y/4$ إلى $\theta$ (مع مساواة $\theta = 0$ و$\theta = 1$ كما سبق)، ومن الرسم البياني يبدو أن هذه القيمة الأقرب لـ$x$ تظهر دائمًا باحتمال يزيد قليلًا عن $40\%$. عندما تكون $\theta$ بالضبط منتصف الطريق بين قيمتين من هذا النوع، مثل $\theta = 0.375$ على سبيل المثال، تكون القيمتان المتساويتان في القرب لـ$y$ متساويتين في الاحتمال.

التحضير للتعميم على كيوبتات كثيرة

بالنظر إلى التحسّن الذي حقّقناه للتو باستخدام كيوبتَي تحكّم بدلًا من واحدة، مقرونًا بمعكوس تحويل فورييه الكمومي ذي البُعد $4$، من الطبيعي أن نفكّر في تعميم الأمر أكثر — بإضافة كيوبتات تحكّم إضافية. حين نفعل ذلك، نحصل على إجراء تقدير الطور العام. سنرى كيف يعمل هذا قريبًا، لكن لوصفه بدقة، سنحتاج إلى مناقشة تحويل فورييه الكمومي بصورة أعمّ، لنرى كيف يُعرَّف للأبعاد الأخرى وكيف يمكننا تطبيقه (أو معكوسه) بدائرة كمومية.

تحويل فورييه الكمومي

تحويل فورييه الكمومي هو عملية أحادية يمكن تعريفها لأي بُعد $N$ صحيح موجب. في هذا القسم، سنرى كيف تُعرَّف هذه العملية وكيف يمكن تطبيقها بدائرة كمومية على $m$ كيوبت بتكلفة $O(m^2)$ حين $N = 2^m$.

المصفوفات التي تصف تحويل فورييه الكمومي مشتقّة من عملية مشابهة على متجهات ذات بُعد $N$ تُعرف بـ تحويل فورييه المنفصل. يمكن التفكير في هذه العملية بطرق مختلفة. مثلًا، يمكننا التفكير فيها بمصطلحات رياضية مجردة بحتة باعتبارها تعيينًا خطيًّا. أو يمكننا التفكير فيها بمصطلحات حسابية، حيث يُعطى لنا متجه ذو بُعد $N$ من الأعداد المركّبة (باستخدام الترميز الثنائي لتشفير الأجزاء الحقيقية والتخيّلية للمدخلات، لنفترض ذلك)، والهدف هو حساب المتجه ذي البُعد $N$ الناتج عن تطبيق تحويل فورييه المنفصل. تركيزنا سيكون على طريقة ثالثة، وهي النظر إلى هذا التحويل بوصفه عملية أحادية يمكن تطبيقها على نظام كمومي.

ثمة خوارزمية فعّالة لحساب تحويل فورييه المنفصل على متجه إدخال معطى تُعرف بـ تحويل فورييه السريع. لها تطبيقات في معالجة الإشارات وكثير من المجالات الأخرى، ويعدّها كثيرون من أهمّ الخوارزميات التي اكتُشفت على الإطلاق. واتّضح أن تطبيق تحويل فورييه الكمومي حين $N$ هو قوة للعدد 2 الذي سندرسه، مبنيٌّ على نفس البنية الأساسية التي تجعل تحويل فورييه السريع ممكنًا.

تعريف تحويل فورييه الكمومي

لتعريف تحويل فورييه الكمومي، سنعرّف أولًا عددًا مركبًا $\omega_N$، لكل عدد صحيح موجب $N$، على هذا النحو:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

هذا هو العدد على دائرة الوحدة المركبة الذي نحصل عليه إذا بدأنا عند $1$ وتحركنا عكس اتجاه عقارب الساعة بزاوية $2\pi/N$ راديان، أو جزء $1/N$ من محيط الدائرة. إليك بضعة أمثلة:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

الآن يمكننا تعريف تحويل فورييه الكمومي ذي الـ$N$ بعد، والذي يوصف بمصفوفة $N\times N$ صفوفها وأعمدتها مرتبطة بحالات الأساس القياسي $\vert 0\rangle,\ldots,\vert N-1\rangle$. سنحتاج فقط إلى هذه العملية عندما تكون $N = 2^m$ قوة من قوى $2$ من أجل تقدير الطور، لكن يمكن تعريف العملية لأي عدد صحيح موجب $N$.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

كما ذُكر سابقًا، هذه هي المصفوفة المرتبطة بـتحويل فورييه المنفصل ذي الـ$N$ بعد. غالبًا ما لا يُدرَج العامل الأمامي $1/\sqrt{N}$ في تعريف هذه المصفوفة، لكننا نحتاج إلى تضمينه للحصول على مصفوفة أحادية.

إليك تحويل فورييه الكمومي، مكتوبًا كمصفوفة، لبعض القيم الصغيرة لـ$N$.

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

لاحظ بالذات أن $\mathrm{QFT}_2$ هو اسم آخر لعملية هادامار.

الأحادية

دعونا نتحقق أن $\mathrm{QFT}_N$ أحادي، لأي اختيار لـ $N$. طريقة واحدة للقيام بذلك هي إثبات أن أعمدته تشكّل أساسًا متعامدًا منظّمًا. يمكننا تعريف متجه يقابل العمود رقم $y$, بدءًا من $y = 0$ وصولًا إلى $y = N-1$, هكذا:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

إذا أخذنا الضرب الداخلي بين أي متجهين من هذه المتجهات نحصل على هذا التعبير:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

يمكننا حساب مجاميع من هذا النوع باستخدام الصيغة التالية لمجموع أول $N$ حد من متسلسلة هندسية.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

تحديدًا، يمكننا استخدام هذه الصيغة حين $\alpha = \omega_N^{y-z}$. حين $y = z$, لدينا $\alpha = 1$, فباستخدام الصيغة والقسمة على $N$ نحصل على

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

حين $y\neq z$, لدينا $\alpha \neq 1$, فالصيغة تكشف لنا ما يلي:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

هذا يحدث لأن $\omega_N^N = e^{2\pi i} = 1$, فـ $\omega_N^{N(y-z)} = 1^{y-z} = 1$, مما يجعل البسط صفرًا، بينما المقام غير صفري لأن $\omega_N^{y-z} \neq 1$. بشكل بديهي، ما نفعله هو جمع مجموعة من النقاط المتوزعة حول دائرة الوحدة، وهي تتلاشى وتعطي $0$ عند جمعها.

بذلك أثبتنا أن $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ مجموعة متعامدة منظّمة،

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

وهذا يكشف أن $\mathrm{QFT}_N$ أحادي.

بوابات الطور المتحكَّم بها

لتطبيق تحويل فورييه الكمومي بدائرة كمومية، سنحتاج إلى الاستعانة بـ بوابات الطور المتحكَّم بها. تذكّر أن عملية الطور هي عملية أحادية وأحادية الكيوبت على الشكل

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

لأي عدد حقيقي $\alpha$. النسخة المتحكَّم بها من هذه البوابة لها المصفوفة التالية:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

بالنسبة لهذه البوابة المتحكَّم بها، لا يهم في الواقع أي الكيوبتين هو المتحكِّم وأيهما الهدف لأن الاحتمالين متكافئان. يمكننا استخدام أي من الرموز التالية لتمثيل هذه البوابة في مخططات الدوائر الكمومية.

بالنسبة للشكل الثالث، العلامة $\alpha$ تُوضع أحيانًا على جانب خط التحكم أو أسفل المتحكِّم السفلي حين يكون ذلك مناسبًا.

لتنفيذ تحويل فورييه الكمومي حين $N = 2^m$ و $m\geq 2$, سنحتاج إلى تنفيذ عملية على $m$ كيوبت يمكن وصف تأثيرها على حالات الأساس القياسية هكذا:

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

حيث $a$ بت واحد و $y \in \{0,\ldots,2^{m-1} - 1\}$ عدد مُرمَّز بالتدوين الثنائي كسلسلة من $m-1$ بت. يمكن إنجاز ذلك باستخدام بوابات الطور المتحكَّم بها عن طريق تعميم المثال التالي، الذي فيه $m=5$.

بشكل عام، لأي اختيار اعتباطي لـ $m\geq 2$, الكيوبت العلوي المقابل للبت $a$ يمكن اعتباره المتحكِّم، مع بوابات الطور $P_{\alpha}$ التي تتراوح من $\alpha = \pi/2^{m-1}$ على الكيوبت المقابل للبت الأقل أهمية في $y$ إلى $\alpha = \frac{\pi}{2}$ على الكيوبت المقابل للبت الأكثر أهمية في $y$. بوابات الطور المتحكَّم بها هذه كلها تبادلية فيما بينها ويمكن تنفيذها بأي ترتيب.

تطبيق الدائرة لتحويل QFT

الآن سنرى كيف يمكننا تطبيق تحويل فورييه الكمومي بدائرة حين يكون البُعد $N = 2^m$ قوةً للعدد $2$. في الواقع، هناك طرق متعددة لتطبيق تحويل فورييه الكمومي، لكن هذه تُعدّ أبسط طريقة معروفة. بمجرد أن نعرف كيف نطبّق تحويل فورييه الكمومي بدائرة كمومية، يصبح تطبيق معكوسه أمرًا مباشرًا: نستطيع استبدال كل بوابة بمعكوسها (أو بعبارة أخرى، المزدوج المترافق) وتطبيق البوابات بالترتيب المعكوس. كل دائرة كمومية مكوّنة من بوابات أحادية فقط يمكن عكسها بهذه الطريقة.

التطبيق ذو طبيعة تكرارية، لذا هذه هي الطريقة الأكثر طبيعية لوصفه. الحالة الأساسية هي $m=1$, وفي هذه الحالة تحويل فورييه الكمومي هو عملية هادامار.

لتنفيذ تحويل فورييه الكمومي على $m$ كيوبت حين $m \geq 2$, يمكننا تنفيذ الخطوات التالية، التي سنصف تأثيرها على حالات الأساس القياسية من الشكل $\vert x \rangle \vert a\rangle$, حيث $x\in\{0,\ldots,2^{m-1} - 1\}$ عدد صحيح مُرمَّز بـ $m-1$ بت باستخدام التدوين الثنائي و $a$ بت واحد.

1. أولًا طبّق تحويل فورييه الكمومي بأبعاد $2^{m-1}$ على آخر $m-1$ كيوبت (اليسار/الأسفل) للحصول على هذه الحالة:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   يتم هذا عن طريق تطبيق الطريقة المذكورة بشكل تكراري على كيوبت واحد أقل، مع استخدام عملية هادامار على كيوبت واحد كحالة أساسية.

2. استخدم الكيوبت الأعلى/الأيمن كـ control لحقن الطور $\omega_{2^m}^y$ لكل حالة من حالات الأساس القياسي $\vert y\rangle$ للكيوبتات الـ $m-1$ الباقية (كما هو موضح أعلاه) للحصول على هذه الحالة:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. نفّذ بوابة هادامار على الكيوبت الأعلى/الأيمن للحصول على هذه الحالة:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. أعد ترتيب الكيوبتات بحيث يصبح البت الأقل أهمية هو البت الأكثر أهمية، مع إزاحة الباقي للأعلى/اليمين:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

مثلاً، هذه هي الدائرة التي نحصل عليها لـ $N = 32 = 2^5$. في هذا الرسم، أُعطيت الكيوبتات أسماء تتوافق مع متجهات الأساس القياسي $\vert x\rangle \vert a\rangle$ (للمدخل) و $\vert b\rangle \vert y\rangle$ (للمخرج) من أجل الوضوح.

التحليل

الصيغة الأساسية التي نحتاجها للتحقق من أن الدائرة الموصوفة للتو تُنفذ تحويل فورييه الكمومي ذي الـ$2^m$ بعد هي هذه:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

تعمل هذه الصيغة مع أي اختيار للأعداد الصحيحة $a$ و$b$ و$x$ و$y$، لكننا سنحتاجها فقط من أجل $a,b\in\{0,1\}$ و$x,y\in\{0,\ldots,2^{m-1}-1\}$. يمكن التحقق منها بتوسيع الجداء في الأس على الجانب الأيمن،

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

حيث تستخدم المساواة الثانية الملاحظة التالية

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

يُعرَّف تحويل فورييه الكمومي ذو الـ$2^m$ بعد كما يلي لكل $u\in\{0,\ldots,2^m - 1\}$.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

إذا كتبنا $u$ و$v$ على النحو

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

لـ$a,b\in\{0,1\}$ و$x,y\in\{0,\ldots,2^{m-1} - 1\}$، نحصل على

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

أخيرًا، بالتفكير في حالات الأساس القياسي $\vert x \rangle \vert a\rangle$ و$\vert b \rangle \vert y \rangle$ كترميزات ثنائية لأعداد صحيحة في المدى $\{0,\ldots,2^m-1\}$،

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

نرى أن الدائرة أعلاه تنفذ العملية المطلوبة. إذا بدت هذه الطريقة لتنفيذ تحويل فورييه الكمومي مذهلة، فهذا لأنها كذلك بالفعل: إنها في جوهرها تحويل فورييه السريع في صورة دائرة كمومية.

أخيرًا، لنعدّ عدد البوابات المستخدمة في الدائرة الموصوفة للتو. بوابات الطور المتحكم فيها ليست ضمن مجموعة البوابات القياسية التي ناقشناها في الدرس السابق، لكن في البداية سنتجاهل ذلك ونعد كل واحدة منها كبوابة مفردة.

لنرمز بـ$s_m$ إلى عدد البوابات التي نحتاجها لكل اختيار ممكن لـ$m$. إذا كانت $m=1$، فإن تحويل فورييه الكمومي هو مجرد عملية هادامارد، لذا

$$s_1 = 1.$$

إذا كانت $m\geq 2$، فإننا في الدائرة أعلاه نحتاج إلى $s_{m-1}$ بوابة لتحويل فورييه الكمومي على $m-1$ Qubit، بالإضافة إلى $m-1$ بوابة طور متحكم فيها، بالإضافة إلى بوابة هادامارد، بالإضافة إلى $m-1$ بوابة تبديل، لذا

$$s_m = s_{m-1} + (2m - 1).$$

يمكننا الحصول على صيغة مغلقة بالجمع:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

في الحقيقة، لا نحتاج بوابات مبادلة بالعدد الذي تصفه الطريقة. لو رتّبنا البوابات قليلاً، يمكننا دفع كل بوابات المبادلة لليمين وتخفيض عدد بوابات المبادلة المطلوبة إلى $\lfloor m/2\rfloor$. من الناحية المقاربة، هذا ليس تحسيناً كبيراً: لا زلنا نحصل على دوائر بحجم $O(m^2)$ لتنفيذ $\mathrm{QFT}_{2^m}$.

لو أردنا تطبيق تحويل فورييه الكمومي باستخدام بوابات من مجموعة بواباتنا القياسية فقط، نحتاج إما إلى بناء أو تقريب كل بوابة طور متحكم بها ببوابات من مجموعتنا. العدد المطلوب يعتمد على مقدار الدقة التي نحتاجها، لكن كدالة في $m$ التكلفة الإجمالية تبقى تربيعية.

في الواقع، من الممكن تقريب تحويل فورييه الكمومي بدقة عالية باستخدام عدد أقل من تربيعي من البوابات، وذلك بالاستفادة من حقيقة أن $P_{\alpha}$ قريبة جداً من عملية المحايد حين يكون $\alpha$ صغيراً جداً — وهذا يعني أنه يمكننا التخلي عن معظم بوابات الطور المتحكم بها دون أن نخسر الكثير من حيث الدقة.

الإجراء العام والتحليل

الآن سنفحص إجراء تقدير الطور بشكل عام. الفكرة هي توسيع نسخة الكيوبتين من تقدير الطور التي درسناها أعلاه بالطريقة الطبيعية التي يقترحها المخطط التالي.

لاحظ أنه مع كل كيوبت تحكم جديد نضيفه في الأعلى، نضاعف عدد مرات تنفيذ العملية الأحادية $U$. هذا يتضح في المخطط من خلال القوى على $U$ لكل عملية أحادية متحكم بها.

أبسط طريقة لتنفيذ عملية controlled-$U^k$ لأي اختيار لـ $k$ هي ببساطة تكرار عملية controlled-$U$ لـ $k$ مرة. لو كانت هذه هي المنهجية المستخدمة، يجب أن نعترف أن إضافة كيوبتات التحكم يساهم بشكل كبير في حجم الدائرة: لو كان لدينا $m$ كيوبت تحكم، كما يُصوّر المخطط، فمجموع $2^m - 1$ نسخة من عملية controlled-$U$ مطلوب. هذا يعني أن تكلفة حسابية كبيرة تُتكبّد كلما زاد $m$ — لكن كما سنرى، هذا يؤدي أيضاً إلى تقريب أدق بكثير لـ $\theta$.

من المهم أن نلاحظ، مع ذلك، أنه لـ بعض اختيارات $U$ قد يكون ممكناً إنشاء دائرة تنفذ عملية $U^k$ لقيم كبيرة من $k$ بطريقة أكثر كفاءة من مجرد تكرار دائرة $U$ لـ $k$ مرة. سنرى مثالاً محدداً على هذا في سياق تحليل الأعداد الصحيحة إلى عوامل لاحقاً في الدرس، حيث تأتي الخوارزمية الفعّالة لـ الرفع الأسي بالمقياس المناقَشة في الدرس السابق للإنقاذ.

الآن لنحلل الدائرة المذكورة. الحالة مباشرة قبل تحويل فورييه الكمومي العكسي تبدو هكذا:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

حالة خاصة

على غرار ما فعلناه في حالة $m=2$، سننظر أولاً في الحالة الخاصة حيث $\theta = y/2^m$ لـ $y\in\{0,\ldots,2^m-1\}$. في هذه الحالة يمكن كتابة الحالة قبل تحويل فورييه الكمومي العكسي بديلاً هكذا:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

إذن، حين يُطبَّق تحويل فورييه الكمومي العكسي، تصبح الحالة

$$\vert\psi\rangle \vert y\rangle$$

والقياسات تكشف عن $y$ (مشفّر بالنظام الثنائي).

تحديد حدود الاحتمالات

لقيم $\theta$ الأخرى، أي التي لا تأخذ الشكل $y/2^m$ لعدد صحيح $y$، نتائج القياس ليست مؤكدة، لكن يمكننا إثبات حدود على احتمالات النتائج المختلفة. من الآن فصاعداً، لنأخذ اختياراً اعتباطياً لـ $\theta$ يحقق $0\leq \theta < 1$.

بعد تطبيق تحويل فورييه الكمومي العكسي، تكون حالة الدائرة هكذا:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

إذن، حين تُجرى القياسات على الـ $m$ كيوبت العلوية، نرى كل نتيجة $y$ باحتمال

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

لنفهم هذه الاحتمالات أكثر، سنستخدم نفس الصيغة التي رأيناها سابقاً، لمجموع الجزء الأولي من متسلسلة هندسية.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

يمكننا تبسيط المجموع الظاهر في صيغة $p_y$ بأخذ $\alpha = e^{2\pi i (\theta - y/2^m)}$. هذا ما نحصل عليه.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

إذن، في الحالة $\theta = y/2^m$، نجد أن $p_y = 1$ (كما عرفنا من النظر في هذه الحالة الخاصة)، وفي الحالة $\theta \neq y/2^m$، نجد أن

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

يمكننا معرفة المزيد عن هذه الاحتمالات بالتفكير في العلاقة بين أطوال الأقواس وأطوال الأوتار على دائرة الوحدة. هذا مخطط يوضح العلاقات التي نحتاجها لأي عدد حقيقي $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$.

أولاً، طول الوتر (مرسوم بالأزرق) لا يمكن أن يكون أكبر من طول القوس (مرسوم بالبنفسجي):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

بالنظر في العلاقة بين هذين الطولين في الاتجاه الآخر، نرى أن نسبة طول القوس إلى طول الوتر تكون أكبر ما يمكن حين $\delta = \pm 1/2$، وفي هذه الحالة النسبة هي نصف محيط الدائرة مقسوماً على القطر، وهو $\pi/2$. وبالتالي لدينا

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

وبالتالي

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

تكشف لنا دراسة هذه العلاقات عن حقيقتين مهمتين.

1. افترض أن $\theta$ عدد حقيقي، وأن $y\in \{0,\ldots,2^m-1\}$ يحقق

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   هذا يعني أن $y/2^m$ إما أفضل تقريب بـ $m$ بت للقيمة $\theta$، أو أنه يقع بالضبط في منتصف المسافة بين $y/2^m$ وبين $(y-1)/2^m$ أو $(y+1)/2^m$، أي أنه أحد أفضل تقريبين للقيمة $\theta$.

   سنثبت أن $p_y$ يجب أن يكون كبيرًا نسبيًا في هذه الحالة. بناءً على الافتراض الذي نأخذه، يترتب على ذلك أن $\vert 2^m \theta - y \vert \leq 1/2$، فيمكننا استخدام الملاحظة الثانية أعلاه المتعلقة بأطوال الأقواس والأوتار لنستنتج أن

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   كما يمكننا استخدام الملاحظة الأولى عن أطوال الأقواس والأوتار لنستنتج أن

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   تطبيق هذين المتراجحتين على $p_y$ يكشف لنا أن

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   هذا يفسر ملاحظتنا بأن أفضل نتيجة تحدث باحتمال أكبر من $40\%$ في النسخة $m=2$ من تقدير الطور التي ناقشناها سابقًا. الاحتمال ليس $40\%$ بالضبط، بل هو $4/\pi^2$، وفي الواقع هذا الحد يسري لكل اختيار للقيمة $m$.

2. الآن افترض أن $y\in \{0,\ldots,2^m-1\}$ يحقق

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   هذا يعني أن هناك تقريبًا أفضل $z/2^m$ للقيمة $\theta$ يقع بين $\theta$ و $y/2^m$.

   هذه المرة سنثبت أن $p_y$ لا يمكن أن يكون كبيرًا جدًا. نبدأ بالملاحظة البسيطة أن

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   وهذا يترتب على حقيقة أن أي نقطتين على دائرة الوحدة لا يمكن أن تختلفا في القيمة المطلقة بأكثر من $2$.

   كما يمكننا استخدام الملاحظة الثانية عن أطوال الأقواس والأوتار من أعلاه، وهذه المرة بتطبيقها على مقام $p_y$ عوضًا عن البسط، لنستنتج

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   الجمع بين المتراجحتين يكشف أن

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   لاحظ أنه رغم أن هذا الحد كافٍ لأغراضنا، إلا أنه تقريب خشن نسبيًا — إذ يكون الاحتمال في الغالب أقل بكثير من $1/4$.

الخلاصة المهمة من هذا التحليل هي أن التقريبات القريبة جدًا من $\theta$ من المرجح أن تحدث — سنحصل على أفضل تقريب بـ $m$ بت باحتمال أكبر من $40\%$ — في حين أن التقريبات التي تبعد أكثر من $2^{-m}$ أقل احتمالًا للحدوث، مع حد أعلى للاحتمال يبلغ $25\%$.

بالنظر إلى هذه الضمانات، يمكن تعزيز ثقتنا بتكرار إجراء تقدير الطور عدة مرات، لجمع دليل إحصائي حول قيمة $\theta$. من المهم الإشارة إلى أن الحالة $\vert\psi\rangle$ لمجموعة الكيوبتات السفلية لا تتأثر بإجراء تقدير الطور، لذا يمكن استخدامها لتشغيل الإجراء بأي عدد من المرات. تحديدًا، في كل مرة نشغل فيها الدائرة، نحصل على أفضل تقريب بـ $m$ بت للقيمة $\theta$ باحتمال أكبر من $40\%$، بينما احتمال الخطأ بأكثر من $2^{-m}$ محدود بـ $25\%$. إذا شغّلنا الدائرة عدة مرات وأخذنا النتيجة الأكثر تكرارًا، فمن المرجح جدًا ألا تكون النتيجة الأكثر شيوعًا هي تلك التي تحدث بحد أقصى $25\%$ من الوقت. وبالتالي، سنحصل على الأرجح على تقريب $y/2^m$ يقع ضمن مسافة $1/2^m$ من القيمة $\theta$. والواقع أن احتمال الخطأ بأكثر من $1/2^m$ يتناقص بشكل أسي مع عدد مرات تشغيل الإجراء.

فيما يلي رسمان بيانيان يوضحان الاحتمالات لثلاث قيم متتالية لـ $y$ عندما يكون $m = 3$ و $m=4$ كدوال للمتغير $\theta$. (يُعرض ثلاثة نتائج فقط للوضوح. يمكن الحصول على احتمالات النتائج الأخرى بالإزاحة الدورية للدالة الأساسية ذاتها.)