مشكلة سيمون

الدالة التالية هي مثال على دالة تحقق الخاصية المطلوبة لـ${\displaystyle n=3}$:

${\displaystyle x}$	${\displaystyle f(x)}$
٠٠٠	101
001	010
010	٠٠٠
011	110
100	٠٠٠
101	110
110	101
111	010

في هذه الحالة،${\displaystyle s=110}$(أي الحل). كل مخرجات${\displaystyle f}$يحدث ذلك مرتين، ويكون ناتج عملية XOR الثنائية بين سلسلتي الإدخال المقابلتين لأي ناتج معين مساوياً لـ${\displaystyle s=110}$.

على سبيل المثال، سلاسل الإدخال${\displaystyle 010}$و${\displaystyle 100}$كلاهما مُحددان (بواسطة${\displaystyle f}$) إلى نفس سلسلة الإخراج${\displaystyle 000}$. إنه،${\displaystyle {\displaystyle f(010)=000}}$و${\displaystyle {\displaystyle f(100)=000}}$بتطبيق عملية XOR على 010 و100 نحصل على 110، أي${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$

${\displaystyle s=110}$يمكن التحقق من ذلك أيضًا باستخدام سلسلتي الإدخال 001 و111 اللتين يتم تعيينهما (بواسطة f) إلى سلسلة الإخراج نفسها 010. بتطبيق عملية XOR على 001 و111 نحصل على 110، أي${\displaystyle 001\oplus 111=110=s}$وهذا يعطي نفس الحل${\displaystyle s=110}$كما كان من قبل.

في هذا المثال، الدالة f هي بالفعل دالة ثنائية التقابل حيث${\displaystyle {\displaystyle s\neq 0^{n}}}$.

من البديهي أن هذه مشكلة صعبة الحل بالطريقة "الكلاسيكية"، حتى مع استخدام العشوائية وقبول احتمال خطأ ضئيل. والسبب وراء هذه الصعوبة بسيط نسبياً: إذا أردت حل المشكلة بالطريقة الكلاسيكية، فأنت بحاجة إلى إيجاد مدخلين مختلفين.${\displaystyle x}$و${\displaystyle y}$والتي${\displaystyle f(x)=f(y)}$ليس بالضرورة أن يكون هناك أي هيكل في الوظيفة${\displaystyle f}$سيساعدنا ذلك في العثور على مدخلين من هذا القبيل: وبشكل أكثر تحديدًا، يمكننا اكتشاف شيء ما حول${\displaystyle f}$(أو ما يفعله) فقط عندما نحصل على نفس المخرجات لمدخلين مختلفين. على أي حال، سنحتاج إلى التخمين.${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$مدخلات مختلفة قبل أن يكون من المحتمل العثور على زوج منها${\displaystyle f}$يُنتج نفس الناتج، كما هو الحال في مسألة عيد الميلاد . لأنه، بالطريقة التقليدية، لإيجاد قيمة s بيقين 100%، سيتطلب الأمر التحقق.${\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}$باستخدام المدخلات، تسعى مشكلة سيمون إلى إيجاد s باستخدام استعلامات أقل من هذه الطريقة الكلاسيكية.

الدائرة الكمومية (انظر الصورة) هي تطبيق للجزء الكمومي من خوارزمية سيمون. يستخدم الروتين الكمومي للخوارزمية تحويل هادامارد.$${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$$أين${\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}$، أين${\displaystyle \oplus }$يشير إلى عملية XOR.

أولاً، تبدأ الخوارزمية بسجلين، يتم تهيئتهما إلى${\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}$ثم نطبق تحويل هادامارد على السجل الأول، مما يعطي الحالة

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}$

استعلم من العرافة${\displaystyle U_{f}}$للحصول على الولاية

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle }$.

قم بتطبيق تحويل هادامارد آخر على السجل الأول. سيؤدي هذا إلى إنتاج الحالة

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}$

