خوارزمية شور

هنا سنتناول مسألة تحليل الأعداد الصحيحة إلى عواملها الأولية، ونرى كيف يمكن حلّها بكفاءة على حاسوب كمي باستخدام تقدير الطور. الخوارزمية التي سنصل إليها هي خوارزمية شور لتحليل الأعداد الصحيحة إلى عواملها. لم يصف شور خوارزميته تحديداً من منظور تقدير الطور، لكنها طريقة طبيعية وبديهية لشرح آلية عملها.

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

مسألة إيجاد الرتبة

بعض أساسيات نظرية الأعداد

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

للبداية، لأي عدد صحيح موجب $N,$ نعرّف المجموعة $\mathbb{Z}_N$ كالتالي.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

مثلاً، $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ وهكذا.

هذه مجموعات من الأعداد، لكن يمكننا التفكير فيها بأكثر من كونها مجرد مجموعات. تحديداً، يمكننا التفكير في العمليات الحسابية على $\mathbb{Z}_N$ كالجمع والضرب — وإذا اتفقنا على أخذ النتائج دائماً مودولو $N$ (أي القسمة على $N$ وأخذ الباقي كنتيجة)، فسنبقى دائماً داخل هذه المجموعة عند إجراء هذه العمليات. العمليتان المحددتان للجمع والضرب، كلتاهما مودولو $N,$ تحوّلان $\mathbb{Z}_N$ إلى حلقة، وهي نوع أساسي بالغ الأهمية في الجبر.

مثلاً، $3$ و $5$ عنصران في $\mathbb{Z}_7,$ وإذا ضربناهما معاً نحصل على $3\cdot 5 = 15,$ التي تعطي باقياً مقداره $1$ عند القسمة على $7.$ نعبّر عن هذا أحياناً كالتالي.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

لكن يمكننا أيضاً الكتابة $3 \cdot 5 = 1$ ببساطة، بشرط أن يكون واضحاً أننا نعمل في $\mathbb{Z}_7$، وذلك للإبقاء على رموزنا بسيطة قدر الإمكان.

كمثال، إليك جدولا الجمع والضرب لـ $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

من بين عناصر $\mathbb{Z}_N$ الـ $N$، العناصر $a\in\mathbb{Z}_N$ التي تحقق $\gcd(a,N) = 1$ هي عناصر خاصة. في الغالب تُرمز المجموعة التي تحتوي هذه العناصر بنجمة كالتالي.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

إذا ركّزنا اهتمامنا على عملية الضرب، فإن المجموعة $\mathbb{Z}_N^{\ast}$ تشكّل زمرة — تحديداً زمرة أبيلية — وهي نوع مهم آخر في الجبر. من الحقائق الأساسية حول هذه المجموعات (والزمر المنتهية بشكل عام) أننا إذا اخترنا أي عنصر $a\in\mathbb{Z}_N^{\ast}$ وضربناه في نفسه مراراً، سنصل في النهاية دائماً إلى العدد $1.$

كمثال أول، لنأخذ $N=6.$ لدينا $5\in\mathbb{Z}_6^{\ast}$ لأن $\gcd(5,6) = 1,$ وإذا ضربنا $5$ في نفسه نحصل على $1,$ كما يؤكد الجدول أعلاه.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

كمثال ثانٍ، لنأخذ $N = 21.$ إذا مررنا على الأعداد من $0$ إلى $20$، فتلك التي يكون القاسم المشترك الأكبر لها مع $21$ مساوياً لـ $1$ هي:

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

لكل عنصر من هذه العناصر، يمكن رفع ذلك العدد إلى قوة صحيحة موجبة للحصول على $1.$ إليك أصغر هذه القوى:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

بطبيعة الحال، نحن نعمل داخل $\mathbb{Z}_{21}$ في كل هذه المعادلات، وهو ما لم نكتبه صراحةً — تركناه ضمنيًا حتى لا تتشعب الأمور. وسنكمل على هذا النهج طوال بقية الدرس.

صياغة المسألة والربط بتقدير الطور

الآن يمكننا نصيغ مسألة إيجاد الرتبة.

إيجاد الرتبة

المدخلات: عددان صحيحان موجبان $N$ و $a$ بحيث $\gcd(N,a) = 1$
المخرجات: أصغر عدد صحيح موجب $r$ بحيث $a^r \equiv 1$ $(\textrm{mod } N)$

