خوارزمية شور

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

في عام 2001، تم عرض خوارزمية شور من قبل مجموعة في شركة IBM ، والتي قامت بتحليل${\displaystyle 15}$داخل${\displaystyle 3\times 5}$باستخدام تطبيق الرنين المغناطيسي النووي لحاسوب كمومي بسبعة كيوبتات. ^{[ 10 ]} بعد تطبيق شركة IBM، قام فريقان مستقلان بتطبيق خوارزمية شور باستخدام كيوبتات ضوئية . ^{[ 11 ] [ 12 ]} في عام 2012، تم تحليل${\displaystyle 15}$أُجريت العملية باستخدام الكيوبتات ذات الحالة الصلبة. ^{[ 13 ]} وفي وقت لاحق، في عام 2012، تم تحليل${\displaystyle 21}$تم تحقيق ذلك. ^{[ 14 ]} في عام 2016، تم تحليل${\displaystyle 15}$أُجريت التجربة مرة أخرى باستخدام كيوبتات الأيونات المحصورة. ^{[ 15 ]} ومع ذلك، لا يفي أي من هذه العروض التوضيحية بمتطلبات خوارزمية شور: فهي تُجمّع الدائرة باستخدام معرفة مسبقة بالحل، بل إن بعضها قد بسّط الخوارزمية بشكل مفرط لدرجة أنها تُصبح مُكافئة لرمي العملة. ^{[ 16 ]}

يمكن التوصل إلى خوارزمية تحليل كاملة إذا تمكنا من تحليل أي عدد بكفاءة${\displaystyle N}$إلى عددين صحيحين فقط${\displaystyle p}$و${\displaystyle q}$أكبر من 1، لأنه إذا كان أي منهما${\displaystyle p}$أو${\displaystyle q}$إذا لم تكن أعدادًا أولية، فيمكن تشغيل خوارزمية التحليل بدورها على تلك الأعداد حتى لا يتبقى سوى الأعداد الأولية.

تتمثل الملاحظة الأساسية في أنه باستخدام خوارزمية إقليدس ، يمكننا دائمًا حساب القاسم المشترك الأكبر بين عددين صحيحين بكفاءة. وعلى وجه الخصوص، هذا يعني أنه يمكننا التحقق بكفاءة مما إذا كان${\displaystyle N}$إذا كان العدد زوجيًا، فإن 2 يكون عاملًا بديهيًا. فلنفترض إذًا أن${\displaystyle N}$يبقى هذا الأمر غريبًا لبقية هذا النقاش. بعد ذلك، يمكننا استخدام خوارزميات كلاسيكية فعالة للتحقق مما إذا كان${\displaystyle N}$هو قوة أولية . ^{[ 17 ]} بالنسبة للقوى الأولية، توجد خوارزميات تحليل كلاسيكية فعالة، ^{[ 18 ]} وبالتالي يمكن لبقية الخوارزمية الكمومية أن تفترض أن${\displaystyle N}$ليست قوة عظمى.

إذا لم تُنتج تلك الحالات السهلة عاملاً غير تافه من${\displaystyle N}$ثم ينتقل البرنامج إلى معالجة الحالة المتبقية. نختار عددًا صحيحًا عشوائيًا.${\displaystyle 2\leq a<N{.}}$قاسم محتمل غير تافه لـ${\displaystyle N}$يمكن إيجادها عن طريق الحساب${\displaystyle \gcd(a,N)}$ويمكن القيام بذلك بطريقة كلاسيكية وفعالة باستخدام خوارزمية إقليدس . إذا نتج عن ذلك عامل غير تافه (بمعنى${\displaystyle \gcd(a,N)\neq 1}$)، وبذلك تكون الخوارزمية قد انتهت، والعامل الآخر غير التافه هو${\displaystyle N/\gcd(a,N)}$إذا لم يتم تحديد عامل غير تافه، فهذا يعني أن${\displaystyle N}$واختيار${\displaystyle a}$هي أعداد أولية فيما بينها ، لذا${\displaystyle a}$يتم احتواؤه في المجموعة الضربية للأعداد الصحيحة modulo${\displaystyle N}$، وله معكوس ضربي modulo${\displaystyle N}$. هكذا،${\displaystyle a}$له ترتيب ضربي${\displaystyle r}$modulo${\displaystyle N}$، معنى

${\displaystyle a^{r}\equiv 1{\bmod {N}},}$

و${\displaystyle r}$هو أصغر عدد صحيح موجب يحقق هذا التطابق.

