خوارزمية شور

في وحدة Qiskit in Classrooms هذه، يجب أن يكون لدى الطلاب بيئة Python تعمل بشكل صحيح مع تثبيت الحزم التالية:

• qiskit الإصدار v2.1.0 أو أحدث
• qiskit-ibm-runtime الإصدار v0.40.1 أو أحدث
• qiskit-aer الإصدار v0.17.0 أو أحدث
• qiskit.visualization
• numpy
• pylatexenc

لإعداد هذه الحزم وتثبيتها، راجع دليل تثبيت Qiskit. لتشغيل المهام على حواسيب كمومية حقيقية، يحتاج الطلاب إلى إنشاء حساب على IBM Quantum® باتباع الخطوات الواردة في دليل إعداد حسابك على IBM Cloud.

تم اختبار هذه الوحدة واستغرقت ثلاث ثوانٍ من وقت وحدة معالجة الكم (QPU). هذا تقدير فقط، وقد يختلف الاستخدام الفعلي.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

مقدمة

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

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

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

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

مسألة التحليل إلى عوامل

الهدف من مسألة التحليل إلى عوامل هو إيجاد العوامل الأولية لعدد $N$. بالنسبة لبعض الأعداد $N$، هذا أمر سهل نسبيًا. فمثلًا، إذا كان $N$ زوجيًا، فأحد عوامله الأولية سيكون 2. وإذا كان $N$ قوة أولية، أي $N=p^k$ لعدد أولي $p$ ما، فمن السهل نسبيًا إيجاد $p$: نقترّب من الجذر $k^{\text{th}}$ للعدد $N$ ونبحث عن الأعداد الأولية القريبة التي قد تكون $p$.

لكن تكمن صعوبة الحواسيب الكلاسيكية حين يكون $N$ فرديًا وليس قوة أولية. وهذا هو الحالة التي تتعامل معها خوارزمية شور. تجد الخوارزمية عاملين $p$ و$q$ بحيث يكون $N=pq$، ويمكن تطبيقها بشكل تكراري حتى تصبح جميع العوامل أولية. في الأقسام التالية سنرى كيف يتم التعامل مع هذه المسألة.

الصلة بالأمن السيبراني

تم بناء كثير من المخططات التشفيرية على أساس أن تحليل الأعداد الكبيرة إلى عوامل أمر صعب، بما في ذلك مخطط يُستخدم شائعًا اليوم يُعرف بـ RSA. في RSA، يُنشأ مفتاح عام بضرب عددين أوليين كبيرين معًا للحصول على $N = p\cdot q$. بعد ذلك، يمكن لأي شخص استخدام هذا المفتاح العام لتشفير البيانات. لكن فقط من يملك المفتاح الخاص، وهو $p$ و$q$، يستطيع فك تشفير تلك البيانات.

لو كان تحليل $N$ إلى عوامل أمرًا سهلًا، لتمكّن أي شخص من تحديد $p$ و$q$ وكسر التشفير. لكنه ليس كذلك. هذه مسألة صعبة للغاية واشتُهرت بذلك. في الواقع، لم يُعثر حتى الآن على العوامل الأولية لعدد يُسمى RSA1024، الذي يتكوّن من 1024 رقمًا ثنائيًا و309 رقمًا عشريًا، على الرغم من تقديم جائزة بقيمة $100,000 لتحليله منذ عام 1991.

حل شور

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

الحساب المعياري

الحساب المعياري هو نظام عدّ دوري، بمعنى أن العدّ يبدأ بالطريقة المعتادة بالأعداد الصحيحة 0، 1، 2، إلخ، لكن عند نقطة معينة، بعد دورة $N$، يبدأ العدّ من جديد. لنرى كيف يعمل هذا بمثال. لنفرض أن الدورة هي 5. إذن، أثناء العدّ، بدلًا من الوصول إلى 5، نعود إلى 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