بعبارة أخرى، بالترميز الذي قدّمناه للتو، المعطيات هي $a \in \mathbb{Z}_N^{\ast},$ ونبحث عن أصغر عدد صحيح موجب $r$ بحيث $a^r = 1.$ هذا العدد $r$ يُسمّى رتبة $a$ بالقياس إلى $N.$

للربط بين مسألة إيجاد الرتبة وتخمين الطور، تأمّل العملية المُعرَّفة على منظومة تتوافق حالاتها الكلاسيكية مع $\mathbb{Z}_N,$ حيث نضرب في عنصر ثابت $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

لنوضّح: الضرب هنا يجري داخل $\mathbb{Z}_N,$ أي أنه يُقاس بالنسبة إلى $N$ ضمنيًا داخل ket في طرف المعادلة الأيمن.

مثلاً، إذا أخذنا $N = 15$ و $a=2,$ فإن تأثير $M_2$ على الأساس القياسي $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ يكون كالتالي.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

هذه عملية وحدوية بشرط أن $\gcd(a,N)=1؛$ فهي تُعيد ترتيب عناصر الأساس القياسي $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ وبالتالي كمصفوفة هي مصفوفة تبديل. يتضح من تعريفها أن هذه العملية حتمية، وأبسط طريقة لرؤية أنها قابلة للعكس هي التفكير في رتبة $r$ لـ $a$ بالقياس إلى $N,$ وإدراك أن معكوس $M_a$ هو $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

ثمة طريقة أخرى للتفكير في المعكوس لا تستلزم معرفة $r$ (الذي هو بالأصل ما نسعى لحسابه). لكل عنصر $a\in\mathbb{Z}_N^{\ast}$ يوجد دائمًا عنصر وحيد $b\in\mathbb{Z}_N^{\ast}$ يحقق $ab=1.$ نرمز لهذا العنصر $b$ بالرمز $a^{-1},$ ويمكن حسابه بكفاءة؛ إذ يؤدي ذلك امتداد خوارزمية إقليدس لإيجاد القاسم المشترك الأكبر بتكلفة تربيعية في $\operatorname{lg}(N).$ وبالتالي

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

إذن، العملية $M_a$ حتمية وقابلة للعكس في آنٍ واحد. وهذا يعني أنها تتمثّل بمصفوفة تبديل، وهي بالتالي وحدوية.

الآن لنفكّر في المتجهات الذاتية والقيم الذاتية للعملية $M_a,$ بافتراض أن $a\in\mathbb{Z}_N^{\ast}.$ كما قلنا للتو، هذا الافتراض يُخبرنا أن $M_a$ وحدوية.

لـ $M_a$ عدد $N$ من القيم الذاتية، قد تتكرر بعضها، وثمة حرية عمومًا في اختيار المتجهات الذاتية المقابلة — لكننا لن نحتاج للقلق بشأن كل الاحتمالات. لنبدأ بشكل مبسّط ونحدد متجهًا ذاتيًا واحدًا فقط لـ $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

العدد $r$ هو رتبة $a$ بالقياس إلى $N,$ هنا وفي كل ما تبقى من الدرس. القيمة الذاتية المرتبطة بهذا المتجه الذاتي هي $1$ لأنه لا يتغيّر عند الضرب في $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

يحدث هذا لأن $a^r = 1,$ وبالتالي كل حالة أساسية قياسية $\vert a^k \rangle$ تنتقل إلى $\vert a^{k+1} \rangle$ لـ $k\leq r-1,$ وتعود $\vert a^{r-1} \rangle$ إلى $\vert 1\rangle.$ بعبارة بسيطة، الأمر كأننا نُحرّك $\vert \psi_0 \rangle$ ببطء، لكنه ممزوج تمامًا أصلًا فلا يتغيّر شيء.

وهنا مثال آخر على متجه ذاتي لـ $M_a.$ هذا المثال بالذات أكثر إثارةً للاهتمام في سياق إيجاد الرتبة وتخمين الطور.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

يمكننا أيضًا كتابة هذا المتجه بصيغة مجموع كالتالي.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

هنا نرى العدد المركّب $\omega_r = e^{2\pi i/r}$ يظهر بشكل طبيعي، نتيجةً لطريقة عمل الضرب في $a$ بالقياس إلى $N.$ القيمة الذاتية المقابلة هذه المرة هي $\omega_r.$ لنتحقق من ذلك بالحساب أولاً.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

