خوارزمية سايمون

خوارزمية سايمون هي خوارزمية استعلام كمومية لمسألة تُعرف بـ مسألة سايمون. هذه مسألة وعد (promise problem) تشبه في طابعها مسألتَي دويتش-جوزا وبرنشتاين-فازيراني، لكنها تختلف عنهما في التفاصيل.

تتميز خوارزمية سايمون بأنها تحقق ميزة أسية للحوسبة الكمومية على الخوارزميات الكلاسيكية (بما فيها الاحتمالية)، كما أن الأسلوب الذي تستخدمه ألهم بيتر شور في اكتشافه خوارزمية كمومية فعّالة لتحليل الأعداد إلى عواملها الأولية.

مسألة سايمون

دالة الإدخال في مسألة سايمون تأخذ الشكل

$$f:\Sigma^n \rightarrow \Sigma^m$$

لأعداد صحيحة موجبة $n$ و $m.$ يمكن الاقتصار على حالة $m = n$ لتبسيط الأمر، لكن لا فائدة كبيرة من هذا الافتراض — فخوارزمية سايمون وتحليلها تبقيان في جوهرهما متطابقتين في الحالتين.

مسألة سايمون

المدخل: دالة $f:\Sigma^n \rightarrow \Sigma^m$
الوعد: يوجد سلسلة $s\in\Sigma^n$ بحيث $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ لكل $x,y\in\Sigma^n$
المخرج: السلسلة $s$

سنشرح الوعد بمزيد من التفصيل بعد قليل، لكن الجدير بالذكر أن هذا الوعد يفرض على $f$ بنية خاصة جداً — فمعظم الدوال لن تستوفيه. من المناسب أيضاً الإشارة إلى أن هذه المسألة لا تستهدف تطبيقاً عملياً محدداً؛ بل هي مسألة مصممة بعناية لتكون سهلة على الحواسيب الكمومية وصعبة على الحواسيب الكلاسيكية.

ثمة حالتان رئيسيتان: الأولى أن تكون $s$ هي السلسلة الصفرية الكاملة $0^n$، والثانية أن تكون $s$ غير ذلك.

• الحالة الأولى: $s=0^n.$ إذا كانت $s$ هي السلسلة الصفرية، فيمكن تبسيط عبارة "إذا وفقط إذا" في الوعد لتصبح $[f(x) = f(y)] \Leftrightarrow [x = y].$ وهذا يعادل كون $f$ دالة واحد-إلى-واحد (أحادية الاتجاه).

• الحالة الثانية: $s\neq 0^n.$ إذا لم تكن $s$ هي السلسلة الصفرية، فإن استيفاء الوعد لهذه السلسلة يعني أن $f$ هي دالة اثنين-إلى-واحد، أي أن لكل سلسلة إخراج ممكنة من $f$ اثنتين فقط من سلاسل الإدخال تُنتجانها. علاوة على ذلك، يجب أن تأخذ هاتان السلسلتان شكل $w$ و $w \oplus s$ لسلسلة ما $w.$

المهم أن ندرك أنه لا يمكن أن تكون هناك إلا سلسلة $s$ واحدة تعمل إذا استُوفي الوعد، أي أن الإجابة الصحيحة دائماً فريدة للدوال التي تستوفي الوعد.

إليك مثالاً على دالة من الشكل $f:\Sigma^3 \rightarrow \Sigma^5$ تستوفي الوعد للسلسلة $s = 011.$

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

يوجد $8$ سلاسل إدخال مختلفة و $4$ سلاسل إخراج مختلفة، تظهر كل منها مرتين — وهذا يجعلها دالة اثنين-إلى-واحد. فضلاً عن ذلك، لأي سلسلتَي إدخال مختلفتين تنتجان نفس سلسلة الإخراج، نجد أن XOR البتي لهاتين السلسلتين يساوي $011$، وهو ما يعادل القول بأن كلاً منهما تساوي الأخرى بعد XOR مع $s.$

لاحظ أن الشيء الوحيد المهم في سلاسل الإخراج الفعلية هو ما إذا كانت متطابقة أو مختلفة لاختيارات مختلفة من سلاسل الإدخال. على سبيل المثال، في المثال أعلاه، ثمة أربع سلاسل ($10011,$ $00101,$ $00001,$ و $11010$) تظهر كمخرجات لـ $f.$ يمكننا استبدال هذه السلاسل الأربع بسلاسل مختلفة، طالما أنها متمايزة، ولن يتغير الحل الصحيح $s = 011.$