هذا لأنه في عالم "modulo-5"، 5 يعادل 0. نقول إن $5\bmod 5 \ = 0$. وفي الواقع، ستعادل جميع مضاعفات 5 القيمة $0\bmod 5$.

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

استخدم الحساب المعياري لحل المسألة التالية:

غادرت في رحلة قطار طويلة عبر القارات الساعة 8 صباحًا. مدة رحلة القطار 60 ساعة. ما الوقت حين تصل؟

الإجابة:

الدورة هي 24، إذ يحتوي اليوم على 24 ساعة. لذا يمكن كتابة المسألة بالحساب المعياري على النحو التالي:

$(8+60)\text{mod}(24) = 20$

إذن، ستصل إلى وجهتك الساعة 20:00، أو الساعة 8 مساءً.

$\mathbb{Z}_N$ و$\mathbb{Z}_N^*$

من المفيد في الغالب تقديم مجموعتين، $\mathbb{Z}_N$ و$\mathbb{Z}_N^*$. $\mathbb{Z}_N$ هي ببساطة مجموعة الأعداد الموجودة في عالم "modulo-$N$". مثلًا، حين كنّا نعدّ modulo-5، ستكون المجموعة $\mathbb{Z}_5=\{0,1,2,3,4\}$. مثال آخر: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. يمكننا إجراء عمليتي الجمع والضرب (معياريًا بالنسبة لـ $N$) على عناصر $\mathbb{Z}_N$، ونتيجة كل من هاتين العمليتين تكون أيضًا عنصرًا في $\mathbb{Z}_N$، مما يجعل $\mathbb{Z}_N$ كيانًا رياضيًا يُسمى حلقة.

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

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

ما هي $\mathbb{Z}_{15}^*$؟

الإجابة:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

استبعدنا الأعداد التالية:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

ما هي رتبة كل عنصر من عناصر $\mathbb{Z}_{15}^*$؟

الإجابة:

الرتبة $r$ هي أصغر عدد بحيث يكون $a^r\text{mod}(15)=1$ لكل عنصر $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

لاحظ أنه على الرغم من أننا تمكّنا من إيجاد رتبة الأعداد في $\mathbb{Z}_{15}^*$، إلا أن هذا ليس مهمة سهلة بشكل عام لقيم $N$ الأكبر. هذا هو جوهر مسألة التحليل إلى عوامل وسبب حاجتنا إلى حاسوب كمومي. سنرى لماذا حين نتابع بقية المفكرة.

تطبيق الحساب المعياري على مسألة التحليل إلى عوامل

مفتاح إيجاد العاملين $p$ و$q$ بحيث يكون $N=pq$ يعتمد على إيجاد عدد صحيح آخر $x$ بحيث

$x^2 \equiv 1 \bmod N$ و $x \not\equiv \pm 1 \bmod N.$

كيف يساعدنا إيجاد $x$ في إيجاد العاملين $p$ و$q$؟ دعنا نستعرض المنطق الآن. بما أن $x^2 \equiv 1 \bmod N$، فهذا يعني أن $x^2 - 1 \equiv 0 \bmod N$. بعبارة أخرى، $x^2 - 1$ هو مضاعف لـ $N$. لذا، لعدد صحيح ما $l$،

$x^2 - 1 = l N$

يمكننا تحليل $x^2 - 1$ للحصول على:

$(x+1)(x-1) = l N$

من افتراضاتنا الأولية نعلم أن $x \not\equiv \pm 1 \bmod N$، لذا لا يقسم $N$ بالتساوي على $x+1$ أو $x-1$. فالعاملان الاثنان لـ $N$، وهما $p$ و$q$، يجب أن يقسم كل منهما على $x-1$ و$x+1$. إما أن $p$ يقسم $x-1$ و$q$ يقسم $x+1$، أو العكس. لذا، إذا حسبنا القاسم المشترك الأكبر (GCD) بين $N$ وكل من $x-1$ و$x+1$، فسيعطينا ذلك العاملين $p$ و$q$. حساب القاسم المشترك الأكبر بين عددين مهمة كلاسيكية سهلة يمكن إنجازها مثلًا باستخدام خوارزمية إقليدس.

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

