خوارزمية غروفر

في الحوسبة الكمومية ، تُعد خوارزمية جروفر ، والمعروفة أيضًا باسم خوارزمية البحث الكمومي ، خوارزمية كمومية للبحث غير المنظم، حيث تجد باحتمالية عالية المدخل الفريد لدالة الصندوق الأسود التي تُنتج قيمة إخراج معينة، باستخدام فقط${\displaystyle O({\sqrt {N}})}$تقييمات الدالة، حيث${\displaystyle N}$يمثل حجم نطاق الدالة . وقد ابتكره عالم الحاسوب الهندي الأمريكي لوف جروفر في عام 1996. ^{[ 1 ]}

ستكون للمشكلة المماثلة في الحوسبة الكلاسيكية تعقيد استعلامي${\displaystyle O(N)}$(أي، يجب تقييم الدالة)${\displaystyle O(N)}$الأوقات: لا توجد طريقة أفضل من تجربة جميع قيم الإدخال واحدة تلو الأخرى، وهو ما يستغرق في المتوسط${\displaystyle N/2}$خطوات). ^{[ 1 ]}

أثبت كل من تشارلز إتش. بينيت ، وإيثان بيرنشتاين، وجيل براسارد ، وأوميش فازيراني أن أي حل كمومي للمشكلة يحتاج إلى تقييم الدالة${\displaystyle \Omega ({\sqrt {N}})}$^{[ 2 ]} بما أن الخوارزميات الكلاسيكية لمسائل NP - complete تتطلب عددًا هائلاً من الخطوات، وخوارزمية جروفر لا توفر سوى تسريع تربيعي على الحل الكلاسيكي للبحث غير المنظم، فإن هذا يشير إلى أن خوارزمية جروفر وحدها لن توفر حلولًا في زمن متعدد الحدود لمسائل NP-complete (لأن الجذر التربيعي للدالة الأسية يظل دالة أسية، وليس دالة متعددة الحدود). ^{[ 3 ]}

على عكس الخوارزميات الكمومية الأخرى، التي قد توفر تسارعًا أُسّيًا مقارنةً بنظيراتها الكلاسيكية، فإن خوارزمية غروفر لا توفر سوى تسارع تربيعي. ومع ذلك، حتى التسارع التربيعي يُعدّ كبيرًا عندما${\displaystyle N}$نظرًا لكبر حجمها، يمكن تطبيق خوارزمية غروفر لتسريع فئات واسعة من الخوارزميات. ^{[ 3 ]} تستطيع خوارزمية غروفر اختراق مفتاح تشفير متناظر بطول 128 بت في حوالي 2^ ⁶⁴ تكرارًا، أو مفتاح بطول 256 بت في حوالي 2^ ¹²⁸ تكرارًا. مع ذلك، قد لا تشكل خوارزمية غروفر خطرًا متزايدًا بشكل ملحوظ على التشفير مقارنةً بالخوارزميات التقليدية الحالية. ^{[ 4 ]}

يمكن استخدام خوارزمية غروفر، إلى جانب متغيراتها مثل تضخيم السعة ، لتسريع نطاق واسع من الخوارزميات. ^{[ 5 ] [ 6 ] [ 7 ]} على وجه الخصوص، يمكن تسريع خوارزميات مسائل NP-complete التي تتضمن بحثًا شاملاً كإجراء فرعي باستخدام خوارزمية غروفر. ^{[ 6 ]} تُعد أفضل خوارزمية نظرية حالية، من حيث تعقيد أسوأ حالة، لمسألة 3SAT مثالًا على ذلك. كما تشهد مسائل إرضاء القيود العامة تسارعًا تربيعيًا مع خوارزمية غروفر. ^{[ 8 ]} لا تتطلب هذه الخوارزميات أن يكون الإدخال على شكل أوراكل، نظرًا لتطبيق خوارزمية غروفر باستخدام دالة صريحة، مثل الدالة التي تتحقق من أن مجموعة من البتات تُحقق حالة 3SAT. مع ذلك، يبقى من غير الواضح ما إذا كانت خوارزمية غروفر قادرة على تسريع أفضل الخوارزميات العملية لهذه المسائل.