ثم، لأن $\omega_r^{-r} = 1 = \omega_r^0$ و $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ نرى أن

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

إذن $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

باستخدام نفس المنطق، يمكننا تحديد أزواج إضافية من المتجهات الذاتية/القيم الذاتية لـ $M_a.$ لأي اختيار $j\in\{0,\ldots,r-1\}$ يكون

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

هو متجه ذاتي لـ $M_a$ وقيمته الذاتية المقابلة هي $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

في الواقع، هناك متجهات ذاتية أخرى لـ $M_a,$ لكن ما يهمنا هنا هو المتجهات $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ التي حددناها للتو فقط.

إيجاد الرتبة عن طريق تقدير الطور

لحل مسألة إيجاد الرتبة لاختيار معين $a\in\mathbb{Z}_N^{\ast},$ يمكننا تطبيق إجراء تقدير الطور على العملية $M_a.$

لعمل هذا، نحتاج أن نُنفّذ ليس فقط $M_a$ بكفاءة في دائرة كمومية، بل أيضًا $M_a^2,$ $M_a^4,$ $M_a^8,$ وهكذا، بالقدر الكافي للحصول على تقدير دقيق من إجراء تقدير الطور. هنا سنشرح كيف يمكن تحقيق هذا، وسنحدد لاحقًا بالضبط كمية الدقة المطلوبة.

لنبدأ بالعملية $M_a$ لوحدها. بطبيعة الحال، بما أننا نشتغل بنموذج الدائرة الكمومية، سنستخدم النظام الثنائي لترميز الأعداد بين $0$ و$N-1.$ أكبر عدد نحتاج لترميزه هو $N-1,$ وعدد البتات المطلوبة هو

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

مثلاً، إذا كان $N = 21$ فعندنا $n = \operatorname{lg}(N-1) = 5.$ هكذا يبدو ترميز عناصر $\mathbb{Z}_{21}$ كسلاسل ثنائية بطول $5.$

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

والآن، هذا هو التعريف الدقيق لكيفية تعريف $M_a$ كعملية على $n$ كيوبت.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

المقصود هنا أنه رغم أننا نهتم فقط بكيفية عمل $M_a$ على $\vert 0\rangle,\ldots,\vert N-1\rangle,$ إلا أننا مضطرين لتحديد كيف تعمل على الحالات القاعدية الأساسية الـ$2^n - N$ المتبقية — وهذا بطريقة تُبقي العملية يونيتارية. تعريف $M_a$ بحيث لا تفعل شيئًا على الحالات الأساسية المتبقية يحقق هذا الشرط.

باستخدام خوارزميات ضرب الأعداد الصحيحة والقسمة التي ناقشناها في الدرس السابق، مع منهجية التنفيذ القابل للعكس وخالي من القمامة، يمكننا بناء دائرة كمومية تُنفّذ $M_a,$ لأي اختيار $a\in\mathbb{Z}_N^{\ast},$ بتكلفة $O(n^2).$ إليك طريقة واحدة لعمل هذا.

1. ابنِ دائرة لتنفيذ العملية

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   حيث

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   باستخدام الطريقة المشروحة في الدرس السابق. هذا يعطينا دائرة بحجم $O(n^2).$

2. بادل نظامَي الـ$n$ كيوبت باستخدام $n$ بوابة مبادلة لتبادل الكيوبتات بشكل فردي.

3. بطريقة مشابهة للخطوة الأولى، ابنِ دائرة للعملية

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   حيث $a^{-1}$ هو معكوس $a$ في $\mathbb{Z}_N^{\ast}.$

بتهيئة الـ$n$ كيوبت السفلية وتركيب الخطوات الثلاث، نحصل على هذا التحويل:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

الطريقة تحتاج كيوبتات فضاء عمل، لكنها تُعاد إلى حالتها الأولية في النهاية، مما يتيح لنا استخدام هذه الدوائر في تقدير الطور. التكلفة الإجمالية للدائرة التي نحصل عليها هي $O(n^2).$

