تضخيم السعة

تضخيم السعة هو أسلوب في الحوسبة الكمومية يعمم الفكرة الكامنة وراء خوارزمية بحث غروفر ، ويؤدي إلى ظهور عائلة من الخوارزميات الكمومية . اكتشفه جيل براسارد وبيتر هوير في عام 1997، ^{[ 1 ]} وأعاد لوف غروفر اكتشافه بشكل مستقل في عام 1998. ^{[ 2 ]}

في الحاسوب الكمومي، يمكن استخدام تضخيم السعة للحصول على تسريع تربيعي مقارنة بالعديد من الخوارزميات الكلاسيكية.

يتبع الاشتقاق المعروض هنا تقريبًا الاشتقاق الذي قدمه براسارد وآخرون في عام 2000. ^{[ 3 ]} لنفترض أن لدينا${\displaystyle N}$فضاء هيلبرت ذو الأبعاد n${\displaystyle {\mathcal {H}}}$يمثل فضاء الحالة لنظام كمومي، يمتد بواسطة حالات الأساس الحسابي المتعامد${\displaystyle B:=\{|k\rangle \}_{k=0}^{N-1}}$علاوة على ذلك، افترض أن لدينا عامل إسقاط هيرميتي${\displaystyle P\colon {\mathcal {H}}\to {\mathcal {H}}}$. بدلاً عن ذلك،${\displaystyle P}$يمكن تقديمها بدلالة دالة أوراكل منطقية${\displaystyle \chi \colon \mathbb {Z} \to \{0,1\}}$ وأساس تشغيلي متعامد ${\displaystyle B_{\text{op}}:=\{|\أوميغا _{ك}\rangle \}_{k=0}^{N-1}}$وفي هذه الحالة

${\displaystyle P:=\sum _{\chi (k)=1}|\omega _{k}\rangle \langle \omega _{k}|}$.

${\displaystyle P}$يمكن استخدامها للتقسيم${\displaystyle {\mathcal {H}}}$إلى مجموع مباشر لفضاءين فرعيين متعامدين، الفضاء الفرعي الجيد${\displaystyle {\mathcal {H}}_{1}}$والفضاء الفرعي السيئ${\displaystyle {\mathcal {H}}_{0}}$:$${\displaystyle {\begin{aligned}{\mathcal {H}}_{1}&:={\text{Image}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=1\},\\{\mathcal {H}}_{0}&:={\text{Ker}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=0\}.\end{aligned}}}$$بمعنى آخر، نحن نحدد " فضاءً فرعياً جيداً ".${\displaystyle {\mathcal {H}}_{1}}$عبر جهاز العرض${\displaystyle P}$ثم يتمثل هدف الخوارزمية في تطوير حالة أولية معينة.${\displaystyle |\psi \rangle \in {\mathcal {H}}}$إلى دولة تابعة لـ${\displaystyle {\mathcal {H}}_{1}}$.

بالنظر إلى متجه الحالة المعياري${\displaystyle |\psi \rangle \in {\mathcal {H}}}$مع وجود تداخل غير صفري مع كلا الفضاءين الفرعيين، يمكننا تحليله بشكل فريد على النحو التالي:

${\displaystyle |\psi \rangle =\sin(\theta )|\psi _{1}\rangle +\cos(\theta )|\psi _{0}\rangle }$،

أين${\displaystyle \theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in [0,\pi /2]}$، و ${\displaystyle |\psi _{1}\rangle }$و${\displaystyle |\psi _{0}\rangle }$هي الإسقاطات المعيارية لـ ${\displaystyle |\psi \rangle }$إلى المساحات الفرعية${\displaystyle {\mathcal {H}}_{1}}$و${\displaystyle {\mathcal {H}}_{0}}$على التوالي. يُعرّف هذا التفكيك فضاءً فرعياً ثنائي الأبعاد ${\displaystyle {\mathcal {H}}_{\psi }}$، الممتدة بواسطة المتجهات ${\displaystyle |\psi _{0}\rangle }$و${\displaystyle |\psi _{1}\rangle }$ احتمالية العثور على النظام في حالة جيدة عند قياسه هي${\displaystyle \sin ^{2}(\theta )}$.

عرّف عاملًا وحدويًا${\displaystyle Q(\psi ,P):=-S_{\psi }S_{P}\,\!}$، أين

${\displaystyle {\begin{aligned}S_{\psi }&=I-2|\psi \rangle \langle \psi |\quad {\text{and}}\\S_{P}&=I-2P.\end{aligned}}}$

${\displaystyle S_{P}}$يقلب طور الحالات في الفضاء الفرعي الجيد ، بينما ${\displaystyle S_{\psi }}$يقلب طور الحالة الأولية${\displaystyle |\psi \rangle }$.

إجراء هذا المشغل على${\displaystyle {\mathcal {H}}_{\psi }}$يُعطى بواسطة

${\displaystyle Q|\psi _{0}\rangle =-S_{\psi }|\psi _{0}\rangle =(2\cos ^{2}(\theta )-1)|\psi _{0}\rangle +2\sin(\theta )\cos(\theta )|\psi _{1}\rangle }$و

${\displaystyle Q|\psi _{1}\rangle =S_{\psi }|\psi _{1}\rangle =-2\sin(\theta )\cos(\theta )|\psi _{0}\rangle +(1-2\sin ^{2}(\theta ))|\psi _{1}\rangle }$.

وهكذا في${\displaystyle {\mathcal {H}}_{\psi }}$الفضاء الجزئي${\displaystyle Q}$يتوافق ذلك مع دوران بزاوية${\displaystyle 2\theta \,\!}$:

${\displaystyle Q={\begin{pmatrix}\cos(2\theta )&\sin(2\theta )\\-\sin(2\theta )&\cos(2\theta )\end{pmatrix}}}$.