يمكن لخوارزمية غروفر أيضًا أن تُحقق تسريعًا مُثبتًا لمسائل الصندوق الأسود في تعقيد الاستعلام الكمومي ، بما في ذلك تمييز العناصر ^{[ 9 ]} ومسألة التصادم ^{[ 10 ]} (التي تم حلها باستخدام خوارزمية براسارد-هوير-تاب ). في هذا النوع من المسائل، تُعامل دالة التنبؤ f كقاعدة بيانات، والهدف هو استخدام الاستعلام الكمومي لهذه الدالة بأقل عدد ممكن من المرات.

لنفترض أن لدينا دالة كمدخل لخوارزمية جروفر${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$في تشبيه "قاعدة البيانات غير المهيكلة"، يمثل المجال مؤشرات لقاعدة البيانات، و${\displaystyle f(x)=1}$إذا كانت البيانات التي${\displaystyle x}$تشير النقاط إلى ما يفي بمعيار البحث. نفترض أيضًا أن فهرسًا واحدًا فقط يفي بـ${\displaystyle f(x)=1}$ونسمي هذا المؤشر${\displaystyle \omega }$هدفنا هو تحديد${\displaystyle \omega }$.

يمكننا الوصول${\displaystyle f}$باستخدام روتين فرعي (يسمى أحيانًا أوراكل ) على شكل عامل وحدوي${\displaystyle U_{\omega }}$والتي تعمل على النحو التالي:

$${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{لـ }}x=\omega {\text{، أي }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{لـ }}x\neq \omega {\text{، أي }}f(x)=0.\end{cases}}}$$

يستخدم هذا${\displaystyle N}$فضاء الحالة ذو الأبعاد${\displaystyle {\mathcal {H}}}$، والذي يتم توفيره من خلال سجل مع${\displaystyle n=\lceil \log _{2}N\rceil }$الكيوبتات . غالبًا ما يُكتب هذا على النحو التالي:

$${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$$

مخرجات خوارزمية غروفر${\displaystyle \omega }$باحتمالية لا تقل عن${\displaystyle 1/2}$استخدام${\displaystyle O({\sqrt {N}})}$تطبيقات${\displaystyle U_{\omega }}$يمكن زيادة هذا الاحتمال بشكل كبير عن طريق تشغيل خوارزمية غروفر عدة مرات. إذا تم تشغيل خوارزمية غروفر حتى${\displaystyle \omega }$إذا تم العثور على ذلك، فإن العدد المتوقع للتطبيقات لا يزال${\displaystyle O({\sqrt {N}})}$، لأنه سيتم تشغيله مرتين فقط في المتوسط.

تُعطى خطوات خوارزمية جروفر على النحو التالي:

1. قم بتهيئة النظام إلى حالة التراكب المنتظم على جميع الحالات${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. قم بتنفيذ "تكرار غروفر" التالي${\displaystyle r(N)}$الأوقات:
   1. قم بتطبيق المشغل${\displaystyle U_{\omega }}$
   2. قم بتطبيق عامل انتشار جروفر${\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}$
3. قم بقياس الحالة الكمومية الناتجة في الأساس الحسابي.

بالنسبة للقيمة المختارة بشكل صحيح لـ${\displaystyle r}$، ستكون النتيجة${\displaystyle |\omega \rangle }$باحتمالية تقترب من 1 عندما يكون N ≫ 1. يُظهر التحليل أن هذه القيمة النهائية لـ${\displaystyle r(N)}$يرضي${\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}$.

يمكن تنفيذ خطوات هذه الخوارزمية باستخدام عدد من البوابات يتناسب خطيًا مع عدد الكيوبتات. ^{[ 3 ]} وبالتالي، فإن تعقيد البوابات لهذه الخوارزمية هو${\displaystyle O(\log(N)r(N))}$، أو${\displaystyle O(\log(N))}$لكل تكرار.

يوجد تفسير هندسي لخوارزمية غروفر، ينبع من ملاحظة أن الحالة الكمومية لخوارزمية غروفر تبقى في فضاء فرعي ثنائي الأبعاد بعد كل خطوة. لنفترض المستوى الذي يمتد بواسطة${\displaystyle |s\rangle }$و${\displaystyle |\omega \rangle }$أو بعبارة أخرى، المستوى الذي يمتد عليه${\displaystyle |\omega \rangle }$والكيت العمودي${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$.

تبدأ خوارزمية غروفر بالحالة الأولية${\displaystyle |s\rangle }$، والذي يقع في الفضاء الجزئي. المؤثر${\displaystyle U_{\omega }}$هو انعكاس عند المستوى الفائق المتعامد مع${\displaystyle |\omega \rangle }$بالنسبة للمتجهات في المستوى الممتد بواسطة${\displaystyle |s'\rangle }$و${\displaystyle |\omega \rangle }$أي أنه يعمل كانعكاس عبر${\displaystyle |s'\rangle }$ويمكن ملاحظة ذلك من خلال الكتابة${\displaystyle U_{\omega }}$على شكل انعكاس لرب الأسرة :

$${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$$

المشغل${\displaystyle U_{s}=2|s\rangle \langle s|-I}$هو انعكاس من خلال${\displaystyle |s\rangle }$كلا المشغلين${\displaystyle U_{s}}$و${\displaystyle U_{\omega }}$خذ الولايات في المستوى الذي يمتد عليه${\displaystyle |s'\rangle }$و${\displaystyle |\omega \rangle }$إلى الحالات الموجودة في المستوى. لذلك، تبقى خوارزمية غروفر في هذا المستوى طوال مدة الخوارزمية.

من السهل التحقق من أن المشغل${\displaystyle U_{s}U_{\omega }}$في كل خطوة من خطوات تكرار غروفر، يتم تدوير متجه الحالة بزاوية${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$لذا، مع عدد كافٍ من التكرارات، يمكن للمرء أن يدور من الحالة الأولية${\displaystyle |s\rangle }$إلى حالة الإخراج المطلوبة${\displaystyle |\omega \rangle }$. تكون الحالة الابتدائية قريبة من الحالة المتعامدة مع${\displaystyle |\omega \rangle }$:

$${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$$

من الناحية الهندسية، الزاوية${\displaystyle \theta /2}$بين${\displaystyle |s\rangle }$و${\displaystyle |s'\rangle }$يُعطى بواسطة

$${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$$

يجب أن نتوقف عندما يقترب متجه الحالة من${\displaystyle |\omega \rangle }$بعد ذلك، تقوم التكرارات اللاحقة بتدوير متجه الحالة بعيدًا عن${\displaystyle |\omega \rangle }$مما يقلل من احتمالية الحصول على الإجابة الصحيحة. الاحتمالية الدقيقة لقياس الإجابة الصحيحة هي

$${\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}$$

حيث يمثل r عدد تكرارات غروفر (عدد صحيح). وبالتالي، فإن أقرب وقت نحصل فيه على قياس شبه مثالي هو${\displaystyle r\approx \pi {\sqrt {N}}/4}$.

لإكمال التحليل الجبري، نحتاج إلى معرفة ما يحدث عند تطبيق ذلك بشكل متكرر${\displaystyle U_{s}U_{\omega }}$إحدى الطرق الطبيعية للقيام بذلك هي تحليل القيم الذاتية للمصفوفة. لاحظ أنه خلال عملية الحساب بأكملها، تكون حالة الخوارزمية عبارة عن توليفة خطية من${\displaystyle s}$و${\displaystyle \omega }$يمكننا كتابة فعل${\displaystyle U_{s}}$و${\displaystyle U_{\omega }}$في المساحة التي تمتد عليها${\displaystyle \{|s\rangle ,|\omega \rangle \}}$مثل:

${\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}$

لذا في الأساس${\displaystyle \{|\omega \rangle ,|s\rangle \}}$(وهو ليس متعامدًا ولا أساسًا للفضاء بأكمله) الفعل${\displaystyle U_{s}U_{\omega }}$تطبيق${\displaystyle U_{\omega }}$ثم يتبع ذلك${\displaystyle U_{s}}$يتم تحديدها بواسطة المصفوفة

$${\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}$$

تتميز هذه المصفوفة بشكل جوردان ملائم للغاية . إذا عرّفنا${\displaystyle t=\arcsin(1/{\sqrt {N}})}$، إنها

$${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$$

أين${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$

ويترتب على ذلك أن القوة r للمصفوفة (المقابلة لـ r تكرارًا) هي

$${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$$

باستخدام هذا الشكل، يمكننا استخدام المتطابقات المثلثية لحساب احتمالية رصد ω بعد r تكرارات مذكورة في القسم السابق،

$${\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}$$

بدلاً من ذلك، يمكن للمرء أن يتصور بشكل معقول أن الوقت الأمثل تقريبًا للتمييز سيكون عندما تكون الزاويتان 2rt و -2rt متباعدتين قدر الإمكان، وهو ما يتوافق مع${\displaystyle 2rt\approx \pi /2}$، أو${\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}$ثم يكون النظام في حالة

$${\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}$$

تُظهر عملية حسابية بسيطة الآن أن الملاحظة تُعطي الإجابة الصحيحة ω مع وجود خطأ${\displaystyle O\left({\frac {1}{N}}\right)}$.

_{تُعتبر خوارزمية غروفر مثالية حتى عوامل شبه ثابتة. أي أن أي خوارزمية تصل إلى} قاعدة البيانات فقط باستخدام العامل Uω يجب أن تطبق Uω على الأقل _a${\displaystyle 1-o(1)}$^{[ 21 ]} يُعدّ توسيع خوارزمية غروفر لتشمل k مدخلات مطابقة، π ( N / k ) ^¹/² /⁴، مثاليًا أيضًا. ^{[ 18 ]} هذه النتيجة مهمة لفهم حدود الحوسبة الكمومية.

إذا كان بالإمكان حل مسألة بحث غروفر باستخدام log ^c N تطبيقًا للدالة U _ω ، فإن ذلك يعني أن مجموعة NP محتواة في BQP ، وذلك بتحويل مسائل NP إلى مسائل بحث من نوع غروفر. تشير مثالية خوارزمية غروفر إلى أن الحواسيب الكمومية لا تستطيع حل مسائل NP-Complete في وقت متعدد الحدود، وبالتالي فإن NP غير محتواة في BQP.

لقد ثبت أن فئة من الحواسيب الكمومية ذات المتغيرات الخفية غير المحلية يمكنها تنفيذ عملية بحث عن${\displaystyle N}$قاعدة بيانات العناصر في أكثر من${\displaystyle O({\sqrt[{3}]{N}})}$خطوات. هذا أسرع من${\displaystyle O({\sqrt {N}})}$الخطوات التي اتخذتها خوارزمية جروفر. ^{[ 22 ]}

• تضخيم السعة
• خوارزمية Brassard-Høyer-Tapp (لحل مشكلة التصادم )
• خوارزمية شور (للتحليل إلى عوامل)
• بحث المشي الكمومي

• جروفر إل كيه: خوارزمية ميكانيكية كمومية سريعة للبحث في قواعد البيانات ، وقائع الندوة السنوية الثامنة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة، (مايو 1996) ص  212
• Grover LK: من معادلة شرودنغر إلى خوارزمية البحث الكمي ، المجلة الأمريكية للفيزياء، 69(7): 769–777، 2001. مراجعة تربوية للخوارزمية وتاريخها.
• Grover LK: الحوسبة الكمومية: كيف يمكن للمنطق الغريب للعالم دون الذري أن يجعل من الممكن للآلات أن تحسب ملايين المرات أسرع مما تفعل اليوم. العلوم ، يوليو/أغسطس 1999، ص  24-30.
• نيلسن، ماجستير وتشوانغ، آي إل. الحوسبة الكمومية والمعلومات الكمومية . مطبعة جامعة كامبريدج، 2000. الفصل 6.
• ما هو دليل الهاتف الكمومي؟، لوف غروفر، لوسنت تكنولوجيز

• ديفي ويبيرال. "محاكي الدوائر الكمومية" . مؤرشف من الأصل بتاريخ 16 يناير 2017. تم الاطلاع عليه بتاريخ 13 يناير 2017 .
• كريغ غيدني (5 مارس 2013). "خوارزمية غروفر للبحث الكمي" . مؤرشف من الأصل بتاريخ 17 نوفمبر 2020. تم الاطلاع عليه بتاريخ 8 مارس 2013 .
• فرانسوا شوارزنتروبر (2013-05-18). "خوارزمية غروفر" .
• ألكسندر بروكوبينيا. "دائرة كمومية تُنفذ خوارزمية بحث جروفر" . وولفرام ألفا .
• "الحوسبة الكمومية، نظرية" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• روبرتو مايستري (11 مايو 2018). "خوارزمية غروفر مُطبقة بلغة R و C" . جيت هاب .
• برنارد عمر. "QCL - لغة برمجة للحواسيب الكمومية" . تاريخ الاسترجاع: 30 أبريل 2022. تم التنفيذ في /qcl-0.6.4/lib/grover.qcl