لتنفيذ $M_a^2,$ $M_a^4,$ $M_a^8,$ وهكذا، يمكننا استخدام نفس الطريقة بالضبط، باستثناء أننا نستبدل $a$ بـ$a^2,$ $a^4,$ $a^8,$ وهكذا، كعناصر في $\mathbb{Z}_N^{\ast}.$ يعني، لأي قوة $k$ نختارها، يمكننا إنشاء دائرة لـ$M_a^k$ ليس بتكرار دائرة $M_a$ لـ$k$ مرة، بل بحساب $b = a^k \in \mathbb{Z}_N^{\ast}$ ثم استخدام الدائرة الخاصة بـ$M_b.$

حساب القوى $a^k \in \mathbb{Z}_N$ هو مسألة الأس النموذجي المذكورة في الدرس السابق. يمكن إجراء هذا الحساب بشكل كلاسيكي، باستخدام خوارزمية الأس النموذجي المذكورة في الدرس السابق (التي يُطلق عليها غالبًا خوارزمية القوة في نظرية الأعداد الحسابية). في الواقع، نحتاج فقط لقوى أسس-2 لـ$a,$ تحديدًا $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ ويمكننا الحصول على هذه القوى بالتربيع المتكرر $m-1$ مرة. كل عملية تربيع يمكن تنفيذها بدائرة منطقية بحجم $O(n^2).$

في جوهر الأمر، ما نقوم به هنا هو نقل مشكلة تكرار $M_a$ لما يصل إلى $2^{m-1}$ مرة إلى حساب كلاسيكي فعّال. وهذا من حسن الحظ أنه ممكن! لاختيار عشوائي لدائرة كمومية في مسألة تقدير الطور، هذا على الأرجح لن يكون ممكنًا — وفي ذلك الحال تنمو التكلفة الناتجة لتقدير الطور بشكل أسي في عدد كيوبتات التحكم $m.$

الحل بوجود متجه ذاتي ملائم

لفهم كيف يمكننا حل مسألة إيجاد الرتبة باستخدام تقدير الطور، لنبدأ بافتراض أننا نُشغّل إجراء تقدير الطور على العملية $M_a$ باستخدام المتجه الذاتي $\vert\psi_1\rangle.$ الحصول على هذا المتجه الذاتي ليس بالأمر السهل كما سيتضح، لذا هذه ليست نهاية القصة — لكنه من المفيد أن نبدأ من هنا.

القيمة الذاتية لـ$M_a$ المقابلة للمتجه الذاتي $\vert \psi_1\rangle$ هي

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

أي أن $\omega_r = e^{2\pi i \theta}$ حيث $\theta = 1/r.$ إذن، إذا شغّلنا إجراء تقدير الطور على $M_a$ باستخدام المتجه الذاتي $\vert\psi_1\rangle,$ سنحصل على تقريب لـ$1/r.$ بحساب المقلوب سنتمكن من معرفة $r$ — بشرط أن يكون تقريبنا كافيًا.

بمزيد من التفصيل، عندما نُشغّل إجراء تقدير الطور باستخدام $m$ كيوبت تحكم، ما نحصل عليه هو عدد $y\in\{0,\ldots,2^m-1\}.$ نأخذ بعدها $y/2^m$ كتخمين لـ$\theta,$ وهو $1/r$ في حالتنا هذه. لمعرفة $r$ من هذا التقريب، الشيء الطبيعي هو حساب مقلوب تقريبنا والتقريب إلى أقرب عدد صحيح.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

على سبيل المثال، لنفترض أن $r = 6$ وأننا نُجري تقدير الطور على $M_a$ بالمتجه الذاتي $\vert\psi_1\rangle$ باستخدام $m = 5$ بتات تحكم. أفضل تقريب من $5$ بتات لـ $1/r = 1/6$ هو $5/32,$ ولدينا احتمال جيد (حوالي $68\%$ في هذه الحالة) للحصول على النتيجة $y=5$ من تقدير الطور. لدينا

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

والتقريب إلى أقرب عدد صحيح يعطي $6,$ وهو الجواب الصحيح.

من ناحية أخرى، إذا لم نستخدم دقة كافية، قد لا نحصل على الجواب الصحيح. مثلاً، إذا أخذنا $m = 4$ كيوبتات تحكم في تقدير الطور، قد نحصل على أفضل تقريب من $4$ بتات لـ $1/r = 1/6,$ وهو $3/16.$ أخذ المعكوس يعطي

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

والتقريب إلى أقرب عدد صحيح يعطي جواباً خاطئاً وهو $5.$

