مشكلة المجموعات الفرعية المخفية

يمكن تعريف تحويل فورييه الكمي بدلالة${\displaystyle \mathrm {Z} _{N}}$، المجموعة الحلقية المضافة من الرتبة${\displaystyle N}$تقديم الشخصية$${\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}$$يُعرَّف تحويل فورييه الكمومي على النحو التالي:$${\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\chi _{j}(k)|k\rangle .}$$علاوة على ذلك، نُعرّف${\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }$يمكن كتابة أي زمرة أبيلية منتهية على شكل حاصل الضرب المباشر لعدة زمر دورية${\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}$في الحاسوب الكمومي، يتم تمثيل ذلك على أنه حاصل ضرب موتر لعدة سجلات ذات أبعاد${\displaystyle N_{1},N_{2},\ldots ,N_{m}}$على التوالي، والتحويل الكمي الإجمالي لفورييه هو${\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}$.

مجموعة الأحرف الخاصة بـ${\displaystyle G}$يشكل مجموعة${\displaystyle {\widehat {G}}}$تُسمى المجموعة الثنائية لـ${\displaystyle G}$لدينا أيضًا مجموعة فرعية${\displaystyle H^{\perp }\leq {\widehat {G}}}$من الحجم${\displaystyle |G|/|H|}$محدد بواسطة$${\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ لجميع }}h\in H\}}$$في كل تكرار للخوارزمية، تُخرج الدائرة الكمومية عنصرًا${\displaystyle g\in G}$مطابق لحرف${\displaystyle \chi _{g}\in H^{\perp }}$و منذ ذلك الحين${\displaystyle \chi _{g}(h)={1}}$للجميع${\displaystyle h\in H}$يساعد ذلك في تحديد ما${\displaystyle H}$يكون.

الخوارزمية كالتالي:

1. ابدأ بالولاية${\displaystyle |0\rangle |0\rangle }$حيث تمثل حالات الأساس للسجل الأيسر كل عنصر من عناصر${\displaystyle G}$، وحالات الأساس للسجل الأيمن هي كل عنصر من عناصر${\displaystyle X}$.
2. أنشئ تراكبًا بين الحالات الأساسية لـ${\displaystyle G}$في السجل الأيسر، مغادرة الولاية${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }$.
3. استعلم عن الدالة${\displaystyle f}$. الحالة بعد ذلك هي${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }$.
4. قم بقياس سجل الإخراج. هذا يعطي بعض النتائج.${\displaystyle f(s)}$بالنسبة للبعض${\displaystyle s\in G}$، ويؤدي إلى انهيار الدولة${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$لأن${\displaystyle f}$لها نفس القيمة لكل عنصر من عناصر المجموعة المشاركة${\displaystyle s+{H}}$نتجاهل سجل الإخراج للحصول على${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }$.
5. قم بإجراء تحويل فورييه الكمي، واحصل على الحالة${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }$.
6. هذه الحالة تساوي${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$والتي يمكن قياسها لمعرفة معلومات حول${\displaystyle H}$.
7. كرر حتى${\displaystyle H}$(أو مجموعة مولدة لـ${\displaystyle H}$يتم تحديد ذلك.

الحالة في الخطوة 5 تساوي الحالة في الخطوة 6 للأسباب التالية:$$\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi \begin{aligned} ...$$أما بالنسبة للمساواة الأخيرة، فنستخدم المتطابقة التالية:

كل قياس للحالة النهائية سيؤدي إلى الحصول على بعض المعلومات حول${\displaystyle H}$بما أننا نعلم ذلك${\displaystyle \chi _{g}(h)=1}$للجميع${\displaystyle h\in H}$.${\displaystyle H}$أو مجموعة مولدة لـ${\displaystyle H}$سيتم إيجادها بعد عدد كثير الحدود من القياسات. سيكون حجم مجموعة التوليد صغيرًا لوغاريتميًا مقارنةً بحجم${\displaystyle G}$. يترك${\displaystyle T}$لنرمز إلى مجموعة مولدة لـ${\displaystyle H}$، معنى${\displaystyle \langle T\rangle =H}$حجم المجموعة الفرعية الناتجة عن${\displaystyle T}$سيتضاعف على الأقل عند إضافة عنصر جديد${\displaystyle t\notin T}$ويضاف إليه ذلك، لأن${\displaystyle H}$و${\displaystyle t+H}$منفصلة ولأن${\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }$لذلك، فإن حجم مجموعة التوليد${\displaystyle |T|}$يرضي$${\displaystyle |T|\leq \log |H|\leq \log |G|}$$وبالتالي، مجموعة مولدة لـ${\displaystyle H}$سيكون من الممكن الحصول عليها في وقت متعدد الحدود حتى لو${\displaystyle G}$حجمه يتزايد بشكل كبير.