قد يكون من الصعب فهم كل خطوة من خطوات المنطق أعلاه، لذا جرّب التحقق منها بمثال. استخدم $N=15$ و$x=11$. أولًا، تحقّق من أن $x^2 \equiv 1 \text{mod}(N)$ و$x \not\equiv \pm 1 \bmod N$. ثم تابع التحقق من كل خطوة. أخيرًا، احسب $\text{GCD}(11\pm1,15)$ وتحقق من أنها عوامل $15$.

الإجابة:

$11^2 = 121$، وهو $15*8 + 1$، إذن $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$، وهو لا يعادل $0\bmod 15$. $\checkmark$

$11 + 1 = 12$، وهو لا يعادل $0\bmod 15$. $\checkmark$

الآن، نعلم أن $(x+1)(x-1) = l N$ لعدد صحيح $l$ ما. يتحقق هذا حين نعوّض بـ $x$ و$N$: $(12)(10) = l 15$ عند $l = 8$. $\checkmark$

الآن، نحتاج إلى حساب $\text{GCD}(12,15)$ و$\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

إذن، وجدنا عوامل $15$!

الخوارزمية

الآن بعد أن رأينا كيف أن إيجاد عدد صحيح $x$ بحيث يكون $x^2 \equiv 1\bmod N$ يساعدنا على تحليل $N$ إلى عوامل، يمكننا استعراض خوارزمية شور. يتلخّص الأمر في جوهره في إيجاد $x$:

1. اختر عددًا صحيحًا عشوائيًا اختر عددًا صحيحًا عشوائيًا $a$ بحيث يكون $1 < a < N$.

• احسب $\text{GCD}(a, N)$ كلاسيكيًا.
  • إذا كان $\text{GCD}(a, N) > 1$، فقد وجدت عاملًا بالفعل. توقف.
  • وإلا، تابع.

2. أوجد الرتبة $r$ لـ $a$ معياريًا بالنسبة لـ $N$ أوجد أصغر عدد صحيح موجب $r$ يحقق $a^r \equiv 1 \pmod N$.

3. تحقق من أن الرتبة زوجية

• إذا كانت $r$ فردية، عُد إلى الخطوة 1 واختر $a$ جديدة.
• إذا كانت $r$ زوجية، تابع إلى الخطوة 4.

4. احسب $x = a^{r/2} \bmod N$

• تحقق من أن $x \not\equiv 1 \pmod N$ وأن $x \not\equiv -1 \pmod N$.
  • إذا كان $x \equiv \pm 1 \pmod N$، عُد إلى الخطوة 1 واختر $a$ جديدة.
• وإلا، احسب القواسم المشتركة الكبرى لاستخراج العوامل:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

ستكون هذه عوامل غير بديهية لـ $N$.

5. حلّل إلى عوامل بشكل تكراري إذا لزم الأمر

• إذا لم يكن $p$ و/أو $q$ أوليين، طبّق الخوارزمية بشكل تكراري لتحليلهما بالكامل.
• بمجرد أن تصبح جميع العوامل أولية، يكتمل التحليل.

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

الجزء الصعب: إيجاد الرتبة

الآن، سنستعرض كيف يمكننا استخدام الحاسوب الكمومي في إيجاد الرتبة. أولًا، لنوضح ما نعنيه بـ "الرتبة". بالطبع، أخبرتك بالفعل ما تعنيه الرتبة رياضيًا: إنها أول عدد صحيح غير صفري $r$ بحيث يكون $a^r = 1 \pmod N.$ لكن دعنا نرى إن كان بإمكاننا اكتساب مزيد من الحدس حول هذا المفهوم.