إذن كم من الدقة نحتاج للحصول على الجواب الصحيح؟ نعرف أن الرتبة $r$ عدد صحيح، وبشكل حدسي ما نحتاجه هو دقة كافية لتمييز $1/r$ عن الاحتمالات القريبة منها، بما فيها $1/(r+1)$ و $1/(r-1).$ أقرب عدد من $1/r$ يجب أن نأخذه بالحسبان هو $1/(r+1),$ والمسافة بين هذين العددين هي

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

لذلك، إذا أردنا التأكد من أننا لن نخلط بين $1/r$ و $1/(r+1),$ يكفي استخدام دقة كافية لضمان أن أفضل تقريب $y/2^m$ لـ $1/r$ يكون أقرب إلى $1/r$ منه إلى $1/(r+1).$ إذا استخدمنا دقة كافية بحيث

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

بحيث يكون الخطأ أقل من نصف المسافة بين $1/r$ و $1/(r+1),$ فسيكون $y/2^m$ أقرب إلى $1/r$ من أي احتمال آخر، بما فيها $1/(r+1)$ و $1/(r-1).$

يمكننا التحقق من هذا على النحو التالي. لنفترض أن

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

حيث $\varepsilon$ يحقق

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

عند أخذ المعكوس نحصل على

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

بالتكبير في البسط والتصغير في المقام، يمكننا تقدير مدى بُعدنا عن $r$ كالتالي.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

نحن أقل من $1/2$ بعيداً عن $r,$ لذا كما هو متوقع سنحصل على $r$ عند التقريب.

للأسف، لأننا لا نعرف $r$ بعد، لا يمكننا استخدامه لمعرفة مقدار الدقة التي نحتاجها. ما يمكننا فعله بدلاً من ذلك هو الاستفادة من حقيقة أن $r$ يجب أن يكون أصغر من $N$ لضمان استخدام دقة كافية. تحديداً، إذا استخدمنا دقة كافية لضمان أن أفضل تقريب $y/2^m$ لـ $1/r$ يحقق

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

فستكون لدينا دقة كافية لتحديد $r$ بشكل صحيح عند أخذ المعكوس. أخذ $m = 2\operatorname{lg}(N)+1$ يضمن أن لدينا فرصة جيدة للحصول على تقدير بهذه الدقة باستخدام الطريقة الموصوفة سابقاً. (أخذ $m = 2\operatorname{lg}(N)$ يكفي إذا كنا مرتاحين لحد أدنى $40\%$ على احتمال النجاح.)

الحل العام

كما رأينا للتو، إذا كان لدينا المتجه الذاتي $\vert \psi_1 \rangle$ لـ $M_a,$ يمكننا معرفة $r$ عبر تقدير الطور، طالما استخدمنا عدداً كافياً من كيوبتات التحكم لتحقيق هذا بدقة كافية. للأسف، ليس من السهل الحصول على المتجه الذاتي $\vert\psi_1\rangle,$ لذا نحتاج لمعرفة كيف نتابع.

لنفترض لحظةً أننا نتابع تماماً كما في الأعلى، لكن مع المتجه الذاتي $\vert\psi_k\rangle$ بدلاً من $\vert\psi_1\rangle,$ لأي اختيار $k\in\{0,\ldots,r-1\}$ نريد التفكير فيه. النتيجة التي نحصل عليها من إجراء تقدير الطور ستكون تقريباً

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

بافتراض أننا لا نعرف $k$ ولا $r,$ هذا قد يسمح لنا أو لا يسمح لنا بتحديد $r.$ مثلاً، إذا كان $k = 0$ سنحصل على تقريب $y/2^m$ لـ $0,$ وهذا للأسف لا يخبرنا بشيء. لكن هذه حالة غير شائعة؛ بالنسبة لقيم $k$ الأخرى، سنتمكن على الأقل من تعلم شيء عن $r.$

يمكننا استخدام خوارزمية تُعرف بـ خوارزمية الكسور المتسلسلة لتحويل تقريبنا $y/2^m$ إلى كسور قريبة — بما فيها $k/r$ إذا كان التقريب جيداً بما يكفي. لن نشرح خوارزمية الكسور المتسلسلة هنا. بدلاً من ذلك، إليك حقيقة معروفة عن هذه الخوارزمية.

حقيقة

