⚛️ quantum physics

On the practicality of quantum sieving algorithms for the shortest vector problem

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

المؤلفون الأصليون: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

نُشر 2026-04-13

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

المنخل الكمي العظيم: مراجعة للواقع حول كسر الشفرات المستقبلية

تخيل أنك تحاول العثور على خيط واحد هو الأقصر في كرة ضخمة ومتشابكة من الخيوط بحجم مجرة كاملة. هذا هو جوهر "مسألة المتجه الأقصر" (SVP). في عالم التشفير، هذه "كرة الخيوط" هي هيكل رياضي يسمى "الشبكة" (Lattice)، والعثور على ذلك الخيط الأقصر هو المفتاح لكسر أكثر الأقفال الرقمية أمانًا لدينا اليوم.

لعقود من الزمن، تساءل العلماء: "هل يمكن للحاسوب الكمي أن يجد هذا الخيط بشكل أسرع بكثير من الحاسوب العادي؟"

هذه الورقة البحثية، التي كتبها فريق من الباحثين، تقول: "على الأرجح لا، ليس على الأقل في وقت قريب."

إليك تفصيل لنتائجهم باستخدام تشبيهات بسيطة.

1. الإعداد: السباق الكمي

لكسر التشفير الحديث (النوع الذي سيحمي بياناتنا بعد وصول الحواسيب الكمية)، سيحتاج المخترقون إلى حل مسألة (SVP) على شبكة ذات بُعد يصل إلى 400. فكر في هذا كأنه متاهة مكونة من 400 بُعد.