وصف الخوارزمية

إليك مخطط دائرة كمومية يمثل خوارزمية سايمون.

توضيحاً، يوجد $n$ كيوبت في الأعلى تؤثر عليها بوابات هادامار، و $m$ كيوبت في الأسفل تدخل مباشرة إلى بوابة الاستعلام. تبدو الخوارزمية مشابهة جداً للخوارزميات التي ناقشناها سابقاً في الدرس، لكن هذه المرة لا يوجد ركل طور (phase kickback)؛ إذ تدخل الـ $m$ كيوبت السفلية جميعها إلى بوابة الاستعلام في الحالة $\vert 0\rangle.$

حل مسألة سايمون باستخدام هذه الدائرة يستلزم في الواقع تشغيلها عدة مرات مستقلة يتبعها خطوة معالجة كلاسيكية، سنصفها لاحقاً بعد تحليل سلوك الدائرة.

التحليل

يبدأ تحليل خوارزمية سايمون بطريقة مشابهة لخوارزمية دويتش-جوزا. بعد تطبيق الطبقة الأولى من بوابات هادامار على الـ $n$ كيوبت العليا، تصبح الحالة

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

عند تطبيق $U_f$، تُضاف XOR خرج الدالة $f$ على الحالة الصفرية للـ $m$ كيوبت السفلية، لتصبح الحالة

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

عند تطبيق الطبقة الثانية من بوابات هادامار، نحصل على الحالة التالية باستخدام نفس صيغة تأثير طبقة بوابات هادامار كما سبق.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

عند هذه النقطة، يختلف التحليل عن تحليل الخوارزميات السابقة في هذا الدرس.

نحن مهتمون باحتمال أن تُفضي القياسات إلى كل سلسلة ممكنة $y\in\Sigma^n.$ باستخدام قواعد تحليل القياسات الموضحة في درس الأنظمة المتعددة من دورة أساسيات المعلومات الكمومية، نجد أن الاحتمال $p(y)$ للحصول على السلسلة $y$ يساوي

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

للتعامل بشكل أفضل مع هذه الاحتمالات، نحتاج إلى قدر بسيط من الرموز والمصطلحات. أولاً، مجال القيم (range) للدالة $f$ هو المجموعة التي تحتوي على جميع سلاسل مخرجاتها.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

ثانياً، لكل سلسلة $z\in\operatorname{range}(f)$، يمكن التعبير عن مجموعة جميع سلاسل الإدخال التي تجعل الدالة تُخرج $z$ بالصيغة $f^{-1}(\{z\}).$

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

تُسمى المجموعة $f^{-1}(\{z\})$ الصورة العكسية (preimage) لـ $\{z\}$ تحت $f.$ يمكن تعريف الصورة العكسية تحت $f$ لأي مجموعة بالمثل — فهي مجموعة جميع العناصر التي تُعين عليها $f$ إلى تلك المجموعة. (لا ينبغي الخلط بين هذه الصيغة وعكس الدالة $f$، الذي قد لا يوجد. كون الوسيط في الجانب الأيسر هو المجموعة $\{z\}$ وليس العنصر $z$ هو ما يُميّز الحالتين.)

باستخدام هذه الصياغة، يمكننا تقسيم المجموع في تعبيرنا للاحتمالات أعلاه للحصول على

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

تُمثَّل كل سلسلة $x\in\Sigma^n$ مرة واحدة بالضبط في المجموعين — نحن نضع هذه السلاسل في دلاء منفصلة حسب سلسلة الإخراج $z = f(x)$ التي تُنتجها عند تقييم الدالة $f$، ثم نجمع على كل دلو على حدة.

يمكننا الآن تقييم مربع القاعدة الإقليدية للحصول على

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

لتبسيط هذه الاحتمالات أكثر، لنلقِ نظرة على القيمة

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

لاختيار عشوائي من $z\in\operatorname{range}(f).$

إذا كان $s = 0^n$، فإن $f$ هي دالة واحد-إلى-واحد وهناك دائماً عنصر واحد فقط $x\in f^{-1}(\{z\})$، لكل $z\in\operatorname{range}(f).$ قيمة التعبير $(1)$ في هذه الحالة هي $1$.