بالنظر إلى عدد صحيح $N\geq 2$ وعدد حقيقي $\alpha\in(0,1),$ يوجد على الأكثر اختيار واحد من الأعداد الصحيحة $u,v\in\{0,\ldots,N-1\}$ مع $v\neq 0$ و $\gcd(u,v)=1$ يحقق $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ بمعطى $\alpha$ و $N,$ تجد خوارزمية الكسور المتسلسلة $u$ و $v,$ أو تُبلّغ بعدم وجودهما. يمكن تنفيذ هذه الخوارزمية كدائرة منطقية بحجم $O((\operatorname{lg}(N))^3).$

إذا كان لدينا تقريب قريب جداً $y/2^m$ لـ $k/r,$ وشغّلنا خوارزمية الكسور المتسلسلة لـ $N$ و $\alpha = y/2^m,$ سنحصل على $u$ و $v$ كما هما موصوفان في الحقيقة. تحليل الحقيقة يسمح لنا بالاستنتاج أن

$$\frac{u}{v} = \frac{k}{r}.$$

لاحظ تحديداً أننا لا نتعلم بالضرورة $k$ و $r,$ بل نتعلم فقط $k/r$ بصورتها المبسّطة.

على سبيل المثال، وكما لاحظنا سابقاً، لن نتعلم أي شيء من $k=0.$ لكن هذه هي القيمة الوحيدة لـ $k$ التي يحدث فيها هذا. عندما يكون $k$ غير صفري، قد يكون له عوامل مشتركة مع $r,$ لكن العدد $v$ الذي نحصل عليه من خوارزمية الكسور المتسلسلة يجب أن يقسم $r$ على الأقل.

هذا ليس واضحاً على الإطلاق، لكنه صحيح: إذا كان لدينا القدرة على معرفة $u$ و $v$ حيث $u/v = k/r$ لـ $k\in\{0,\ldots,r-1\}$ مختارة بشكل عشوائي منتظم، فمن المرجح جداً أن نتمكن من استرداد $r$ بعد عدد قليل من العينات. تحديداً، إذا كان تخميننا لـ $r$ هو المضاعف المشترك الأصغر لجميع قيم المقام $v$ التي نلاحظها، سنكون محقين باحتمال عالٍ.

بشكل حدسي، بعض قيم $k$ ليست مفيدة لأنها تشترك في عوامل مشتركة مع $r,$ وهذه العوامل المشتركة تكون خفية علينا لما نعرف $u$ و $v.$ لكن الاختيارات العشوائية لـ $k$ ما يُرجَّح أنها تخفي عوامل $r$ لفترة طويلة، واحتمال أننا ما نخمّن $r$ صح بأخذ المضاعف المشترك الأصغر للمقامات التي نلاحظها يقل بشكل أسي مع عدد العينات.

لا يزال علينا أن نعالج مسألة كيف نحصل على متجه ذاتي $\vert\psi_k\rangle$ لـ $M_a$ من أجل تشغيل إجراء تقدير الطور عليه. والحقيقة، لا نحتاج إلى إنشائها في الأصل!

ما سنفعله بدلاً من ذلك هو تشغيل إجراء تقدير الطور على الحالة $\vert 1\rangle,$ ونقصد بها الترميز الثنائي بـ $n$ بت للعدد $1,$ بدلاً من متجه ذاتي $\vert\psi\rangle$ لـ $M_a.$ حتى الآن تكلمنا فقط عن تشغيل إجراء تقدير الطور على متجه ذاتي معين، لكن ما في شيء يمنعنا من تشغيل الإجراء على حالة دخل ليست متجهاً ذاتياً لـ $M_a,$ وهذا بالضبط ما نفعله هنا مع الحالة $\vert 1\rangle.$ (هذه ليست متجهاً ذاتياً لـ $M_a$ إلا إذا كان $a=1,$ وهو اختيار لسنا مهتمين به.)

المبرر لاختيار الحالة $\vert 1\rangle$ بدلاً من متجه ذاتي لـ $M_a$ هو أن المعادلة التالية صحيحة.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

طريقة للتحقق من هذه المعادلة هي مقارنة الضرب الداخلي للطرفين مع كل حالة أساسية قياسية، مستخدمين الصيغ المذكورة سابقاً في الدرس للمساعدة في تقييم نتائج الطرف الأيمن. كنتيجة لذلك، سنحصل على نفس نتائج القياس بالضبط كأننا اخترنا $k\in\{0,\ldots,r-1\}$ بشكل موحد عشوائي واستخدمنا $\vert\psi_k\rangle$ كمتجه ذاتي.