يعلم الباحثون منذ فترة أن "خوارزمية غروفر" (Grover's Algorithm) (وهي خدعة بحث كمية شهيرة) يمكنها نظريًا تسريع عملية البحث هذه. الأمر يشبه امتلاك مصباح يدوي سحري يسمح لك بفحص غرفتين في وقت واحد بدلاً من غرفة واحدة. من الناحية النظرية، ينبغي أن يجعل هذا البحث أسرع بكثير.

ومع ذلك، تطرح هذه الورقة سؤالاً عملياً للغاية: "ما هي التكلفة الفعلية لبناء ذلك المصباح اليدوي السحري؟"

2. التكاليف الخفية: "السحر" ليس مجانياً

أدرك المؤلفون أن الدراسات السابقة كانت تشبه تقدير تكلفة رحلة بالسيارة عبر حساب سعر الوقود فقط، مع تجاهل سعر السيارة، والسائق، والرسوم، وحقيقة أن السيارة قد تتعطل في الطريق.

لقد قرروا حساب "الفاتورة الكاملة"، بما في ذلك:

السيارة (الأجهزة/Hardware): بناء حاسوب كمي يتطلب ملايين الأجزاء الصغيرة.
السائق (تصحيح الخطأ): البتات الكمية (qubits) هشة للغاية، مثل كرات رخامية زجاجية على طريق وعر. وللحفاظ عليها من التحطم، تحتاج إلى تغليف كل كرة "مفيدة" بفقاعة واقية مصنوعة من آلاف الكرات الأخرى. هذا ما يسمى "تصحيح الخطأ الكمي" (Quantum Error Correction).
الذاكرة (QRAM): للبحث في كرة الخيوض، يحتاج الحاسوب إلى تذكر مكان كل خيط. تحسب الورقة تكلفة بناء "مكتبة كمية" ضخمة (QRAM) يمكن الوصول إليها فوراً.
الوقود (الوقت): كم من الوقت يستغرق المحرك ليعمل؟

3. الكشف الكبير: الأرقام صادمة

عندما قام المؤلفون بمعالجة الأرقام لشبكة ذات بُعد 400 (الحجم المطلوب لكسر معايير "ما بعد الكم" الأمنية الحالية)، كانت النتائج متواضعة:

عدد البتات الكمية (Qubits): لتشغيل هذه الخوارزمية، ستحتاج إلى حوالي 10 تريليون (10¹³) بت كمي فيزيائي.
- تشبيه: إذا كان كل ذرة في جسم الإنسان تمثل بتًا كميًا، فستحتاج إلى ذرات مليارات البشر مكدسة معًا لبناء هذا الحاسوب.
الوقت: حتى مع هذه الآلة الضخمة، سيستغرق الأمر حوالي 10³¹ سنة لحل المسألة.
- تشبيه: عمر الكون هو حوالي 13.8 مليار سنة فقط (10¹⁰). هذا الحاسوب سيستغرق مدة زمنية أطول بـ 1,000,000,000,000,000,000,000,000,000,000 مرة من عمر الكون.

4. المفاجأة "الكلاسيكية"

هنا تكمن المفارقة: قام المؤلفون أيضًا بحساب المدة التي سيستغرقها حاسوب كلاسيكي عادي، أحادي النواة (مثل الذي في حاسوبك المحمول، ولكن يعمل بسرعة عالية جداً) للقيام بنفس المهمة.

سيستغرق الأمر تقريبًا نفس الوقت: 10³¹ سنة.

هذا يعني أنه بالنسبة لمسألة كسر أكواد الشبكة هذه تحديدًا، فإن "التسريع الكمي" (المصباح السحري) مكلف للغاية في البناء والتشغيل لدرجة أنه لا يقدم أي ميزة حقيقية مقارنة بالحاسوب العادي. إن عبء الحفاظ على استقرار الحاسوب الكمي يلتهم كل مكاسب السرعة.

5. لماذا هذا صعب للغاية؟ (عنق زجاجة الـ QRAM)

المتسبب الأكبر في هذه التكلفة الهائلة هو الـ QRAM (ذاكرة الوصول العشوائي الكمية).

تشبيه: تخيل أنك تبحث عن إبرة في كومة قش. يريد الحاسوب الكمي النظر في كومة القش بأكملها في وقت واحد. ولكن للقيام بذلك، يحتاج إلى بطاقة مكتبة لكل قطعة قش. بناء نظام بطاقات مكتبة لكومة قش بحجم مجرة يتطلب موارد أكثر من كومة القش نفسها!
توضح الورقة أن الذاكرة المطلوبة لحفظ البيانات اللازمة للبحث ضخمة جدًا لدرجة أنها تبتلع جميع فوائد التسريع الكمي.

6. الخلاصة: لا داعي للذعر (بعد)

خلص المؤلفون إلى ما يلي:

المعايير الحالية آمنة: التشفير القائم على الشبكات الذي يتم وضعه كمعيار من قبل المعهد الوطني للمعايير والتقنية (NIST) (مثل Kyber و Dilithium) آمن ضد الهجمات الكمية في المستقبل المنظور.
لا يوجد حل سحري: مجرد إضافة حاسوب كمي إلى المعادلة لا يكسر هذه الأكواد تلقائيًا. المتطلبات العتادية مستحيلة حاليًا.
أمل مستقبلي؟ لكي تتمكن الحواسيب الكمية من كسر هذه الأكواد فعليًا، سنحتاج إلى طفرات هائلة في مجالين:
- الأجهزة (Hardware): بناء حواسيب كمية لا تحتاج إلى ملايين "الفقاعات" الواقية لكل بت كمي.
- الذاكرة: إيجاد طريقة لبناء ذاكرة كمية (QRAM) لا تتطلب مساحة بحجم مجرة!

ملخص

اعتبر هذه الورقة بمثابة مراجعة للواقع بشأن "النهاية الكمية" (Quantum Apocalypse). بينما الحواسيب الكمية مذهلة وستحل العديد من المشكلات في النهاية، إلا أنها ليست عصا سحرية تكسر جميع أنواع التشفير فورًا.

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

ملخص تقني لورقة بحثية بعنوان: "حول عملية خوارزميات النخل الكمومي لحل مشكلة المتجه الأقصر"

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

تعتمد أمن التشفير ما بعد الكمي (PQC)، وخاصة المخططات القائمة على الشبكات (Lattices) مثل تلك التي اعتمدتها NIST (على سبيل المثال، Kyber وDilithium)، على الصعوبة الحسابية لـ مشكلة المتجه الأقصر (SVP). تطلب مشكلة SVP إيجاد أقصر متجه غير صفري في شبكة عددية صحيحة. وبينما تُعرف الخوارزميات الكلاسيكية (التعداد والنخل/Sieving) بأنها أسية بالنسبة لبعد الشبكة $D$ ، يُعتقد على نطاق واسع أن الحواسيب الكمومية يمكن أن توفر تسريعاً، بشكل أساسي من خلال خوارزمية بحث غروفر (Grover's search algorithm)، والتي توفر تسريعاً تربيعياً ( $O(\sqrt{N})$ مقابل $O(N)$ ) للبحث غير المنظم.

أشارت التحليلات النظرية السابقة إلى أن خوارزميات النخل الكمومية يمكنها حل SVP بتعقيد يبلغ حوالي $2^{0.267D}$ (باستخدام بحث غروفر على نخل يستخدم التجزئة ذات الحساسية الموضعية/الترشيح/LSH/LSF)، وهو أقل بكثير من أفضل التعقيدات الكلاسيكية ( $2^{0.292D}$ ). ومع ذلك، غالباً ما تجاهلت هذه التحليلات التقاربية الأعباء الإضافية الحرجة:

تكلفة ذاكرة الوصول العشوائي الكمومية (QRAM).
عبء تصحيح الخطأ الكمومي (QEC).
تكلفة الحسابات ذات النقطة الثابتة (fixed-point arithmetic) على الأجهزة الكمومية.
القيود غير التقاربية (مثل العدد غير المعروف للحلول).

تعالج الورقة الفجوة بين النظرية التقاربية والجدوى العملية من خلال إجراء تقدير دقيق للموارد اللازمة لحل SVP في الأبعاد ذات الصلة بالمعايير التشفيرية الحالية (تحديداً $D=400$ ).

2. المنهجية

أجرى المؤلفون تحليلاً شاملاً لتقدير الموارد لثمانية أنواع من خوارزميات النخل:

NVSieve (Nguyen-Vidick) و GaussSieve (Micciancio-Voulgaris).
متغيرات محسنة باستخدام التجزئة ذات الحساسية الموضعية (LSH): LSH الزاوي و LSH الكروي.
متغيرات محسنة باستخدام الترشيح ذات الحساسية الموضعية (LSF): LSF الكروي.

دمج التحليل المكونات التالية:

الحساب الكمومي: استخدموا دوائر متطورة للحسابات ذات النقطة الثابتة (الجمع، المقارنة، الضرب) بدقة 32 بت ( $\kappa=32$ ). واستخدموا جامع Gidney "خارج المكان" (الأقل في عدد بوابات Toffoli) ومضاعفاً بأسلوب المدرسة التقليدية (schoolbook-style).
بحث غروفر: تم تنفيذ بحث غروفر غير التقاربي (باستخدام متغيرات البحث الأسي) لأن عدد الحلول في خطوات النخل غير معروف مسبقاً.
QRAM: نمذجة تكلفة QRAM بنظام bucket-brigade (تصميم Arunachalam et al.) للوصول إلى قواعد البيانات الكلاسيكية. كان هذا محور تركيز رئيسي، حيث تتطلب QRAM عدداً من الكيوبتات المنطقية يتناسب طردياً مع حجم قاعدة البيانات.
تصحيح الخطأ: افترضوا بنية الرمز السطحي (surface code) مع معدل خطأ فيزيائي $p_{phy} = 10^{-5}$ . واستخدموا تقطير الحالة السحرية (magic state distillation) متعدد المستويات (حتى 3 مستويات) لتحقيق معدلات خطأ منطقية أقل من $10^{-40}$ ، وهو أمر ضروري للعدد الهائل من بوابات Toffoli المطلوبة.
البنى التحتية: تم تقييم بنيتين فيزيائيتين:
- الأساسية (Baseline): شبكة ثنائية الأبعاد مع تفاعلات الجوار القريب (مثل Google Sycamore).
- الحجم النشط (Active-Volume): بنية أكثر كفاءة (Litinski/Nickerson) تستخدم اتصالات غير محلية ووحدات "مساحة عمل" لتقليل تكاليف الكيوبتات الخاملة.
المرجع الكلاسيكي: قارنوا أوقات التنفيذ الكمومي مقابل حاسوب كلاسيكي أحادي النواة (6 جيجاهرتز) يقوم بعمليات بحث متسلسلة وتجزئة.

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

أول تقدير شامل للموارد: على عكس الأعمال السابقة التي ركزت على عدد البوابات التقاربي أو تجاهلت QRAM/QEC، توفر هذه الورقة تقديراً كاملاً لموارد الـ Full-stack بما في ذلك الكيوبتات الفيزيائية، والوقت، وأعباء تصحيح الخطأ.
هيمنة QRAM: أثبت المؤلفون أن تكلفة QRAM هي العائق الرئيسي. في خوارزميات النخل، يستهلك الحاجة للوصول إلى قوائم متجهات ضخمة أسياً عبر QRAM الغالبية العظمى من الكيوبتات الفيزيائية.
التحليل غير التقاربي: أخذوا في الاعتبار مشكلة "العدد غير المعروف للحلول" في بحث غروفر، مما يزيد من تعقيد الاستعلام مقارنة بحالة $O(\sqrt{N/M})$ المثالية.
واقعية الأجهزة: من خلال دمج معايير واقعية لزمن الاستجابة (1 ميكروثانية)، ودورات الكود (100 نانوثانية)، وتقطير الحالة السحرية متعدد المستويات، ينتقل هذا البحث إلى ما وراء نماذج "اللعب" (toy models) النظرية.

4. النتائج الرئيسية

النتائج الخاصة بالبعد الحرج $D=400$ (المطلوب لكسر معايير الأمان من المستوى الأول لـ NIST) صارخة:

الكيوبتات الفيزيائية: حتى في ظل الافتراضات المتفائلة، تتطلب أفضل خوارزمية نخل كمومية (GaussSieve مع Spherical LSF) حوالي $10^{13}$ كيوبت فيزيائي.
- التفصيل: يتم تخصيص غالبية هذه الكيوبتات للبنية التحتية لـ QRAM المطلوبة لتخزين قوائم المتجهات المرشحة.
وقت التنفيذ: الوقت المقدر لحل SVP عند $D=400$ $D = 400$ هو حوالي $10^{31}$ سنة.
- هذه المدة أطول بكثير من عمر الكون ( $\approx 1.38 \times 10^{10}$ سنة).
المقارنة مع الكلاسيكي: حاسوب كلاسيكي أحادي النواة (6 جيجاهرتز) يقوم بنفس المهمة (بحث متسلسل) سيستغرق أيضاً حوالي $10^{31}$ سنة.
- الاستنتاج: لا يوجد تسريع كمومي عملي عند الأبعاد التشفيرية. التسريع التربيعي من خوارزمية غروفر يتم إلغاؤه تماماً بواسطة أعباء QRAM، وتصحيح الخطأ، والحسابات.
القياس (Scaling): لا يظهر التفوق الكمومي (حيث يكون الوقت الكمومي < الوقت الكلاسيكي) إلا في أبعاد تتجاوز بكثير $D=1000$ ، حيث يصل عامل التسريع الكمومي إلى $\approx 10^5$ ، ولكن الوقت المطلق يظل فلكياً ومتطلبات الكيوبت تظل غير قابلة للتنفيذ.
قيود العمق: عندما يتم تقييد البحث بحدود العمق المقترحة من NIST (مثلاً $2^{40}$ بوابة)، ينخفض عدد الكيوبتات الفيزيائية، ولكن وقت التنفيذ يزداد أكثر، مما يعزز عدم وجود ميزة.

5. الأهمية والآثار المترتبة

أمن تشفير الشبكات: توفر الورقة دليلاً قوياً على أن التشفير القائم على الشبكات (تحديداً المخططات القائمة على SVP) يظل آمناً ضد الهجمات الكمومية باستخدام التقنيات الكمومية الحالية والقريبة المستقبلية. "التهديد الكمومي" لهذه المعايير من المرجح أن يكون ضئيلاً مقارنة بالتهديدات الكلاسيكية.
عائق QRAM: تسلط الدراسة الضوء على أنه ما لم يحدث اختراق في بنية QRAM (لجعلها أرخص بكثير من حيث الكيوبتات والعمق)، فإن الخوارزميات الكمومية التي تعتمد على عمليات البحث في قواعد البيانات الضخمة (مثل النخل) لن تكون عملية.
معايير تقدير الموارد: تضع الورقة معياراً جديداً لتقدير الموارد في تحليل التشفير الكمومي، بالانتقال من مجرد عد البوابات إلى نمذجة الموارد الفيزيائية الكاملة بما في ذلك تصحيح الخطأ وتكاليف الذاكرة.
الاتجاهات المستقبلية: يشير المؤلفون إلى أنه بينما تحليلهم متشائم فيما يتعلق بالبروتوكولات الحالية، فإن الاختراقات النظرية الكبيرة في المسارات العشوائية الكمومية (quantum random walks) أو بنيات الأجهزة الجديدة قد تغير المشهد. ومع ذلك، يجب أن تكون هذه الاختراقات جوهرية للتغلب على حاجز الـ $10^{13}$ كيوبت.

باختصار، تخلص الورقة إلى أن بحث غروفر يقدم ميزة عملية ضئيلة أو معدومة لحل SVP في الأبعاد ذات الصلة بالتشفير بسبب التكاليف الباهظة لتصحيح الخطأ و QRAM، مما يشير إلى أن التشفير القائم على الشبكات قوي في مواجهة الهجمات الكمومية المتوقعة.