A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

إليك ملخص تقني مفصل لورقة البحث بعنوان "نهج قابل للتوسع عملياً لمسألة المتجه الأقرب (CVP) عبر خوارزمية QAOA بزوايا ثابتة" من إعداد بن بريستلي وبتروس والدن.

1. بيان المشكلة

تتناول الورقة مسألة المتجه الأقرب (Closest Vector Problem - CVP) في سياق تحليل الأعداد الصحيحة إلى عواملها، مع التركيز بشكل خاص على طرق نخل الشبكة (lattice sieving) التي اقترحها شنور (Schnorr).

• السياق: يعتمد تحليل الأعداد الصحيحة (مثل RSA) على صعوبة إيجاد "أزواج علاقات سلسة" (sr-pairs). وتختزل طريقة شنور هذه المسألة إلى إيجاد حل لـ CVP في "شبكة أولية" (prime lattice) محددة.
• التحدي: أشارت ادعاءات حديثة (على سبيل المثال، Yan et al. [1]) إلى أن خوارزمية التحسين التقريبي الكمي (QAOA) يمكنها حل مسألة CVP هذه بموارد دون خطية، مما قد يؤدي لكسر نظام RSA. ومع ذلك، واجهت هذه الادعاءات شكوكاً فيما يتعلق بـ:
  1. القابلية للتوسع (Scalability): ما إذا كانت الخوارزمية تتوسع مع أبعاد الشبكة الأكبر.
  2. تحسين المعلمات (Parameter Optimization): التكلفة الحسابية لإيجاد الزوايا المثلى لـ QAOA لكل حالة جديدة.
  3. فضاء البحث (Search Space): ما إذا كان فضاء البحث المقترح ($O(n)$ كيوبت) كافياً لإيجاد المتجه الأقرب الحقيقي (حيث يرى النقاد أن $O(n \log n)$ هو المطلوب).
• الهدف: يهدف المؤلفون إلى تقييم القابلية للتوسع العملي والتعقيد الزمني لاستخدام QAOA مع زوايا ثابتة (معلمات مدربة مسبقاً) لتحسين التقريبات الكلاسيكية لمسألة CVP، بمعزل عن الادعاء النهائي بكسر نظام RSA.

2. المنهجية

يقترح المؤلفون إطار عمل يجمع بين تقليل الشبكة الكلاسيكي (classical lattice reduction) ونهج كمي متغير باستخدام Fixed-Angle QAOA.

أ. صياغة المشكلة

• بناء الشبكة الأولية: يقومون ببناء شبكة $L(B_{n,c})$ بناءً على لوغاريتمات الأعداد الأولية، حيث يمثل المتجه الهدف $t$ القيمة $\log N$.
• المعالجة المسبقة الكلاسيكية:
  1. تطبيق اختزال LLL على الأساس (basis).
  2. استخدام خوارزمية Babai لأقرب مستوٍ (Nearest Plane Algorithm) لإيجاد حل تقريبي $b_{op}$.
• التحسين الكمي (الجوهر):
  • بدلاً من البحث في كامل الشبكة، تبحث خوارزمية QAOA في الجوار الوحدوي (unit neighborhood) للمتجه $b_{op}$.
  • يتم تعيين المسألة كمسألة حالة ذات قيمة ذاتية دنيا (QUBO)، حيث دالة التكلفة هي المسافة الإقليدية بين المتجه المرشح $v_{new}$ والهدف $t$.
  2. حجم فضاء البحث هو $2^n$ (خطي في بعد الشبكة $n$)، ويتم ترميزه في $n$ من الكيوبتات.

ب. QAOA بزوايا ثابتة والتدريب المسبق

لمعالجة عقبة القابلية للتوسع المتمثلة في تحسين معلمات QAOΑ ($\gamma, \beta$) لكل حالة، قدم المؤلفون مخطط تدريب مسبق:

1. توزيع التدريب: توليد حالات CVP عشوائية بأحجام متفاوتة.
2. التحسين: لمجموعة من الحالات، يتم تحسين زوايا QAOA لزيادة احتمالية إيجاد حل أفضل من $b_{op}$.
3. التحقق والتعميم: تقييم مجموعات الزوايا هذه على توزيع تحقق مستقل. الهدف هو إيجاد مجموعة من الزوايا التي تتعمم (generalizes) بشكل جيد على أبعاد الشبكة الأكبر (تقليل اضمحلال احتمال النجاح مع زيادة $n$).
4. الزوايا الثابتة: بمجرد العثور على مجموعة زوايا قوية، يتم "تثبيتها" وتطبيقها على جميع الحالات اللاحقة دون مزيد من التحسين، مما يلغي حلقة التحسين الخارجية فعلياً.

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

1. مخطط تدريب مسبق قوي: خوارزمية مبتكرة (Algorithm 1) تدرب زوايا QAOA على حالات صغيرة/متوسطة لإيجاد مجموعة معلمات تتوسع لتشمل المشكلات الأكبر، مما يتجنب الإفراط في التخصيص (overfitting) للحالات الصغيرة المحددة.
2. تحليل التعقيد الزمني: تحليل تجريبي صارم لسلوك التوسع لـ QAOA في تحسين CVP. لقد تجاوزوا الحدود النظرية لتقديم أدلة عددية على الأداء.
3. تطبيق الزوايا الثابتة: أحد أوائل التطبيقات لـ Fixed-Angle QAOA على مسألة ذات أهمية تشفيرية (CVP)، مما يثبت أن التدريب المسبق يمكن أن يقلل بشكل كبير من العبء الحسابي.
4. إثبات التفوق الكمي: يوضحون وجود تسريع كمي يتجاوز تسريع Grover التربيعي القياسي ($O(\sqrt{N})$) لهياكل شبكية محددة.