بالنسبة لقيم $N$ الصغيرة بما يكفي، يمكننا تحديد الرتبة ببساطة بحساب كل قوة من قوى $a$، وأخذ المعيار $N$ لذلك العدد، ثم التوقف حين نجد القوة $r$ التي تحقق $a^r = 1 \text{mod}(N)$. هذا ما فعلناه في مثالنا $N=15$ أعلاه. دعنا نلقي نظرة على بعض رسوم بيانية لهذه القوى المعيارية لبعض قيم $a$ و$N$:

لاحظ شيئًا؟ هذه دوال دورية! والرتبة $r$ هي نفسها الدورة! إذن، إيجاد الرتبة يعادل إيجاد الدورة.

الحواسيب الكمومية مناسبة جدًا لإيجاد دورة الدوال. لهذا الغرض، يمكننا استخدام روتين خوارزمي فرعي يُسمى تقدير الطور الكمومي. تحدّثنا عن QPE وعلاقته بتحويل فورييه الكمومي في الوحدة السابقة. للاطلاع على مراجعة تفصيلية، انتقل إلى وحدة QFT أو درس John Watrous عن تقدير الطور الكمومي في دورة خوارزميات الكم. سنستعرض جوهر الإجراء الآن:

في تقدير الطور الكمومي (QPE)، نبدأ بعامل أحادي $U$ وحالة ذاتية لذلك العامل الأحادي $|\psi\rangle$. ثم نستخدم QPE لتقريب القيمة الذاتية المقابلة، والتي، بما أن العامل أحادي، ستكون على الشكل $e^{2\pi i \theta}$. إذن، إيجاد القيمة الذاتية يعادل إيجاد قيمة $\theta$ في الدالة الدورية. تبدو الدائرة كالتالي:

حيث يحدد عدد كيوبتات التحكم (الكيوبتات $m$ العليا في الشكل أعلاه) دقة التقريب.

في خوارزمية شور، نستخدم QPE على العامل الأحادي $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

هنا، $|y\rangle$ يشير إلى حالة أساس حسابية لسجل متعدد الكيوبتات، حيث القيمة الثنائية للكيوبتات تقابل العدد الصحيح $y$. مثلًا، إذا كان $N=15$ و$y = 2$، فإن $|y\rangle$ يُمثَّل بحالة الأساس رباعية الكيوبتات $|0010\rangle$، إذ يلزم أربعة كيوبتات لترميز الأعداد حتى 15. (إذا كان هذا المفهوم غير مألوف، راجع وحدة Qiskit in Classrooms التمهيدية لمراجعة الترميز الثنائي للحالات الكمومية.)

الآن، نحتاج إلى تحديد حالة ذاتية لهذا العامل الأحادي. إذا بدأنا في الحالة $|1\rangle$، نلاحظ أن كل تطبيق متتالٍ لـ $U$ سيضرب حالة سجلنا في $a \pmod N$، وبعد $r$ تطبيقًا سنصل إلى الحالة $|1\rangle$ مجددًا. مثلًا مع $a = 3$ و$N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

إذن، التراكبات فوق الحالات في هذه الدورة ($|\psi_j\rangle$) على الشكل:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

هي جميعها حالات ذاتية لـ $M_a$. (هناك حالات ذاتية أكثر من هذه، لكننا نهتم فقط بالتي على الشكل أعلاه.)

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

أوجد حالة ذاتية للعامل الأحادي المقابل لـ $a=2$ و$N = 15$.

الإجابة:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

إذن، الرتبة $r=4$. ستكون الحالات الذاتية التي نهتم بها تراكبًا متساويًا لجميع الحالات التي مررنا بها أعلاه، مع أطوار متنوعة:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