إذا كان $s\neq 0^n$ من ناحية أخرى، فإن هناك سلسلتين بالضبط في المجموعة $f^{-1}(\{z\}).$ بدقة، إذا اخترنا $w\in f^{-1}(\{z\})$ لتكون إحدى هاتين السلسلتين، فإن السلسلة الأخرى يجب أن تكون $w \oplus s$ وفقاً للوعد في مسألة سايمون. باستخدام هذه الملاحظة يمكننا تبسيط $(1)$ كما يلي.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

اتضح إذن أن القيمة $(1)$ مستقلة عن الاختيار المحدد لـ $z\in\operatorname{range}(f)$ في كلتا الحالتين.

يمكننا الآن استكمال التحليل بدراسة نفس الحالتين السابقتين كل على حدة.

• الحالة الأولى: $s = 0^n.$ في هذه الحالة $f$ هي دالة واحد-إلى-واحد، إذن هناك $2^n$ سلسلة $z\in\operatorname{range}(f)$، ونحصل على

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  بعبارة أخرى، تُنتج القياسات سلسلة $y\in\Sigma^n$ مختارة بالتساوي عشوائياً.

• الحالة الثانية: $s \neq 0^n.$ في هذه الحالة $f$ هي دالة اثنين-إلى-واحد، إذن هناك $2^{n-1}$ عنصراً في $\operatorname{range}(f).$ باستخدام الصيغة أعلاه نستنتج أن احتمال قياس كل $y\in\Sigma^n$ هو

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  بعبارة أخرى، نحصل على سلسلة مختارة بالتساوي عشوائياً من المجموعة $\{y\in\Sigma^n : y \cdot s = 0\}$، التي تحتوي على $2^{n-1}$ سلسلة. (بما أن $s\neq 0^n$، فإن نصف السلاسل الثنائية بالضبط بطول $n$ لها حاصل ضرب نقطي ثنائي يساوي $1$ مع $s$ والنصف الآخر يساوي $0$، كما لاحظنا سابقاً في تحليل خوارزمية دويتش-جوزا لمسألة برنشتاين-فازيراني.)

المعالجة الكلاسيكية اللاحقة

نعرف الآن ما هي احتمالات نتائج القياس الممكنة عند تشغيل الدائرة الكمومية لخوارزمية سايمون. هل هذا كافٍ لتحديد $s$؟

الجواب نعم، شريطة أن نكون مستعدين لتكرار العملية عدة مرات وقبول احتمال فشل صغير، يمكن تقليصه بتشغيل الدائرة عدداً كافياً من المرات. الفكرة الأساسية هي أن كل تشغيل للدائرة يمدنا بأدلة إحصائية حول $s$، ويمكننا استخدام هذه الأدلة لإيجاد $s$ باحتمال مرتفع جداً إذا شغّلنا الدائرة عدداً كافياً من المرات.

لنفترض أننا نشغّل الدائرة بشكل مستقل $k$ مرة، حيث $k = n + 10.$ لا يوجد شيء مميز في هذا العدد تحديداً — يمكن اختيار $k$ أكبر أو أصغر حسب احتمال الفشل المقبول، كما سنرى. اختيار $k = n + 10$ سيضمن احتمالاً يزيد على $99.9$% في استرداد $s.$

بتشغيل الدائرة $k$ مرة، نحصل على سلاسل $y^1,...,y^{k} \in \Sigma^n.$ المؤشرات العلوية هنا جزء من أسماء هذه السلاسل وليست أسساً أو مؤشرات للبتات، لذا لدينا

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

نُشكّل الآن مصفوفة $M$ بـ $k$ صفاً و $n$ عموداً باتخاذ بتات هذه السلاسل إدخالات ذات قيم ثنائية.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

الآن، لا نعرف ما هي $s$ في هذه المرحلة — هدفنا إيجاد هذه السلسلة. لكن تخيّل للحظة أننا نعرف السلسلة $s$، وأننا نُشكّل متجهاً عمودياً $v$ من بتات السلسلة $s = s_{n-1} \cdots s_0$ كما يلي.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

إذا أجرينا ضرب المصفوفة بالمتجه $M v$ بالتحويل modulo $2$ — أي نُجري الضرب بالطريقة المعتادة ثم نأخذ باقي قسمة عناصر النتيجة على $2$ — نحصل على متجه الأصفار.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

