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

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

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

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

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

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

نهج بسيط لمسألة تقدير الطور يتيح لنا تعلم شيء عن قيمة $\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\}$ أساس متعامد معياري. لذا نعرف فورًا أن ثمة قياسًا يمكنه تمييزها تمييزًا مثاليًا — أي أنك لو أُعطيت واحدًا منها دون أن تعرف أيّها، يمكنك معرفة أيّها بلا خطأ.

لإجراء هذا التمييز بدائرة كمومية، يمكننا أولًا تعريف عملية unitarity $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}$$

هذه مصفوفة خاصة، وعلى الأرجح إنّ بعض القرّاء سبق لهم التعامل معها: إنها المصفوفة المرتبطة بـ تحويل فورييه المنفصل ذي البُعد $4$. انطلاقًا من هذه الحقيقة، دعونا نسمّيها $\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.$

هذا تحسّن واضح مقارنةً بالنسخة أحادية الكيوبت التي وصفناها في وقت سابق من الدرس. ليست مثالية — قد تعطينا إجابة خاطئة — لكن الإجابة مُنحازة بشدة نحو قيم $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$ كيوبت، زائد $m-1$ بوابة طور متحكم بها، زائد بوابة هادامار، زائد $m-1$ بوابة تبديل (swap)، إذن

$$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$. (يُعرض ثلاثة نتائج فقط للوضوح. يمكن الحصول على احتمالات النتائج الأخرى بالإزاحة الدورية للدالة الأساسية ذاتها.)