لنفرض أننا تمكّنّا من تهيئة حالة كيوبتنا إلى إحدى هذه الحالات الذاتية (سبويلر — لسنا كذلك. أو على الأقل ليس بسهولة. سنوضح لماذا وما يمكننا فعله بدلًا من ذلك قريبًا). عندها يمكننا استخدام QPE لتقدير القيمة الذاتية المقابلة، $\omega_j = e^{2 \pi i \theta_j}$ حيث $\theta_j = \frac{j}{r}$. ثم سنتمكّن من تحديد الرتبة $r$ بالمعادلة البسيطة:

$r = \frac{j}{\theta_j}.$

لكن تذكّر، قلت إن QPE يقدّر $\theta_j$ — لا يعطينا قيمة دقيقة. نحتاج إلى أن يكون التقدير جيدًا بما يكفي للتمييز بين $r$ و$r+1$. كلما زاد عدد كيوبتات التحكم $m$، كان التقدير أفضل. في المسائل في نهاية الدرس، ستُطلب منك تحديد الحد الأدنى لـ $m$ اللازم لتحليل العدد $N$ إلى عوامل.

الآن، علينا التعامل مع مشكلة. كل الشرح أعلاه حول كيفية إيجاد $r$ يبدأ بتحضير الحالة الذاتية $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. لكننا لا نعرف كيف نفعل ذلك دون أن نعرف $r$ مسبقًا. المنطق دائري. نحتاج إلى طريقة لتقدير القيمة الذاتية دون تهيئة الحالة الذاتية.

بدلًا من البدء بحالة ذاتية لـ $M_a$، يمكننا تحضير الحالة الابتدائية في حالة الكيوبت البالغة $n$ المقابلة لـ $|1\rangle$ في الثنائي (أي $|000...01\rangle$). على الرغم من أن هذه الحالة ليست حالة ذاتية لـ $M_a$ بوضوح، إلا أنها تراكب فوق جميع الحالات الذاتية $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

تحقق من أن $|1\rangle$ يعادل التراكب فوق الحالات الذاتية التي وجدتها لـ $N=15$ و$a=2$ في سؤال التحقق السابق.

الإجابة:

الحالات الذاتية الأربع كانت:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

إذن،

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

كيف يساعدنا هذا في إيجاد الرتبة $r$؟ بما أن الحالة الابتدائية هي تراكب فوق جميع الحالات الذاتية من الشكل المذكور أعلاه، فإن خوارزمية QPE تقدّر في آنٍ واحد كل من $\theta_k$ المقابلة لهذه الحالات الذاتية. لذا، قياس كيوبتات التحكم البالغة $m$ في النهاية سيعطي تقريبًا للقيمة $k/r$ حيث $k \in \{0,1,2,...,r-1\}$ هي إحدى القيم الذاتية المختارة عشوائيًا. إذا كرّرنا هذه الدائرة بضع مرات وحصلنا على بضع عيّنات بقيم مختلفة لـ $k$، سنتمكّن بسرعة من استنتاج $r$.

التطبيق في Qiskit

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

سنُشغّل الخوارزمية باستخدام إطار العمل القياسي لدينا لحل المسائل الكمومية، المسمى إطار أنماط Qiskit. يتكوّن من أربع خطوات:

1. تعيين مسألتك على دائرة كمومية
2. تحسين الدائرة لتشغيلها على الأجهزة الكمومية
3. تنفيذ دائرتك على الحاسوب الكمومي
4. المعالجة اللاحقة للقياسات

1. التعيين

لنحلّل $N=15$، مختارين $a=2$ كعددنا الصحيح الأولي المشترك.

أولًا، نحتاج إلى بناء الدائرة التي ستنفّذ العامل الأحادي للضرب المعياري، $M_a$. هذا في الواقع أصعب جزء في التطبيق بأكمله، ويمكن أن يكون مكلفًا حسابيًا جدًا، حسب طريقة إجرائه. لهذا، سنحتال قليلًا: نعلم أننا نبدأ في الحالة $|1\rangle$، ومن سؤال تحقق سابق،

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

