Quantum Circuits for the Metropolis-Hastings Algorithm

ملخص تقني: الدوائر الكمومية لخوارزمية ميتروبوليس-هيستينجز

بيان المشكلة
تُعد خوارزمية ميتروليس-هيستينجز (MH) حجر الزاوية في طرق مونت كارلو بسلاسل ماركوف (MCMC)، وتُستخدم لأخذ عينات من التوزيعات الاحتمالية في مجالات تتراوح من الديناميكا الجزيئية إلى تعلم الآلة. وبينما توفر تكميم سيجديدي (Szegedy's quantization) لسلاسل ماركوف العكوس تسريعاً تربيعياً نظرياً في زمن الخلط عبر تضخيم الفجوة الطيفية، فإن التنفيذ العملي على الحواسيب الكمومية القريبة من المدى والمقاومة للأخطاء يواجه عقبات كبيرة. تتطلب الطرق العامة الحالية لتنفيذ المشية الكمومية (quantum walk) الحساب المتماسك لاحتمالات الانتقال (احتمالات الرفض) لنموذج ماركوف الأساسي. وهذا يستلزم روتينيات حسابية عكوسة تتناسب مع تعقيد الحساب، مما يؤدي إلى عدد مفرط من الكيوبتات والعمليات المنطقية. هذا العبء الإضافي يعد مشكلة خاصة في خوارزميات MH، حيث يمكن أن يتضمن حساب احتمالات الرفض جمع العديد من الحدود، مما قد يبطل التسريع الكمومي. علاوة على ذلك، فإن خطوة "النسيان" في MH الكلاسيكية (رفض مقترح والعودة إلى الحالة السابقة) هي عملية غير قابلة للعكس، مما يجعل المحاكاة الوحدوية المباشرة صعبة دون هياكل حوسبة عكوسة مساعدة.

المنهجية
يقترح المؤلفون بناءً جديداً للمشية الكمومية لسيجديدي يلتزم بمنطق المقترح-القبول الكلاسيكي دون الحاجة إلى حساب متماسك لاحتمالات الرفض. يتضمن المنهج الأساسي ثلاثة مكونات رئيسية:

1. نموذج ماركوف مزدوج على فضاء حالة ممتد: بدلاً من العمل على فضاء الحالة $S$، يعرّف المؤلفون نموذج ماركوف مزدوجاً على فضاء الحواف $S^2$ (أزواج من الحالات $(x, y)$). في هذا الفضاء الممتد، يمثل "الذيل" $x$ الحالة الحالية، ويمثل "الرأس" $y$ إما الحالة السابقة (في حالة القبول) أو المقترح المرفوض (في حالة الرفك). هذا الامتداد يجعل عملية الرفض قابلة للعكس: فالرفض ببساطة يقوم بتحديث الرأس إلى المقترح المرفوض بدلاً من محو المعلومات.
2. ترميزات الوحدة المسقطة (PUEs): يعتمد البناء على أوراكلين (oracles): $O_T$ لنموذج المقترح و $O_A$ لمصفوفة احتمال القبول. يبني المؤلفون مؤثرات الخطوة الكمومية للنموذج المزدوج $P = TA$ وعكسه الزمني $P^\star = AT$ باستخدام هذه الأوراكل. ومن الأهمية بمكان أن هذه المؤثرات تعمل على عدد ثابت من السجلات ولا تقوم بإجراء عمليات حسابية على سجلات الكيوبت لحساب احتمالات الانتقال.
3. الهرمتية (Hermitianization) والمشية المكممة: بما أن النموذج المزدوج $P$ غير قابل للعكس بشكل عام، يستخدم المؤلفون إجراء هرمتة لدمج ترميزات $P$ و $P^\star$ في ترميز وحدة مسقط متماثل (SPUE) واحد. يسمح هذا بتطبيق نظرية المشية المكممة (qubitized-walk spectral theorem). يتم بناء مؤثر المشية $W$ الناتج باستخدام عدد ثابت من الاستدعاءات لأوراكل $O_T, O_A$ ومرافقاتهما.

المساهمات الرئيسية

• ترميز عكوس بدون حسابات: تقدم الورقة أول تكميم لسيجديدي لنماذج MH يتجنب الحساب المتماسك لعناصر المصفوفة أو احتمالات الانتقال. وقد حققت ذلك من خلال توسيع فضاء الحالة ليشمل سجلاً للذاكرة للمقترحات المرفوضة، مما يجعل العملية وحدوية دون عبء حسابي عكوس.
• كفاءة الموارد: تتطلب الدوائر المقترحة عدداً ثابتاً من الاستدعاءات لأوراكل المقترح والقبول. بالنسبة لفضاء حالة بحجم $n$ (يتطلب $m = \lceil \log_2 n \rceil$ من الكيوبتات)، يستخدم البناء الرئيسي $4m + 4$ من الكيوبتات. ويقلل بناء بديل (الملحق A) هذا العدد إلى $2m + 1$ كيوبت. وهذا يمثل انخفاضاً كبيراً مقارنة بالطرق السابقة (مثل Childs et al. [16] أو Lemieux et al. [14]) التي تتطلب أعداد كيوبتات تتناسب مع دقة الإحداثيات أو عدد الحركات الممكنة.
• تضخيم الفجوة التربيعي: يثبت المؤلفون أن الفجوة الطيفية للتمديد العكوس للنموذج المزدوج هي من نفس رتبة نموذج MH الأصلي. وبالتالي، فإن الفجوة الزاوية للمشية المكممة الناتجة هي في $\Omega(\sqrt{\delta})$، حيث $\delta$ هي الفجوة الطيفية لسلسلة ماركوف الكلاسيكية. وهذا يحافظ على التسريع التربيعي النظري.
• إجراء أخذ العينات: يتم توفير خوارزمية كاملة (الخوارزمية 1) تستخرج العينات من التوزيع المستقر $\pi$ عن طريق إسقاط مؤثر المشية على الحالة الذاتية 1 ورسم النتيجة مرة أخرى إلى التوزيع المستهدف باستخدام الأوراكل.

النتائج
يتحقق المؤلفون من صحة بنائهم من خلال البراهين النظرية والمحاكاة العددية:

• الضمانات النظرية: تثبت الورقة أن مؤثر المشية المبني $W$ له متجه ذاتي فريد للحالة 1 في نطاق الترميز الذي يتوافق مع التوزيع المستقر. كما توضح أن الفجوة الطيفية للمشية يتم تضخيمها تربيعياً بالنسبة للسلسلة الكلاسيكية، حتى بالنسبة لمصفوفات القبول العامة (باستخدام نسخة "كسولة" من النموذج لضمان العشوائية/الارتباط).
• التحقق العددي: تم تطبيق الطريقة على خوارزمية لانجفان المعدلة بميتروليس (MALA) التي تستهدف جهداً ذا بئرين. باستخدام إجمالي 27 كيوبت (6 كيوبتات لكل سجل حالة لـ 64 حالة مجزأة)، قام المؤلفون بمحاكاة مؤثر المشية. وأكدت النتائج أن الفجوة الطيفية للمشية الكمومية كانت أكبر تربيعياً من العملية الكلاسيكية، وهو ما يطابق الحد الأدني النظري $\cos^{-1}(\sqrt{1-\delta/2})$.
• القابلية للتوسع: يشير التدرج الخطي لمتطلبات الكيوبت مع عدد الذرات في محاكاة الديناميكا الجزيئية ($12N$ سجلات إحداثيات + 3 سجلات مساعدة) إلى مسار قابل للتوسع نحو الأنظمة الواقعية دون العبء المرهق للحسابات العكوسة.

الأهمية والادعاءات
تدعي الورقة أن هذا البناء يتيح تنفيذ مشيات MH الكمومية على الحواسيب الكمومية القريبة من المدى والمقاومة للأخطاء من خلال تقليل عدد الكيوبتات وإلغاء العمليات الحسابية المكلفة. ويذكر المؤلفون أن طريقتهم هي الوحيدة لتكميم سيجديدي لنماذج MH التي لا تعتمد على الحساب المتماسك لعناصر المصفوفة. ويجادلون بأن هذا يشير إلى أن التسريع التربيعي الشامل لمحاكاة MCMC عبر الكم هو أمر قابل للتحقيق عملياً، بشر شرط إمكانية تنفيذ أوراكل $O_T$ و $O_A$ بكفاءة. تُقدم هذه الأعمال كخطوة تدريجية نحو تسريع كمي تربيعي كامل لـ MCMC، مع الميزة الإضافية المتمثلة في أن متطلبات الموارد المخفضة تسمح بإجراء محاكاة عددية دقيقة للنماذج الصغيرة للتحقق من الأداء. كما يشير المؤلفون إلى أن مؤثرات الخطوة نفسها هي موضوع ذو أهمية مستقلة لتحويلات القيمة المفردة الكمومية (QSVT)، وأن نهج فضاء الحافة قد يكون قابلاً للتطبيق على مشكلات تحسين الدوائر الكمومية الأخرى.