يجد الروتين الكمومي${\displaystyle r}$يتضح من التطابق أن${\displaystyle N}$يقسم${\displaystyle a^{r}-1}$، مكتوب${\displaystyle N\mid a^{r}-1}$يمكن تحليل هذا باستخدام فرق المربعات :$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1).}$$بما أننا قمنا بتحليل التعبير بهذه الطريقة، فإن الخوارزمية لا تعمل مع الأعداد الفردية.${\displaystyle r}$(لأن${\displaystyle a^{r/2}}$(يجب أن يكون عددًا صحيحًا)، مما يعني أنه سيتعين على الخوارزمية إعادة التشغيل برقم جديد.${\displaystyle a}$ومن ثم يمكننا أن نفترض أن${\displaystyle r}$هو زوجي. لا يمكن أن يكون الأمر كذلك.${\displaystyle N\mid a^{r/2}-1}$لأن هذا من شأنه أن يعني${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$، الأمر الذي من شأنه أن يعني بشكل متناقض أن${\displaystyle r/2}$سيكون ترتيب${\displaystyle a}$، وهو ما كان بالفعل${\displaystyle r}$في هذه المرحلة، قد يكون الأمر كذلك أو لا.${\displaystyle N\mid a^{r/2}+1}$. لو${\displaystyle N}$لم ينقسم${\displaystyle a^{r/2}+1}$إذن، هذا يعني أننا قادرون على إيجاد عامل غير تافه لـ${\displaystyle N}$نقوم بالحساب$${\displaystyle d=\gcd(N,a^{r/2}-1).}$$لو${\displaystyle d=1}$، ثم${\displaystyle N\mid a^{r/2}+1}$كان ذلك صحيحًا، وعاملًا غير تافه من${\displaystyle N}$لا يمكن تحقيق ذلك من${\displaystyle a}$ويجب إعادة تشغيل الخوارزمية بمعالج جديد${\displaystyle a}$وإلا، نكون قد وجدنا عاملاً غير تافه من${\displaystyle N}$والآخر هو${\displaystyle N/d}$وبذلك تنتهي الخوارزمية. في هذه الخطوة، يكون الأمر مكافئًا أيضًا لحساب${\displaystyle \gcd(N,a^{r/2}+1)}$سينتج عنه عامل غير تافه إذا${\displaystyle \gcd(N,a^{r/2}-1)}$غير تافه، ولن يكون كذلك إذا كان تافهاً (حيث${\displaystyle N\mid a^{r/2}+1}$).

يمكن إعادة صياغة الخوارزمية باختصار كما يلي: ليكن${\displaystyle N}$ليكن عددًا فرديًا، وليس قوة عدد أولي. نريد إخراج عاملين غير تافهين من${\displaystyle N}$.

1. اختر رقماً عشوائياً${\displaystyle 1<a<N}$.
2. الحوسبة${\displaystyle K=\gcd(a,N)}$، القاسم المشترك الأكبر لـ${\displaystyle a}$و${\displaystyle N}$.
3. لو${\displaystyle K\neq 1}$، ثم${\displaystyle K}$وهو عامل غير تافه من${\displaystyle N}$أما العامل الآخر فهو${\displaystyle N/K}$وهكذا انتهينا.
4. وإلا، فاستخدم الروتين الفرعي الكمومي لإيجاد الترتيب${\displaystyle r}$ل${\displaystyle a}$.
5. لو${\displaystyle r}$إذا كان الأمر فرديًا، فارجع إلى الخطوة 1.
6. الحوسبة${\displaystyle g=\gcd(N,a^{r/2}+1)}$. لو${\displaystyle g}$وهو ليس بالأمر التافه، أما العامل الآخر فهو${\displaystyle N/g}$وهكذا نكون قد انتهينا. وإلا، فارجع إلى الخطوة الأولى.

لقد ثبت أن هذا من المرجح أن ينجح بعد بضع محاولات. ^{[ 2 ]} عمليًا، يكفي استدعاء واحد للروتين الفرعي لإيجاد الترتيب الكمومي لتحليله بالكامل.${\displaystyle N}$مع احتمال نجاح مرتفع للغاية إذا استخدم المرء أسلوب اختزال أكثر تقدماً. ^{[ 19 ]}

الهدف من الروتين الكمومي لخوارزمية شور هو، بالنظر إلى الأعداد الصحيحة الأولية فيما بينها...${\displaystyle N}$و${\displaystyle 1<a<N}$للعثور على الترتيب${\displaystyle r}$ل${\displaystyle a}$modulo${\displaystyle N}$أصغر عدد صحيح موجب${\displaystyle r}$بحيث${\displaystyle a^{r}\equiv 1{\pmod {N}}}$لتحقيق ذلك، تستخدم خوارزمية شور دائرة كمومية تتضمن سجلين. يستخدم السجل الثاني${\displaystyle n}$الكيوبتات، حيث${\displaystyle n}$هو أصغر عدد صحيح بحيث${\displaystyle N\leq 2^{n}}$، أي،${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$يُحدد حجم السجل الأول مدى دقة التقريب الذي تُنتجه الدائرة. ويمكن إثبات ذلك باستخدام${\displaystyle 2n}$توفر الكيوبتات دقة كافية لإيجاد${\displaystyle r}$تعتمد الدائرة الكمومية الدقيقة على المعاملات.${\displaystyle a}$و${\displaystyle N}$والتي تحدد المشكلة. يستخدم الوصف التالي للخوارزمية ترميز برا-كيت للدلالة على الحالات الكمومية، و${\displaystyle \otimes }$للدلالة على حاصل الضرب الموتري .

تتكون الخوارزمية من خطوتين رئيسيتين:

1. استخدم تقدير الطور الكمومي مع المصفوفة الوحدوية${\displaystyle U}$يمثل عملية الضرب في${\displaystyle a}$(modolo)${\displaystyle N}$) وحالة الإدخال${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$(حيث يكون السجل الثاني)${\displaystyle |1\rangle }$مصنوع من${\displaystyle n}$الكيوبتات). القيم الذاتية لهذا${\displaystyle U}$ترميز المعلومات المتعلقة بالفترة، و${\displaystyle |1\rangle }$يمكن اعتبارها قابلة للكتابة كمجموع متجهاتها الذاتية. وبفضل هذه الخصائص، تُخرج مرحلة تقدير الطور الكمومي عددًا صحيحًا عشوائيًا على الشكل التالي:${\displaystyle {\frac {j}{r}}2^{2n}}$عشوائيًا${\displaystyle j=0,1,...,r-1}$.
2. استخدم خوارزمية الكسور المستمرة لاستخراج الدورة${\displaystyle r}$انطلاقاً من نتائج القياسات التي تم الحصول عليها في المرحلة السابقة، تُجرى هذه العملية لمعالجة بيانات القياس (باستخدام حاسوب تقليدي) التي تم الحصول عليها من قياس حالات الكم الناتجة، واستعادة الدورة.

لم تتم مناقشة العلاقة مع تقدير الطور الكمي في الصياغة الأصلية لخوارزمية شور، ^{[ 2 ]} ولكن تم اقتراحها لاحقًا بواسطة أليكسي كيتايف . ^{[ 20 ]}

تقدير الطور الكمومي

بشكل عام، خوارزمية تقدير الطور الكمومي ، لأي نظام وحدوي${\displaystyle U}$والحالة الذاتية${\displaystyle |\psi \rangle }$بحيث${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$يرسل حالات الإدخال${\displaystyle |0\rangle |\psi \rangle }$لإخراج حالات قريبة من${\displaystyle |\phi \rangle |\psi \rangle }$، أين${\displaystyle \phi }$هو تراكب لأعداد صحيحة قريبة من${\displaystyle 2^{2n}\theta }$بمعنى آخر، يرسل كل حالة ذاتية${\displaystyle |\psi _{j}\rangle }$ل${\displaystyle U}$إلى حالة تحتوي على معلومات قريبة من القيمة الذاتية المرتبطة بها. ولأغراض إيجاد الترتيب الكمومي، نستخدم هذه الاستراتيجية باستخدام الوحدة المحددة بواسطة الفعل$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$فعل${\displaystyle U}$بشأن الولايات${\displaystyle |k\rangle }$مع${\displaystyle N\leq k<2^{n}}$لا يُعدّ هذا الأمر بالغ الأهمية لعمل الخوارزمية، ولكنه ضروري لضمان أن يكون التحويل الكلي بوابة كمومية محددة جيدًا. تنفيذ الدائرة لتقدير الطور الكمومي باستخدام${\displaystyle U}$يتطلب ذلك القدرة على تنفيذ البوابات بكفاءة${\displaystyle U^{2^{j}}}$ويمكن تحقيق ذلك من خلال عملية الأس المعياري ، وهي الجزء الأبطأ من الخوارزمية.

تُحقق البوابة المُعرَّفة على هذا النحو ما يلي:${\displaystyle U^{r}=I}$وهذا يعني مباشرةً أن قيمها الذاتية هي${\displaystyle r}$جذور الوحدة${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$علاوة على ذلك، كل قيمة ذاتية${\displaystyle \omega _{r}^{j}}$له متجه ذاتي على الشكل${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$وهذه المتجهات الذاتية هي بحيث$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$ حيث تُستنتج المتطابقة الأخيرة من صيغة المتسلسلة الهندسية ، مما يعني${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$.

استخدام تقدير الطور الكمومي على حالة الإدخال${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$ثم سيعيد العدد الصحيح${\displaystyle 2^{2n}j/r}$باحتمالية عالية. وبشكل أدق، ترسل دائرة تقدير الطور الكمومي${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$ل${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$بحيث يكون التوزيع الاحتمالي الناتج${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$يبلغ ذروته حوالي${\displaystyle k=2^{2n}j/r}$، مع${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$يمكن جعل هذا الاحتمال قريبًا بشكل تعسفي من 1 باستخدام كيوبتات إضافية.

بتطبيق المنطق المذكور أعلاه على المدخلات${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$وبالتالي، فإن تقدير الطور الكمومي يؤدي إلى التطور$${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$بقياس السجل الأول، أصبح لدينا الآن احتمال متوازن${\displaystyle 1/r}$للعثور على كل${\displaystyle |\phi _{j}\rangle }$، كل منها يعطي تقريبًا صحيحًا لـ${\displaystyle 2^{2n}j/r}$، والتي يمكن قسمتها على${\displaystyle 2^{2n}}$للحصول على قيمة تقريبية عشرية لـ${\displaystyle j/r}$.

تُعدّ عملية الرفع الأسي المعياري الكمومي العائق الرئيسي في خوارزمية شور ، فهي أبطأ بكثير من تحويل فورييه الكمومي والمعالجة المسبقة/اللاحقة التقليدية. توجد عدة طرق لبناء دوائر الرفع الأسي المعياري وتحسينها. أبسط هذه الطرق وأكثرها عملية (حاليًا) هي محاكاة دوائر الحساب التقليدية باستخدام بوابات عكسية ، بدءًا من جامعات التموج . معرفة أساس ومعامل الرفع الأسي تُسهّل إجراء المزيد من التحسينات. ^{[ 22 ] [ 23 ]} تستخدم الدوائر العكسية عادةً ما يقارب${\displaystyle n^{3}}$بوابات لـ${\displaystyle n}$الكيوبتات. تعمل التقنيات البديلة على تحسين عدد البوابات بشكل مقارب باستخدام تحويلات فورييه الكمومية ، لكنها لا تنافس أقل من 600 كيوبت بسبب الثوابت العالية.

بالنظر إلى مجموعة${\displaystyle G}$مع الطلب${\displaystyle p}$ومولد​${\displaystyle g\in G}$لنفترض أننا نعلم أن${\displaystyle x=g^{r}\in G}$بالنسبة للبعض${\displaystyle r\in \mathbb {Z} _{p}}$ونرغب في حساب${\displaystyle r}$، وهو اللوغاريتم المنفصل :${\displaystyle r={\log _{g}}(x)}$لننظر إلى المجموعة الأبيلية${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$حيث يتوافق كل عامل مع الجمع المعياري للقيم. الآن، لننظر إلى الدالة

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

وهذا يعطينا مسألة مجموعة فرعية مخفية أبيلية ، حيث${\displaystyle f}$يتوافق مع تماثل المجموعة . النواة تتوافق مع مضاعفات${\displaystyle (r,1)}$لذا، إذا استطعنا إيجاد النواة، فسنتمكن من إيجاد${\displaystyle r}$توجد خوارزمية كمومية لحل هذه المشكلة. هذه الخوارزمية، مثل خوارزمية إيجاد العوامل، تعود إلى بيتر شور، وكلاهما يُنفذ عن طريق إنشاء تراكب باستخدام بوابات هادامارد، ثم تنفيذ${\displaystyle f}$كتحويل كمي، متبوعًا أخيرًا بتحويل فورييه الكمي. ^{[ 3 ]} ولهذا السبب، يُشار أحيانًا إلى الخوارزمية الكمية لحساب اللوغاريتم المنفصل باسم "خوارزمية شور".

يمكن أيضًا النظر إلى مسألة إيجاد الترتيب على أنها مسألة مجموعة فرعية مخفية. ^{[ 3 ]} ولتوضيح ذلك، لنفترض مجموعة الأعداد الصحيحة تحت عملية الجمع، ولعدد معين من الأعداد الصحيحة.${\displaystyle a\in \mathbb {Z} }$بحيث:${\displaystyle a^{r}=1}$، الوظيفة

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

لأي مجموعة أبيلية منتهية${\displaystyle G}$توجد خوارزمية كمومية لحل المجموعة الفرعية المخفية لـ${\displaystyle G}$في وقت متعدد الحدود. ^{[ 3 ]}