إذن، سنبني عاملًا أحاديًا يقوم بالعمليات الصحيحة على هذه الحالات الأربع، لكنه يترك جميع الحالات الأخرى دون تغيير. هذا يعدّ غشًا لأننا نستخدم معرفتنا برتبة $2\bmod 15$ لتبسيط العامل الأحادي. لو كنّا نحاول فعلًا تحليل عدد لا نعرف عواملها، لما تمكّنا من فعل هذا.

اختبر فهمك

اقرأ السؤال/الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث للاطلاع على الحل.

بناءً على معرفتك بكيفية تحويل المؤثر $M_2$ للحالات المذكورة أعلاه، أنشئ المؤثر من سلسلة بوابات SWAP التي تبادل حالات كيوبتين. (تلميح: كتابة كل حالة $|i\rangle$ بالصيغة الثنائية سيساعدك.)

الجواب:

لنعيد كتابة فعل $M_2$ على الحالات بالصيغة الثنائية:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

كل واحدة من هذه الأفعال يمكن تحقيقها بعملية SWAP بسيطة. $M_2|0001\rangle$ تتحقق بتبادل حالتَي الكيوبت $0$ و$1$. $M_2|0010\rangle$ تتحقق بتبادل حالتَي الكيوبت $1$ و$2$. وهكذا. إذن، يمكننا تفكيك مصفوفة $M_2$ إلى السلسلة التالية من بوابات SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

بالأخذ بعين الاعتبار أن المؤثرات تعمل من اليمين إلى اليسار، لنتحقق أن هذا يحقق الأثر المطلوب على كل حالة:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

الآن يمكننا برمجة الدائرة المكافئة لهذا المؤثر في Qiskit.

أولاً، نستورد الحزم اللازمة:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

ثم نبني المؤثر $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

خوارزمية QPE تستخدم بوابة $U$ متحكَّم بها. إذن، بعد أن أنشأنا دائرة $M_2$، نحتاج إلى جعلها دائرة متحكَّم بها $M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

الآن لدينا بوابة $U$ المتحكَّم بها. لكن لتشغيل خوارزمية تقدير الطور الكمي، سنحتاج إلى $U^2$ متحكَّم بها، و$U^4$ متحكَّم بها، وصولاً إلى $U^{2^{m-1}}$ متحكَّم بها، حيث $m$ هو عدد الكيوبتات المستخدمة لتقدير الطور. كلما زاد عدد الكيوبتات، كان تقدير الطور أكثر دقة. سنستخدم $m=8$ كيوبتات تحكم في إجراء تقدير الطور. إذن نحتاج إلى:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

حيث المؤشر $k$، مع $0 \le k \le m-1 = 7$، يتوافق مع كيوبت التحكم. الآن لنحسب $a^{2^k}\bmod N$ لكل قيمة من قيم $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

بما أن $a^{2^k} \bmod N = 1$ عند $k \ge 2$، فإن كل المؤثرات المقابلة ($M_8$ وما فوق) مكافئة للمؤثر الوحداني. إذن، نحتاج فقط إلى بناء مصفوفة واحدة إضافية وهي $M_4$.

ملاحظة: هذا التبسيط يعمل هنا فقط لأن رتبة $2 \bmod 15$ هي $4$. بمجرد أن يصبح $k=2$ (أي $2^k = 4$)، كل قوة لاحقة للمؤثر تصبح مؤثراً وحدانياً. بشكل عام، للأعداد الأكبر $N$ أو اختيارات مختلفة لـ $a$، لا يمكنك تخطي بناء القوى الأعلى. هذا أحد الأسباب التي تجعل هذا يُعتبر مثالاً تجريبياً: الأرقام الصغيرة تتيح اختصارات لن تنجح مع الحالات الأكبر.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

وكما فعلنا سابقاً، نجعلها مؤثر $M_4$ متحكَّماً به:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