بتفصيل أكثر، لنتخيل أننا نشغّل إجراء تقدير الطور مع الحالة $\vert 1\rangle$ بدلاً من أحد المتجهات الذاتية $\vert\psi_k\rangle.$ بعد أداء تحويل فورييه الكمومي العكسي، يتركنا هذا مع الحالة

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

حيث

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

المتجه $\vert\gamma_k\rangle$ يمثل حالة الكيوبتات الـ $m$ العلوية بعد تطبيق عكس تحويل فورييه الكمومي عليها.

إذن، بفضل حقيقة أن $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ مجموعة متعامدة معيارية، نجد أن قياس الكيوبتات الـ $m$ العلوية يعطي تقريباً $y/2^m$ للقيمة $k/r$ حيث يُختار $k\in\{0,\ldots,r-1\}$ بشكل موحد عشوائي. كما ناقشنا بالفعل، هذا يسمح لنا بمعرفة $r$ بدرجة عالية من الثقة بعد عدة تشغيلات مستقلة، وهذا كان هدفنا.

التكلفة الإجمالية

تكلفة تنفيذ كل وحدة تحكم موحدة $M_a^k$ هي $O(n^2).$ هناك $m$ من عمليات الوحدة الموحدة المتحكم بها، ولدينا $m = O(n),$ لذا التكلفة الإجمالية لعمليات الوحدة الموحدة المتحكم بها هي $O(n^3).$ بالإضافة إلى ذلك، لدينا $m$ بوابة هادامارد (تساهم بـ $O(n)$ في التكلفة)، وتحويل فورييه الكمومي العكسي يساهم بـ $O(n^2)$ في التكلفة. إذن، تكلفة عمليات الوحدة الموحدة المتحكم بها تهيمن على تكلفة الإجراء كله — وبالتالي هي $O(n^3).$

بالإضافة إلى الدائرة الكمومية نفسها، هناك بعض الحسابات الكلاسيكية التي نحتاج إلى أدائها على طول الطريق. هذا يشمل حساب القوى $a^k$ في $\mathbb{Z}_N$ لـ $k = 2, 4, 8, \ldots, 2^{m-1},$ وهي مطلوبة لإنشاء بوابات الوحدة الموحدة المتحكم بها، إلى جانب خوارزمية الكسور المتسلسلة التي تحوّل تقريبات $\theta$ إلى كسور. يمكن أداء هذه الحسابات بدوائر بوليانية بتكلفة إجمالية $O(n^3).$

كما هو معتاد، يمكن تحسين كل هذه الحدود باستخدام خوارزميات سريعة مقارباً؛ هذه الحدود تفترض أننا نستخدم خوارزميات قياسية للعمليات الحسابية الأساسية.

التحليل إلى عوامل عبر إيجاد الرتبة

آخر شيء محتاجين نناقشه هو كيف يساعدنا حل مسألة إيجاد الرتبة في التحليل إلى عوامل. هذا الجزء كلاسيكي تماماً — ما له علاقة تحديداً بالحوسبة الكمومية.

إليك الفكرة الأساسية. نريد تحليل العدد $N$ إلى عوامل، ويمكننا فعل ذلك بشكل تعاودي. تحديداً، يمكننا التركيز على مهمة تقسيم $N,$ التي تعني إيجاد أي عددين صحيحين $b,c\geq 2$ بحيث $N = bc.$ هذا ليس ممكناً لو $N$ عدد أولي، لكن يمكننا التحقق بكفاءة إذا كان $N$ أولياً باستخدام خوارزمية اختبار الأولية أولاً، وإذا لم يكن $N$ أولياً سنحاول تقسيمه. بمجرد أن نقسّم $N,$ يمكننا تطبيق التعاود على $b$ و $c$ حتى تصير كل عواملنا أولية ونحصل على التحليل الأولي لـ $N.$

تقسيم الأعداد الزوجية سهل: نُخرج فقط $2$ و $N/2.$

