الحوسبة الكلاسيكية على الحواسيب الكمومية

سنوجّه الآن انتباهنا نحو تطبيق الخوارزميات الكلاسيكية على الحواسيب الكمومية. سنرى أن أي حوسبة يمكن تنفيذها بدائرة كلاسيكية بوليانية يمكن أيضاً تنفيذها بدائرة كمومية بتكلفة حسابية مقاربة مقاساً بالتدرج التبايني. علاوة على ذلك، يمكن تنفيذ ذلك بطريقة "نظيفة" سيُوصف معناها قريباً، وهو متطلب مهم لاستخدام هذه الحوسبات كروتينات فرعية ضمن حوسبات كمومية أكبر.

محاكاة الدوائر البوليانية بالدوائر الكمومية

تتألف الدوائر البوليانية من بوابات AND وOR وNOT وFANOUT. لمحاكاة الدوائر البوليانية بالدوائر الكمومية، سنبدأ بإظهار كيف يمكن محاكاة كل من هذه البوابات الأربع ببوابات كمومية. بعد ذلك، تحويل أي دائرة بوليانية إلى دائرة كمومية مجرد مسألة محاكاة بوابة بوابة. سنحتاج فقط إلى بوابات NOT وبوابات NOT المضبوطة وبوابات توفولي لتحقيق ذلك، وكلها عمليات حتمية بالإضافة إلى كونها أحادية.

بوابات توفولي

يمكن وصف بوابات توفولي بديلاً بأنها بوابات NOT مضبوطة مضبوطة، ويظهر تأثيرها على حالات القاعدة القياسية كما في الشكل التالي.

مع الأخذ بعين الاعتبار أننا نستخدم اتفاقية ترتيب Qiskit، حيث تُرتَّب الكيوبتات بالأهمية المتزايدة من الأعلى إلى الأسفل، يكون التمثيل المصفوفي لهذه البوابة على النحو التالي:

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

طريقة أخرى للتفكير في بوابات توفولي هي أنها أساساً بوابات استعلام لدالة AND، بمعنى أنها تتبع النمط الذي رأيناه في الدرس السابق لتطبيقات بوابات الاستعلام الأحادية للدوال ذات المدخلات والمخرجات الثنائية.

بوابات توفولي ليست ضمن مجموعة البوابات الافتراضية التي نوقشت سابقاً في الدرس، لكن يمكن بناء بوابة توفولي من بوابات $H$ و$T$ و$T^{\dagger}$ وCNOT على النحو التالي:

محاكاة البوابات البوليانية ببوابات توفولي وNOT المضبوطة وNOT

بوابة توفولي واحدة مقرونة بعدد من بوابات NOT يمكنها تطبيق بوابة AND وOR، ويمكن تطبيق بوابات FANOUT بسهولة باستخدام بوابات NOT المضبوطة كما تقترح المخططات التالية.

في الحالات الثلاث، تدخل الكيوبتات التي تعمل عليها بوابات AND وOR وFANOUT من اليسار كمدخلات، ونحتاج أيضاً إلى كيوبت مساحة عمل واحد يُهيَّأ بالحالة الصفرية لكل منها. تظهر كيوبتات مساحة العمل هذه داخل الصناديق التي تمثل تطبيقات البوابة للإشارة إلى أنها جديدة، وبالتالي جزء من تكلفة هذه التطبيقات.

في بوابتَي AND وOR يبقى لدينا أيضاً كيوبتان إضافيان بالإضافة إلى كيوبت المخرج. على سبيل المثال، داخل الصندوق في المخطط الذي يمثل محاكاة بوابة AND، تبقى الكيوبتان العليا في الحالتين $\vert a\rangle$ و$\vert b\rangle$. تُصوَّر هذه الكيوبتات على أنها تبقى داخل الصناديق لأنها لم تعد مطلوبة وليست جزءاً من المخرج. يمكن تجاهلها في الوقت الراهن، وإن كنا سنعود إليها قريباً.

بوابة NOT البوليانية المتبقية مدرجة في مجموعتنا الافتراضية من البوابات الكمومية، لذا لا نحتاج إلى محاكاة لها.

المحاكاة بوابة بوابة للدوائر البوليانية