التقديم${\displaystyle Q}$${\displaystyle n}$أوقات في الولاية ${\displaystyle |\psi \rangle }$ أعطِ

${\displaystyle Q^{n}|\psi \rangle =\cos((2n+1)\theta )|\psi _{0}\rangle +\sin((2n+1)\theta )|\psi _{1}\rangle }$،

تدوير الحالة بين الفضاءات الفرعية الجيدة والسيئة . بعد ذلك${\displaystyle n}$عدد التكرارات، احتمال العثور على النظام في حالة جيدة هو${\displaystyle \sin ^{2}((2n+1)\theta )\,\!}$تكون الاحتمالية في أعلى مستوياتها إذا اخترنا

${\displaystyle n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor }$.

حتى هذه النقطة، تزيد كل تكرارة من سعة الحالات الجيدة ، ومن هنا جاء اسم التقنية.

لنفترض أن لدينا قاعدة بيانات غير مرتبة مع${\displaystyle N}$العناصر، ووظيفة أوراكل${\displaystyle \chi }$والتي يمكنها التعرف على المدخلات الجيدة التي نبحث عنها، و${\displaystyle B_{\text{op}}=B}$لتبسيط الأمور.

إذا كان هناك${\displaystyle G}$بعد جمع البيانات الجيدة في قاعدة البيانات، يمكننا العثور عليها عن طريق تهيئة سجل كمومي.${\displaystyle |\psi \rangle }$مع${\displaystyle n}$الكيوبتات حيث${\displaystyle 2^{n}=N}$في تراكب موحد لجميع عناصر قاعدة البيانات${\displaystyle N}$بحيث

${\displaystyle |\psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}|k\rangle }$

وبتشغيل الخوارزمية المذكورة أعلاه، يكون تداخل الحالة الأولية مع الفضاء الفرعي الجيد مساوياً للجذر التربيعي لتردد الإدخالات الجيدة في قاعدة البيانات.${\displaystyle \sin(\theta )=|P|\psi \rangle |={\sqrt {G/N}}}$. لو${\displaystyle \sin(\theta )\ll 1}$يمكننا تقريب عدد التكرارات المطلوبة على النحو التالي:

${\displaystyle n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor \approx \left\lfloor {\frac {\pi }{4\sin(\theta )}}\right\rfloor =\left\lfloor {\frac {\pi }{4}}{\sqrt {\frac {N}{G}}}\right\rfloor =O({\sqrt {N}}).}$

سيؤدي قياس الحالة الآن إلى الحصول على إحدى القيم الصحيحة باحتمالية عالية . نظرًا لأن كل تطبيق لـ${\displaystyle S_{P}}$يتطلب الأمر استعلامًا واحدًا من أوراكل (بافتراض أن أوراكل مُنفذ كبوابة كمومية )، ويمكننا العثور على مدخل جيد باستخدام${\displaystyle O({\sqrt {N}})}$تُحقق استعلامات أوراكل تسارعًا تربيعيًا مقارنةً بأفضل خوارزمية كلاسيكية ممكنة. (تتمثل الطريقة الكلاسيكية للبحث في قاعدة البيانات في تنفيذ الاستعلام لكل${\displaystyle e\in \{0,1,\dots ,N-1\}}$إلى حين إيجاد حل، مما سيكلف${\displaystyle O(N)}$(الاستفسارات.) علاوة على ذلك، يمكننا العثور على جميع${\displaystyle G}$حلول باستخدام${\displaystyle O({\sqrt {GN}})}$استفسارات.

إذا حددنا حجم المجموعة${\displaystyle G}$أولاً، يختزل السيناريو المذكور أعلاه بشكل أساسي إلى بحث غروفر الأصلي .

لنفترض أن عدد المدخلات الصحيحة غير معروف. هدفنا هو تقدير${\displaystyle {\tilde {G}}}$بحيث${\displaystyle (1-\delta )G\leq {\tilde {G}}\leq (1+\delta )G}$للصغار${\displaystyle \delta >0}$يمكننا حل المشكلة.${\displaystyle {\tilde {G}}}$بتطبيق خوارزمية تقدير الطور الكمومي على المؤثر الوحدوي${\displaystyle Q}$.

منذ${\displaystyle e^{2i\theta }}$و${\displaystyle e^{-2i\theta }}$القيمتان الذاتيتان الوحيدتان لـ${\displaystyle Q}$يمكننا أن نجعل متجهاتهم الذاتية المقابلة هي${\displaystyle |\psi _{1}\rangle }$و${\displaystyle |\psi _{2}\rangle }$يمكننا إيجاد القيمة الذاتية${\displaystyle e^{2i\theta }}$ل${\displaystyle |\psi \rangle }$وهو ما يعادل في هذه الحالة تقدير الطور${\displaystyle \theta }$يمكن تحقيق ذلك بتطبيق تحويلات فورييه وعمليات وحدوية مضبوطة، كما هو موضح في خوارزمية تقدير الطور الكمومي. مع التقدير${\displaystyle {\tilde {\theta }}}$، يمكننا أن نقدر${\displaystyle \sin {\theta }}$والذي بدوره يقدر${\displaystyle G}$.

لنفترض أننا نريد تقدير${\displaystyle \theta }$مع حالة بداية عشوائية${\displaystyle |s\rangle }$، بدلاً من المتجهات الذاتية${\displaystyle |\psi _{1}\rangle }$و${\displaystyle |\psi _{2}\rangle }$يمكننا القيام بذلك عن طريق التفكيك${\displaystyle |s\rangle }$إلى توليفة خطية من${\displaystyle |\psi _{1}\rangle }$و${\displaystyle |\psi _{2}\rangle }$ثم تطبيق خوارزمية تقدير الطور.