من السهل أيضاً تقسيم القوى الكاملة، يعني الأعداد بالصيغة $N = s^j$ للأعداد الصحيحة $s,j\geq 2,$ فقط بـ تقريب الجذور $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ وهكذا، والتحقق من الأعداد الصحيحة القريبة كمرشحين لـ $s.$ ما نحتاج نتجاوز $\log(N)$ خطوة في هذا التسلسل، لأن عند تلك النقطة الجذر ينزل عن $2$ ولن يكشف مرشحين إضافيين.

من الجيد أننا نستطيع فعل كلا الأمرين لأن إيجاد الرتبة لن يساعدنا في تحليل الأعداد الزوجية أو القوى الأولية, حيث يكون العدد $s$ أولياً. لكن لو كان $N$ فردياً وليس قوة أولية، فإيجاد الرتبة يسمح لنا بتقسيم $N.$

خوارزمية احتمالية لتقسيم عدد صحيح مركّب فردي N ليس قوة أولية

1. اختر عشوائياً $a\in\{2,\ldots,N-1\}.$

2. احسب $d=\gcd(a,N).$

3. إذا كان $d > 1$ فأخرج $b = d$ و $c = N/d$ وأوقف. وإلا استمر للخطوة التالية مع العلم أن $a\in\mathbb{Z}_N^{\ast}.$

4. ليكن $r$ هو رتبة $a$ مودولو $N.$ (هنا نحتاج إيجاد الرتبة.)

5. إذا كان $r$ زوجياً:

   5.1 احسب $x = a^{r/2} - 1$ مودولو $N$
   5.2 احسب $d = \gcd(x,N).$
   5.3 إذا كان $d>1$ فأخرج $b=d$ و $c = N/d$ وأوقف.

6. إذا وصلنا لهذه النقطة، الخوارزمية فشلت في إيجاد عامل لـ $N.$

تشغيل هذه الخوارزمية قد يفشل في إيجاد عامل لـ $N.$ تحديداً، هذا يحدث في حالتين:

• رتبة $a$ مودولو $N$ هي فردية.
• رتبة $a$ مودولو $N$ زوجية و $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

باستخدام نظرية الأعداد الأساسية يمكن إثبات أنه، لاختيار عشوائي لـ $a,$ باحتمال لا يقل عن $1/2$ لا يحدث أيٌّ من هذين الحدثين. في الواقع، احتمال أن يحدث أي من الحدثين لا يتجاوز $2^{-(m-1)}$ حيث $m$ هو عدد العوامل الأولية المتمايزة لـ $N,$ وهذا هو سبب الحاجة لافتراض أن $N$ ليست قوة أولية. (افتراض أن $N$ فردية مطلوب أيضاً لصحة هذه الحقيقة.)

هذا يعني أن كل تشغيل لديه فرصة لا تقل عن 50% لتقسيم $N.$ لذا، لو شغّلنا الخوارزمية $t$ مرة، مع اختيار $a$ عشوائياً كل مرة، سننجح في تقسيم $N$ باحتمال لا يقل عن $1 - 2^{-t}.$

الفكرة الأساسية وراء الخوارزمية هي كالتالي. لو لدينا اختيار لـ $a$ حيث الرتبة $r$ لـ $a$ مودولو $N$ زوجية، فإن $r/2$ عدد صحيح ويمكننا النظر في الأعداد

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

باستخدام الصيغة $Z^2 - 1 = (Z+1)(Z-1),$ نستنتج أن

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

الآن، نعرف أن $a^r \; (\textrm{mod}\; N) = 1$ بتعريف الرتبة — وهذه طريقة أخرى للقول أن $N$ تقسّم $a^r - 1$ بالتساوي. هذا يعني أن $N$ تقسّم الحاصل

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

لكي يكون هذا صحيحاً، يجب أن تكون كل العوامل الأولية لـ $N$ أيضاً عوامل أولية لـ $a^{r/2} - 1$ أو $a^{r/2} + 1$ (أو كليهما) — ولاختيار عشوائي لـ $a$ يتبيّن أنه من غير المرجح أن تقسّم كل العوامل الأولية لـ $N$ أحد الحدّين دون أن تقسّم الآخر. وإلا، فطالما أن بعض العوامل الأولية لـ $N$ تقسّم الحدّ الأول وبعضها يقسّم الحدّ الثاني، سنتمكن من إيجاد عامل غير تافه لـ $N$ بحساب القاسم المشترك الأكبر مع الحدّ الأول.