لنفترض الآن أن لدينا دائرة بوليانية اعتيادية نسميها $C$، مؤلَّفة من بوابات AND وOR وNOT وFANOUT، ولها $n$ بتاً كمدخل و$m$ بتاً كمخرج. ليكن $t = \operatorname{size}(C)$ عدد البوابات في $C$، ولنُسمِّ $f$ الدالة التي تحسبها $C$، والتي تأخذ الشكل

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

بالنسبة لـ$\Sigma = \{0,1\}$.

الآن لنتأمل ما يحدث حين نمر واحدة بواحدة على بوابات AND وOR وFANOUT في $C$، نستبدل كل منها بالمحاكاة المقابلة الموصوفة أعلاه مع إضافة كيوبتات مساحة العمل المطلوبة. لنسمّ الدائرة الناتجة $R$، ولنرتّب كيوبتات $R$ بحيث تقابل $n$ بتات المدخل في $C$ الكيوبتات الـ$n$ العليا في $R$ وكيوبتات مساحة العمل في الأسفل.

هنا، $k$ هو عدد كيوبتات مساحة العمل المطلوبة — واحد لكل بوابة AND وOR وFANOUT في $C$ — و$g$ دالة بالشكل $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ تصف حالات الكيوبتات المتبقية التي تُنشئها محاكاة البوابات بعد تشغيل $R$. في الشكل، كيوبتات المخرج $f(x)$ في الأعلى والكيوبتات المتبقية التي تخزن $g(x)$ في الأسفل. يمكننا إجبار ذلك على الحدوث إذا أردنا بإعادة ترتيب الكيوبتات باستخدام بوابات SWAP، التي يمكن تطبيقها بثلاث بوابات NOT مضبوطة هكذا:

كما سنرى في القسم التالي، إعادة ترتيب كيوبتات المخرج بهذه الطريقة ليست ضرورية فعلاً، لكن يمكن تنفيذها بسهولة إن اخترنا ذلك.

الدالة $g$ التي تصف الحالات الكلاسيكية للكيوبتات المتبقية تُحدَّد بالدائرة $C$، لكننا في الحقيقة لا نحتاج للقلق كثيراً بشأنها؛ لا يهمنا تحديداً في أي حالة تكون هذه الكيوبتات حين تنتهي الحوسبة. الحرف $g$ يأتي بعد $f$، فهو اسم معقول لهذه الدالة لذلك السبب، لكن ثمة سبب أفضل لاختيار الاسم $g$ — فهو اختصار لكلمة garbage أي قمامة.

تنظيف القمامة

إذا كان اهتمامنا الوحيد هو تقييم الدالة $f$ المحسوبة بدائرة بوليانية معطاة $C$ بدائرة كمومية، فلا نحتاج إلى المضي أبعد من المحاكاة البوابة-بالبوابة المذكورة آنفاً. هذا يعني أنه إضافة إلى مخرج الدالة، سيكون لدينا كومة من القمامة المتبقية.

غير أن هذا لا يكفي إذا أردنا تنفيذ الحوسبات الكلاسيكية كروتينات فرعية ضمن حوسبات كمومية أكبر، لأن كيوبتات القمامة تلك ستُسبِّب مشكلات. ظاهرة التداخل ذات أهمية بالغة للخوارزميات الكمومية، وكيوبتات القمامة يمكنها تدمير أنماط التداخل اللازمة لعمل الخوارزميات الكمومية بشكل صحيح.

لحسن الحظ، تنظيف القمامة ليس بالأمر الصعب. المفتاح هو الاستفادة من حقيقة أن $R$ دائرة كمومية يمكننا تشغيلها بشكل عكسي، ببساطة باستبدال كل بوابة بمعكوسها وتطبيقها بالترتيب العكسي، مما يُعطينا دائرة كمومية للعملية $R^{\dagger}$. بوابات توفولي وCNOT وNOT هي معكوساتها في الواقع، لذا تشغيل $R$ بشكل عكسي هو مجرد تطبيق البوابات بالترتيب المعكوس — لكن بشكل أعم يمكن عكس أي دائرة كمومية كما وُصف للتو.

تحديداً، ما يمكننا فعله هو إضافة $m$ كيوبتاً إضافياً (مع تذكر أن الدالة $f$ لها $m$ بتاً كمخرج)، استخدام بوابات CNOT لنسخ مخرج $R$ على هذه الكيوبتات، وعكس $R$ لتنظيف القمامة. يوضح الشكل التالي الدائرة الناتجة ويصف تأثيرها على حالات القاعدة القياسية.

إذا وضعنا صندوقاً حول الدائرة كاملة وسمّيناها $Q$، ستبدو هكذا:

بما أن $C$ تحتوي على $t$ بوابة، فإن الدائرة $Q$ ستحتوي على $O(t)$ بوابة.

إذا تجاهلنا كيوبتات مساحة العمل الـ$k$ الإضافية، ما لدينا هو دائرة $Q$ تعمل تماماً كبوابة استعلام للدالة $f$. إذا أردنا ببساطة حساب الدالة $f$ على سلسلة $x$ ما، يمكننا ضبط $y = 0^m$ وستظهر القيمة الناتجة $f(x)$ على أسفل $m$ كيوبتاً — أو يمكننا تغذية حالة مختلفة إلى أسفل $m$ كيوبتاً إن أردنا (ربما للاستفادة من الركل الطوري، كما في خوارزمية دويتش أو دويتش-يوزسا).

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

لاحظ أن كيوبتات مساحة العمل ضرورية لجعل هذه العملية تعمل، لكنها تعود إلى حالاتها الابتدائية بعد تنفيذ الدائرة المجمَّعة. هذا يتيح استخدام هذه الكيوبتات مجدداً ككيوبتات مساحة عمل لأغراض أخرى. هناك أيضاً استراتيجيات معروفة لتقليل عدد كيوبتات مساحة العمل المطلوبة (على حساب جعل الدوائر أكبر)، لكننا لن نناقش تلك الاستراتيجيات هنا.

تطبيق الدوال القابلة للعكس

البناء الموصوف للتو يتيح لنا محاكاة أي دائرة بوليانية بدائرة كمومية بصورة خالية من القمامة. إذا كانت $C$ دائرة بوليانية تطبق دالة $f:\Sigma^n \rightarrow \Sigma^m$، نحصل على دائرة كمومية $Q$ تعمل على النحو التالي على حالات القاعدة القياسية:

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

العدد $k$ يُشير إلى إجمالي عدد كيوبتات مساحة العمل المطلوبة. هذا كافٍ لأغراض هذه الدورة، لكن يمكن أخذ هذه المنهجية خطوة أبعد حين تكون الدالة $f$ نفسها قابلة للعكس.

لنكن دقيقين، لنفترض أن الدالة $f$ تأخذ الشكل $f:\Sigma^n \rightarrow \Sigma^n$، ولنفترض أيضاً أنه توجد دالة $f^{-1}$ بحيث $f^{-1}(f(x)) = x$ لكل $x\in\Sigma^n$ (وهي ضرورياً فريدة حين توجد). هذا يعني أن العملية التي تُحوِّل $\vert x \rangle$ إلى $\vert f(x) \rangle$ لكل $x\in\Sigma^n$ أحادية، لذا قد نأمل في بناء دائرة كمومية تطبق العملية الأحادية المُعرَّفة بـ

$$U \vert x \rangle = \vert f(x) \rangle$$

لكل $x\in\Sigma^n$.

لنكن واضحين، كون هذه العملية أحادية يعتمد على قابلية $f$ للعكس — فهي ليست أحادية حين لا تكون $f$ قابلة للعكس. بتجاهل كيوبتات مساحة العمل، $U$ تختلف عن العملية التي تطبقها الدائرة $Q$ لأننا لا نحتفظ بنسخة من المدخل ولا نجري XOR عليها مع سلسلة اعتباطية، بل نحن نستبدل $x$ بـ$f(x)$.

السؤال هو: حين تكون $f$ قابلة للعكس، هل يمكننا تحقيق ذلك؟

الجواب نعم، شريطة أن نُتاح لنا استخدام كيوبتات مساحة عمل، وإضافة إلى امتلاكنا دائرة بوليانية تحسب $f$، نمتلك أيضاً دائرة تحسب $f^{-1}$. إذن هذا ليس اختصاراً لعكس الدوال حسابياً حين لا نعرف كيف نفعل ذلك مسبقاً! يوضح المخطط التالي كيف يمكن تحقيق ذلك بتركيب دائرتين كموميتين $Q_f$ و$Q_{f^{-1}}$، تُحصلان بصورة مستقلة للدالتين $f$ و$f^{-1}$ بالطريقة الموصوفة أعلاه، إضافة إلى $n$ بوابة تبادل، مع أخذ $k$ بحيث يكون الحد الأقصى لعدد كيوبتات مساحة العمل المطلوبة من $Q_f$ و$Q_{f^{-1}}$.