وأخيرًا، نقيس السجل الأول (تعمل الخوارزمية أيضًا إذا تم قياس السجل الثاني قبل الأول، ولكن هذا غير ضروري). احتمال قياس حالة ما${\displaystyle |j\rangle }$يكون$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}$$ويرجع ذلك إلى حقيقة أن أخذ مقدار هذا المتجه وتربيعه يجمع كل احتمالات جميع القياسات الممكنة للسجل الثاني التي يجب أن يكون السجل الأول فيها هو${\displaystyle |j\rangle }$هناك حالتان لقياسنا:

1. ${\displaystyle s=0^{n}}$و${\displaystyle f}$هو واحد لواحد.
2. ${\displaystyle s\neq 0^{n}}$و${\displaystyle f}$نسبة اثنين إلى واحد.

في الحالة الأولى،$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}$$لأنه في هذه الحالة،${\displaystyle f}$هو علاقة واحد لواحد، مما يعني أن نطاق${\displaystyle f}$يكون${\displaystyle \{0,1\}^{n}}$وهذا يعني أن عملية الجمع تشمل كل متجه أساسي. أما في الحالة الثانية، فلاحظ وجود سلسلتين،${\displaystyle x_{1}}$و${\displaystyle x_{2}}$بحيث${\displaystyle f(x_{1})=f(x_{2})=z}$، أين${\displaystyle z\in \mathrm {range} (f)}$. هكذا،$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}$$علاوة على ذلك، بما أن${\displaystyle x_{1}\oplus x_{2}=s}$،${\displaystyle x_{2}=x_{1}\oplus s}$وهكذا$${\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}$$أصبح من السهل الآن حساب قيمة هذا التعبير. تذكر أننا نقيس${\displaystyle j}$. متى${\displaystyle j\cdot s=1}$إذاً، سيتم تقييم هذا التعبير إلى${\displaystyle 0}$ومتى${\displaystyle j\cdot s=0}$إذن، سيكون هذا التعبير${\displaystyle 2^{-n+1}}$.

وهكذا، سواء عندما${\displaystyle s=0^{n}}$ومتى${\displaystyle s\neq 0^{n}}$قياساتنا${\displaystyle j}$يرضي${\displaystyle j\cdot s=0}$.

نقوم بتشغيل الجزء الكمومي من الخوارزمية حتى نحصل على قائمة مستقلة خطيًا من سلاسل البتات${\displaystyle y_{1},\ldots ,y_{n-1}}$وكل${\displaystyle y_{k}}$يرضي${\displaystyle y_{k}\cdot s=0}$وبالتالي، يمكننا حل نظام المعادلات هذا بكفاءة بالطريقة الكلاسيكية لإيجاد${\displaystyle s}$.