4. النتائج

أجرى المؤلفون محاكاة عددية مكثفة لأبعاد الشبكة $n$ حتى 18 (ما يقابل أعداداً بطول 128 بت) وعمق QAOA $p$ من 1 إلى 10.

• توسع احتمالية النجاح:

  • احتمال $q(n)$ لتحسين الحل يتناقص أسياً مع بعد الشبكة: $q(n) \approx 1/2^{\alpha n}$.
  • البحث الكلاسيكي الشامل (Brute Force): $\alpha \approx 1$ (ضمنيًا).
  • خوارزمية Grover: $\alpha = 0.5$ (تسريع تربيعي).
  • Fixed-Angle QAOA ($p=10$): حققت $\alpha \approx 0.225$.
  • الدلالة: يمثل هذا تفوقاً من الدرجة الخامسة ($O(2^{0.225n})$) مقارنة بالبحث الشامل، وهو ما يتفوق بشكل كبير على خوارزمية Grover.

• التقارب:

  • تقاربت الزوايا المدربة مسبقاً بشكل مستقر مع زيادة طول البت (bit-length) لحالات التدريب.
  • الزوايا التي تم العثست عليها في الحالات الصغيرة (مثلاً، طول البت < 20) فشلت في التعميم، مما يؤكد ضرورة استراتيجية التدريب المسبق الخاصة بالمؤلفين بدلاً من مجرد التدريب البسيط للحالة الواحدة.

• جودة التحسين:

  • بينما تنخفض احتمالية إيجاد تحسين مع زيادة البعد، فإن جودة التحسين (مدى قرب المتجه من الهدف) تتناقص أيضاً بشكل دون أسي.
  • يشير المؤلفون إلى أنه بالنسبة لهيكل "الشبكة الأولية" المحدد المستخدم، تظهر الطريقة واعدة، رغم إقرارهم بأن جودة التحسين قد تتراجع في حالات CVP العامة أو فضاءات البحث الأكبر ($O(n \log n)$).

5. الأهمية والقيود

الأهمية

• إعادة تقييم الأمن الكمي: تشير النتائج إلى أن خوارزميات التحسين الكمي المتغيرة ذات الزوايا الثابتة قد تشكل تهديداً لأنظمة التشفير القائمة على الشبكات (lattice-based) بشكل أسرع مما كان متوقعاً، مما قد يتطلب أبعاد شبكة أكبر مما هو معيار حالي.
• العملية: من خلال إلغاء الحاجة إلى تحسين المعلمات لكل حالة، يصبح النهج قابلاً للتنفيذ حسابياً على أجهزة NISQ (الكمية ذات القدرة المتوسطة والضجيج)، بشرما كانت الزوايا تتعمم.
• ما وراء Grover: تقدم الورقة دليلاً على أن QAOA يمكن أن يحقق تسريعاً "فوق تربيعي" للمشكلات المهيكلة، مما يتحدى فكرة أن حد Grover هو السقف للبحث الكمي في هذا السياق.

القيود والنطاق

• فضاء بحث مقيد: تستخدم الدراسة فضاء بحث بقوة $O(n)$ كيوبت (خطي)، بينما تتطلب المتطلبات النظرية لضمان حلول CVP غالباً $O(n \log n)$. يقر المؤلفون بأن هذا قد يحد من جودة الحل للشبكات العامة.
• هيكل شبكة محدد: النتائج خاصة بـ "الشبكة الأولية" المستخدمة في طريقة تحليل شنور. ومن غير الواضح ما إذا كانت هذه الزوايا الثابتة ستتعمم على حالات CVP عشوائية أو أنظمة تشفير أخرى قائمة على الشبكات.
• الضجيج: المحاكاة خالية من الضجيج. يشير المؤلفون إلى أن الضجيج قد يربك عملية التدريب المسبق، رغم أنهم يجادلون بأن الدوائر ذات العمق الضحل قد تظل قابلة للتطبيق على الأجهزة الأولى ذات الخطأ المنخفض (fault-tolerant).
• ادعاءات التحليل: لا تدعي الورقة كسر نظام RSA. بل تعزل عملية CVP الفرعية لتحليل كفاءتها. ويظل المؤلفون متشككين في ادعاءات "التحليل دون الخطي" بسبب التناقص الأسي للأعداد السلسة في الأبعاد الكبيرة (الملحق ب).

الخاتمة

تثبت الورقة أن Fixed-Angle QAOA، عندما يدعمها مخطط تدريب مسبق قوي، توفر نهجاً قابلاً للتوسع عملياً لتحسين حلول CVP. وهي تحقق تسريعاً كمياً كبيراً (يقترب من $O(2^{0.1n})$ في الأعماق الأعلى) يتجاوز خوارزمية Grover. وبينما يعتمد هذا الأسلوب على هياكل شبكية محددة وقيود في فضاء البحث، فإنه يسلط الضوء على ثغرة محتملة في التشفير القائم على الشبكات ويستوجب إعادة تقييم معايير الأمان للأنظمة ما بعد الكمية.