الآن، يمكننا تجميع كل شيء معاً لإيجاد رتبة $2\bmod 15$ بدائرة كمومية، باستخدام تقدير الطور:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. التحسين

بعد أن رسمنا دائرتنا، الخطوة التالية هي تحسينها لتشغيلها على حاسوب كمي معين. أولاً نحتاج إلى تحميل الخلفية (backend).

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

إذا لم يكن لديك وقت متاح على حسابك أو أردت استخدام محاكي لأي سبب، يمكنك تشغيل الخلية أدناه لإعداد محاكٍ يحاكي الجهاز الكمي الذي اخترناه أعلاه:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. التنفيذ

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

نرى أربع قمم واضحة عند 00000000 و01000000 و10000000 و11000000، مع بعض العدّات في سلاسل بت أخرى بسبب الضوضاء في الحاسوب الكمي. سنتجاهل هذه ونحتفظ فقط بالأربع القمم الرئيسية من خلال تطبيق عتبة: فقط العدّات التي تتجاوز هذه العتبة تُعتبر إشارة حقيقية فوق الضوضاء.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. المعالجة اللاحقة

في خوارزمية شور، جزء كبير من الخوارزمية يُنفَّذ كلاسيكياً. إذن، سنضع باقي الخطوات في مرحلة "المعالجة اللاحقة"، بعد أن نحصل على قياساتنا من الحاسوب الكمي. كل واحدة من القياسات أعلاه يمكن تحويلها إلى أعداد صحيحة، والتي بعد القسمة على $2^m$ تصبح تقريباتنا لـ $\frac{k}{r}$، حيث $k$ عشوائي في كل مرة.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

الخاتمة

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

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

المسائل

المفاهيم الأساسية:

• تعتمد أنظمة التشفير الحديثة على الصعوبة الكلاسيكية في تحليل الأعداد الصحيحة الكبيرة.
• الحساب المعياري — بما في ذلك البنيتان $\mathbb{Z}_N$ و$\mathbb{Z}_N^*$ — يوفر الأساس الرياضي لخوارزمية شور.
• يمكن اختزال مشكلة تحليل العدد الصحيح $N$ إلى مشكلة إيجاد رتبة عدد ما بالنسبة المعيارية لـ $N$.
• إيجاد الرتبة الكمومي يستخدم تقنيات تقدير الطور الكمي لتحديد دورة الدالة $a^x \mod N$.
• تتكون خوارزمية شور من سير عمل هجين كلاسيكي-كمي يختار قاعدة، وينفذ إيجاد الرتبة كمومياً، ثم يحسب العوامل كلاسيكياً من النتيجة.

صح/خطأ:

1. ص/خ كفاءة خوارزمية شور تهدد أمان تشفير RSA.
2. ص/خ يمكن تنفيذ خوارزمية شور بكفاءة على أي حاسوب كمي حديث.
3. ص/خ تستخدم خوارزمية شور تقدير الطور الكمي (QPE) كروتين فرعي رئيسي.
4. ص/خ الجزء الكلاسيكي من خوارزمية شور يتضمن حساب القاسم المشترك الأكبر (GCD).
5. ص/خ تعمل خوارزمية شور فقط لتحليل الأعداد الزوجية.
6. ص/خ التشغيل الناجح لخوارزمية شور يضمن دائماً الحصول على العوامل الصحيحة.

أسئلة قصيرة:

1. لماذا تُعتبر خوارزمية شور تهديداً مستقبلياً محتملاً لتشفير RSA؟
2. لماذا يُعدّ إيجاد الدورة أو الرتبة لدالة أسية معيارية مفيداً لتحليل عدد ما في خوارزمية شور؟

مسائل تحدي:

1. كم عدد كيوبتات التحكم $m$ الذي نحتاجه لعدد معطى $N$ نحاول تحليله للحصول على الدقة اللازمة في QPE لإيجاد القيمة الصحيحة للرتبة $r$؟