احتمال أن${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$الاستقلال الخطي هو على الأقل$${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }$$بمجرد أن نحل نظام المعادلات، ونتوصل إلى حل${\displaystyle s'}$يمكننا اختبار ما إذا${\displaystyle f(0^{n})=f(s')}$إذا كان هذا صحيحًا، فإننا نعلم${\displaystyle s'=s}$، منذ${\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}$إذا كان الأمر كذلك${\displaystyle f(0^{n})\neq f(s')}$إذن هذا يعني أن${\displaystyle s=0^{n}}$، و${\displaystyle f(0^{n})\neq f(s')}$منذ${\displaystyle f}$هو واحد لواحد.

يمكننا تكرار خوارزمية سيمون عددًا ثابتًا من المرات لزيادة احتمالية النجاح بشكل تعسفي، مع الحفاظ على نفس التعقيد الزمني.

لنفترض أبسط مثال للخوارزمية، مع${\displaystyle n=1}$في هذه الحالة، يؤدي تطوير حالة الإدخال من خلال بوابة هادامارد والنتيجة المرجعية إلى الحالة (حتى إعادة التطبيع):

${\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}$

لو${\displaystyle s=1}$، إنه،${\displaystyle f(0)=f(1)}$ثم إن قياس السجل الثاني يعطي النتيجة دائمًا${\displaystyle |f(0)\rangle }$ويؤدي ذلك دائمًا إلى انهيار السجل الأول إلى الحالة (حتى إعادة التطبيع):

${\displaystyle |0\rangle +|1\rangle .}$

وبالتالي، فإن تطبيق معادلة هادامارد وقياس السجل الأول يعطي النتيجة دائمًا.${\displaystyle |0\rangle }$من ناحية أخرى، إذا${\displaystyle f}$أي أنها علاقة واحد لواحد.${\displaystyle s=0}$ثم قياس السجل الأول بعد هادامارد الثاني يمكن أن يؤدي إلى كليهما${\displaystyle |0\rangle }$و${\displaystyle |1\rangle }$باحتمالية متساوية.

نتعافى${\displaystyle s}$من نتائج القياس من خلال النظر فيما إذا كنا نقيس دائمًا${\displaystyle |0\rangle }$وفي هذه الحالة${\displaystyle s=1}$أو قمنا بقياس كليهما${\displaystyle |0\rangle }$و${\displaystyle |1\rangle }$باحتمالية متساوية، وفي هذه الحالة نستنتج أن${\displaystyle s=0}$ستفشل هذه الخطة إذا${\displaystyle s=0}$لكننا مع ذلك كنا نجد النتيجة دائمًا${\displaystyle |0\rangle }$لكن احتمال وقوع هذا الحدث هو${\displaystyle 2^{-N}}$مع${\displaystyle N}$عدد القياسات التي تم إجراؤها، وبالتالي يمكن جعلها صغيرة بشكل كبير عن طريق زيادة الإحصائيات.

لننظر الآن في الحالة مع${\displaystyle n=2}$ينتج عن الجزء الأولي من الخوارزمية الحالة التالية (حتى إعادة التطبيع):$${\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}$$لو${\displaystyle s=(00)}$، معنى${\displaystyle f}$إذا كانت دالة حقنية، فإن إيجاد${\displaystyle |f(x)\rangle }$في السجل الثاني، يتم دائمًا دمج السجل الأول إلى${\displaystyle |x\rangle }$للجميع${\displaystyle x\in \{0,1\}^{2}}$بمعنى آخر، بتطبيق بوابات هادامارد وقياس السجل الأول، يتم تسجيل النتائج الأربع.${\displaystyle 00,01,10,11}$وبالتالي يتم العثور عليهم باحتمالية متساوية.

لنفترض من ناحية أخرى${\displaystyle s\neq (00)}$، على سبيل المثال،${\displaystyle s=(01)}$ثم القياس${\displaystyle |f(00)\rangle }$في السجل الثاني، يتم دمج السجل الأول مع السجل الأصلي.${\displaystyle |00\rangle +|10\rangle }$وبشكل أعم، القياس${\displaystyle |f(xy)\rangle }$أعطِ${\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}$في السجل الأول. وبالتالي، فإن تطبيق بوابات هادامارد والقياس على السجل الأول يمكن أن يؤدي إلى النتائج التالية${\displaystyle 00}$و${\displaystyle 10}$باحتمالات متساوية.

وينطبق منطق مماثل على الحالات الأخرى: إذا${\displaystyle s=(10)}$إذن، النتائج المحتملة هي${\displaystyle 00}$و${\displaystyle 01}$بينما إذا${\displaystyle s=(11)}$النتائج المحتملة هي${\displaystyle 00}$و${\displaystyle 11}$، بما يتوافق مع${\displaystyle j\cdot s=0}$القاعدة التي تمت مناقشتها في الحالة العامة.

للتعافي${\displaystyle s}$وبالتالي، نحتاج فقط إلى التمييز بين هذه الحالات الأربع، وجمع إحصاءات كافية لضمان أن احتمال الخطأ في توزيع احتمالية نتيجة ما هو توزيع احتمالية نتيجة أخرى صغير بما فيه الكفاية.