أي أن السلسلة $s$ ستكون دائماً عنصراً في الفضاء الصفري (null space) للمصفوفة $M$ معاملَةً كمتجه عمودي $v$ كما وصفنا، شريطة إجراء الحسابات بالتحويل modulo $2$. وهذا صحيح في حالتَي $s = 0^n$ و $s\neq 0^n$ على حد سواء. بدقة أكبر، متجه الأصفار موجود دائماً في الفضاء الصفري لـ $M$، وينضم إليه المتجه الذي عناصره بتات $s$ في حالة $s\neq 0^n.$

السؤال المتبقي هو ما إذا كانت توجد متجهات أخرى في الفضاء الصفري لـ $M$ غير تلك المقابلة لـ $0^n$ و $s$. الإجابة هي أن هذا يصبح أقل احتمالاً كلما زاد $k$ — وإذا اخترنا $k = n + 10$، لن يحتوي الفضاء الصفري لـ $M$ على متجهات أخرى بخلاف تلك المقابلة لـ $0^n$ و $s$ باحتمال يزيد على $99.9$%. بشكل عام، إذا استبدلنا $k = n + 10$ بـ $k = n + r$ لاختيار عشوائي من عدد صحيح موجب $r$، فإن احتمال انفراد المتجهين المقابلين لـ $0^n$ و $s$ في الفضاء الصفري لـ $M$ هو على الأقل $1 - 2^{-r}.$

باستخدام الجبر الخطي، يمكن حساب وصف الفضاء الصفري لـ $M$ بالتحويل modulo $2$ بكفاءة. تحديداً، يمكن فعل ذلك باستخدام الحذف الغاوسي (Gaussian elimination)، الذي يعمل بنفس الطريقة عند إجراء الحساب modulo $2$ كما هو الحال مع الأعداد الحقيقية أو المركبة. طالما أن المتجهين المقابلين لـ $0^n$ و $s$ هما وحدهما في الفضاء الصفري لـ $M$، وهو ما يحدث باحتمال مرتفع، يمكننا استنتاج $s$ من نتائج هذا الحساب.

الصعوبة الكلاسيكية

كم استعلاماً تحتاج خوارزمية استعلام كلاسيكية لحل مسألة سايمون؟ الجواب: كثيراً جداً بوجه عام.

ثمة عبارات دقيقة مختلفة يمكن صياغتها حول الصعوبة الكلاسيكية لهذه المسألة، وإليك واحدة منها. إذا كان لدينا أي خوارزمية استعلام احتمالية أجرت أقل من $2^{n/2 - 1} - 1$ استعلاماً — وهو عدد استعلامات أسي في $n$ — فستفشل في حل مسألة سايمون باحتمال لا يقل عن $1/2.$

أحياناً يكون إثبات نتائج استحالة من هذا القبيل أمراً صعباً للغاية، لكن هذا الإثبات ليس صعباً كثيراً ويمكن تقديمه عبر تحليل احتمالي أولي. لكننا هنا سنكتفي بالنظرة العامة خلف الحدس الأساسي.

نحن نحاول إيجاد السلسلة المخفية $s$، لكن طالما لم نستعلم عن الدالة بسلسلتين لهما نفس قيمة الإخراج، ستحصل على معلومات محدودة جداً حول $s$. بصورة بديهية، كل ما ستتعلمه هو أن السلسلة المخفية $s$ ليست XOR أي سلسلتين متمايزتين استُعلم عنهما. وإذا كان الاستعلام عن أقل من $2^{n/2 - 1} - 1$ سلسلة، ستبقى هناك خيارات كثيرة لـ $s$ لم يُستبعَد أيٌّ منها لأن الأزواج غير كافية لذلك. هذا ليس إثباتاً رسمياً، بل الفكرة الأساسية فحسب.

إذن، خلاصة القول، تمنحنا خوارزمية سايمون ميزة لافتة للكم على الكلاسيك في نموذج الاستعلام. تحديداً، تحل خوارزمية سايمون مسألة سايمون بعدد استعلامات خطي في عدد بتات الإدخال $n$ للدالة، بينما تحتاج أي خوارزمية كلاسيكية، حتى لو كانت احتمالية، إلى عدد استعلامات أسي في $n$ لحل مسألة سايمون باحتمال نجاح معقول.