⚛️ quantum physics

Probabilistic modeling over permutations using quantum computers

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

المؤلفون الأصليون: Vasilis Belis, Giulio Crognaletti, Matteo Argenton, Michele Grossi, Maria Schuld

نُشر 2026-03-25

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

CC BY 4.0

المؤلفون الأصليون: Vasilis Belis, Giulio Crognaletti, Matteo Argenton, Michele Grossi, Maria Schuld

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

تخيل أنك تحاول حل لغز "بازل" ضخم، ولكن بدلاً من 1,000 قطعة، لديك لغز يحتوي على n! (n مضروبة في نفسها) من القطع. إذا كان لديك 10 كائنات فقط، فهناك 3.6 مليون طريقة لترتيبها. وإذا كان لديك 20 كائناً، فإن عدد الترتيبات أكبر من عدد الذرات في الكون.

هذه هي مشكلة التباديل (Permutations). وهي تظهر في كل مكان:

شاحنات التوصيل: تحديد أفضل ترتيب لزيارة 50 منزلاً.
محركات الترشيح: تخمين الأفلام العشرة التي قد تعجبك من بين الآلاف.
تسلسل الحمض النووي (DNA): إعادة تجميع الجينوم من قطع صغيرة مبعثرة.

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

تقترح هذه الورقة البحثية طريقة لاستخدام الحواسيب الكمومية لحل هذه المشكلة، ليس من خلال النظر في كل قطعة، بل من خلال النظر إلى "موسيقى" اللغز.

الفكرة الجوهرية: الاستماع إلى "موسيقى" الترتيبات

يستخدم المؤلفون مفهوماً رياضياً يسمى التحليل التوافقي (Harmonic Analysis). فكر في الصوت المعقد (مثل السيمفونية) ليس كضجيج واحد، بل كمزيج من نوتات موسيقية مختلفة (ترددات).

النغمات المنخفضة (الترددات المنخفضة): تمثل الأنماط البسيطة. "الكائن (أ) عادة ما يكون في المركز الأول".
النغمات العالية (الترددات العالية): تمثل الأنماط المعقدة والمتداخلة. "إذا كان الكائن (أ) هو الأول، فيجب أن يكون (ب) في المركز الثالث، ولكن فقط إذا كان (ج) في المركز الأخير".

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

الميزة الكمومية:
تمتلك الحواسيب الكمومية قوة خارقة خاصة تسمى تحويل فورييه الكمومي (QFT). إنه يشبه شوكة رنانة سحرية يمكنها سماع كل نوتة في السيمفونية فوراً، من أعمق نغمات الباص إلى أعلى صفير. وبينما يستغرق الحاسوب الكلاسيكي وقتاً أطل من عمر الكون للقيام بذلك للغاز الكبيرة، يمكن للحاسوب الكمومي القيام به في ثوانٍ.

كيف تعمل الخوارزمية الكمومية: رقصة "الاعتقاد"

تصف الورقة عملية تشبه الرقصة بين خطوتين: الانتشار (Diffusion) والتكييف (Conditioning). تخيل أنك تحاول تخمين الترتيب السري لأوراق اللعب.

الخطوة 1: الانتشار (نشر عدم اليقين)

تخيل أن لديك اعتقاداً بشأن ترتيب الأوراق. رب maybe تعتقد أن "الآس" (Ace) في الأعلى.

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

الخطوة 2: التكييف (اختبار الواقع)

الآن، تلقي نظرة خاطفة على الورقة العلوية. إنها ورقة "الملك"!

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

الحلقة السحرية

المشكلة هي أن "الانتشار" سهل في "وضع الموسيقى"، لكن "التكييف" سهل في "وضع الأوراق".

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

النتيجة: "المُخمّن الخارق"

من خلال تكرار هذه الرقصة، يبني الحاسوب الكمومي نموذجاً احتمالياً (Probabilistic Model).

بدلاً من إعطائك إجابة واحدة فقط (مثلاً: "الترتيب هو أ-ب-ج")، فإنه يعطيك سحابة من الاحتمالات.
يخبرك: "هناك احتمال 90% أن يكون الترتيد هو أ-ب-ج، واحتمال 5% أن يكون أ-ج-ب، واحتمال ضئيل أن يكون شيئاً آخر".

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

لماذا هذا مهم؟ (ما الفائدة؟)

ترشيحات أفضل: يمكن لـ Netflix أو Spotify فهم ذوقك ليس فقط كـ "أنا أحب الروك"، بل كأنماط معقدة ودقيقة مثل "أنا أحب أغاني الروك ذات الإيقاع الطبل المحدّد الذي لا يعمل إلا عندما تمطر".
لوجستيات أذكى: يمكن لطائرات التوصيل بدون طيار (Drones) إيجاد المسار المثالي لـ 100 محطة، مما يوفر كميات هائلة من الوقود والوقت، من خلال فهم أنماط حركة المرور المعقدة التي تغفل عنها البرمجيات الحالية.
فيزياء جديدة: يفتح الباب لحل المشكلات المتعلقة بالتناظر والنظام التي كانت تعتبر مستحيلة سابقاً.

العقبة (واقع الحال)

المؤلفون صريحون: هذا مخطط هندسي (Blueprint)، وليس منتجاً نهائياً.

الأجهزة (Hardware): لا نملك حواسيب كمومية كبيرة بما يكفي لاستيعاب "مجموعة أوراق اللعب" لـ 20 أو 30 عنصراً بعد.
الضجيج (Noise): الحواسيب الكمومية الحالية مليئة بالضجيج؛ القليل من التشويش يمكن أن يفسد "الموسيقى".
الخطوات التالية: يحتاجون لإثبات نجاح ذلك على بيانات من العالم الحقيقي وبناء الدوائر المحددة لجعل ذلك ممكناً.

باختختصار

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "النمذجة الاحتمالية على التباديل باستخدام الحواسيب الكمومية" لـ بليس وآخرون.

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

تعد النمذجة الاحتمالية على التباديل (الزمرة المتماثلة $S_n$ ) تحديًا جوهريًا في تطبيقات تعلم الآلة مثل تتبع الأجسام المتعددة، وأنظمة التوصية، وتعلم التفضيلات.

العائق الكلاسيكي: تنمو مساحة التباديل بشكل عاملي ( $n!$ ). تعتمد الطرق الكلاسيكية التي تستخدم التحليل التوافقي غير الأبلي (Non-Abelian Harmonic Analysis) (تحويل فورييه للمجموعات) على "طيف فورييه" لالتقاط الارتباطات. تمثل الترددات المنخفضة الهوامش البسيطة، بينما تلتقط الترددات العالية الاعتمادات المعقدة متعددة الأجسام.
القيود:
- تحديد النطاق (Band-limiting): لجعل الحساب قابلاً للتطبيق، يجب على الطرق الكلاسيكية بتر الطيف إلى الترددات المنخفضة، مما يؤدي إلى فقدان معلومات الارتباط عالية الرتبة.
- التعقيد الحسابي: يتطلب الاستدلال الدقيق التناوب بين الفضاء المباشر (التباديل) وفضاء فورييه. يعمل تحويل فورييه السريع (FFT) الكلاسيكي على $S_n$ بمقياس فائق الأسي قدره $O(n! n^2)$ ، مما يجعل النمذجة الدقيقة غير قابلة للتطبيق حتى لقيم $n$ متوسطة.
- صعوبة الاستدلال: حساب التوزيع اللاحق (Posterior Distribution) أو إيجاد تقدير الاحتمال الأقصى البعدي (MAP) هو أمر باهظ التكلفة حسابيًا دون استخدام تقريبات.

2. المنهجية

يقترح المؤلفون خوارزمية كمومية تقوم بتشفير النموذج الاحتمالي الدقيق في سعات حالة كمومية، مستفيدة من تحويل فورييه الكمومي (QFT) عبر الزمرة المتماثلة لتجاوز العوائق الكلاسيكية.

أ. الإطار الجوهري: سلسلة ماركوف على $S_n$

يتطور النموذج عبر حالة اعتقاد $h^{(t)}(\sigma)$ فوق التباديل من خلال خطوات متناوبة:

الانتشار (Diffusion): ينمذج نمو عدم اليقين بين الملاحظات. يتم تنفيذه كالتفاف متماثل مع المجموعة (Random walk على مخطط كايلي لـ $S_n$ $S_{n}$ المتولد عن التبديلات الانتقالية).
- الميزة الكمومية: في فضاء فورييه، يصبح الالتفاف ضربًا مصفوفيًا نقطيًا.
الاشتراط (Conditioning): يُحدث حالة الاعتقاد عبر قاعدة بايز عند تلقي بيانات جديدة (مثل قراءة مستشعر أو تفضيل مستخدم).
- الميزة الكمومية: في الفضاء المباشر، يكون الاشتراط عبارة عن ضرب نقطي بسيط (الاحتمالية $\times$ الاحتمال السابق).

ب. التنفيذ الكمومي

تستخدم الخوارزمية $O(n \log n)$ كيوبت لتشفير التباديل باستخدام أكواد ليهمر (Lehmer codes) (ربط التباديل بالأعداد الصحيحة). تتضمن العملية ما يلي:

تشفير الحالة: يتم تشفير التوزيع الاحتمالي في سعات حالة كمومية $|\psi\rangle = \sum \sqrt{h(\sigma)} |\sigma\rangle$ (ترميز بورن - Born encoding) أو $|\psi\rangle = \sum h(\sigma) |\sigma\rangle$ (ترميز السعة - Amplitude encoding).
تبديل QFT: تقوم الخوارزمية بالتبديل بكفاءة بين الفضاء المباشر وفضاء فورييه باستخدام QFT على $S_n$ ، والذي يبلغ زمن تشغيله $O(n^3 \log n)$ ، مما يوفر تسارعًا فائق الأسي مقارنة بـ $O(n! n^2)$ الكلاسيكي.
الترميز الكتلي (Block-Encoding):
- الانتشار: يتم تنفيذه في فضاء فورييه. نظرًا لأن نواة الانتشار هي دالة صنف (Class function)، فإن تحويل فورييه الخاص بها يكون قطريًا كتليًا (ضربات قياسية لمصفوفة الوحدة). تستخدم الخوارزمية الترميز الكتلي لتطبيق هذه القيم القياسية على سعات الحالة.
- الاشتراط: يتم تنفيذه في الفضاء المباشر. تستخدم الخوارزمية استراتيجية "إعادة الترتيب والتحديث" لربط قيود الملاحظة المحددة (مثل "الجسم A في الموقع 3") ببداية أو نهاية سلسلة كود ليهمر، مما يسمح بحساب دالة الاحتمالية $\phi(\sigma)$ بكفاءة دون فك التشفير الكامل.
تضخيم السعة (Amplitude Amplification): بما أن عمليات الانتشار والاشتراط هي عمليات غير وحدوية (Non-unitary) يتم تنفيذها عبر كيوبتات مساعدة (Ancilla qubits)، يتم استخدام تضخيم السعة (أو تضخيم السعة ذو النقطة الثابتة) في نهاية التسلسل لتعزيز احتمال الحالة الصحيحة، مما يضمن أن الحالة النهائية تشفر التوزيع اللاحق.

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

النمذجة الاحتمالية الكمومية الدقيقة: أول خوارزمية تشفر نموذجًا احتماليًا دقيقًا على التباديل (بدون تقريبات تحديد النطاق) في حالة كمومية.
الاستخدام الفعال لـ QFT: تقدم تطبيقًا عمليًا لـ QFT على الزمر، وهي أداة كانت تُعتبر سابقًا مثيرة للاهتمام نظريًا فقط وتفتقر إلى حالات استخدام عملية.
تحليل القابلية للتوسع:
- تثبت أن احتمال نجاح خطوة الانتشار مقيد بأسفل بثابت (للمشي الكسول/Lazy walks) أو بمعكوس حدودي لـ $n$ (للمشي العام)، مما يضمن بقاء الخوارزمية فعالة.
- توضح أن زمن التشغيل الإجمالي يهيمن عليه QFT ( $O(n^3 \log n)$ )، بشرط أن يتناسب عدد خطوات سلسلة ماركوف $T$ لوغاريتميًا مع $n$ .
استراتيجيات التشفير المرنة:
- ترميز السعة (Amplitude Encoding): ينتج عينات من $|h(\sigma)|^2$ ، مما يؤدي إلى حدة التوزيع (مفيد لإيجاد الأنماط/Modes).
- ترميز بورن (Born Encoding): ينتج عينات من $h(\sigma)$ مباشرة، حيث يعامل الانتشار كعملية تطور غير ماركوفية للسعات (مشابه للتطور في الزمن التخيلي).
التطبيقات اللاحقة: تحدد طرقًا لاستخدام الحالة الناتجة في النمذجة التوليدية (أخذ عينات من تباديل جديدة) و تقدير MAP (إيجاد التبديل الأكثر احتمالًا) باستخدام تحويل القيمة المفردة الكمومي (QSVT) لتضخيم القمم ذات الاحتمالية العالية.

4. النتائج والنتائج النظرية

التعقيد: تحقق الخوارزمية زمن تشغيل يهيمن عليه $O(n^3 \log n)$ ، وهو تحسن فائق الأسي مقارنة بالطرق الكلاسيكية الدقيقة.
احتمال النجاح: اشتق المؤلفون حدودًا دنيا لنجاح خطوات الترميز الكتلي.
- بالنسبة للمشي العشوائي الكسول ( $p > 1/2$ )، يكون احتمال النجاح مقيدًا بثابت مستقل عن $n$ .
- بالنسبة للمشي العشوائي العقلاني العام، يكون مقيدًا بـ $O(n^{-4})$ ، وهو ما يكفي للتضخيم الحدودي.
الجدوى: تحدد الورقة "نقطة مثالية" للحواسيب الكمومية القريبة من المدى المتاح والمقاومة للأخطاء (Fault-tolerant)، حيث تُقدر أن التطبيقات المفيدة قد تظهر عند $n \approx 15$ إلى $30$. في هذا النطاق، يكون عدد التقسيمات (Irreps) قابلاً للحساب مسبقًا كلاسيكيًا لمعاملات الانتشار، ومع ذلك يظل حجم المشكلة غير قابل للتطبيق كلاسيكيًا لـ FFT الدقيق.

5. الأهمية

فتح آفاق الطرق الطيفية: يجسد هذا العمل الفجوة بين التحليل التوافقي غير الأبلي المجرد وتعلم الآلة العملي. فهو يؤكد الفرضية القائلة بأن الحواسيب الكمومية يمكنها إطلاق القوة الكاملة للطرق الطيفية للبيانات ذات البنية الزمرية.
ما وراء مشكلات الزمرة الجزئية المخفية (HSP): بينما ركزت الخوارزميات الكمومية المبكرة على مشكلات الزمرة الجزئية المخفية الأبلية (مثل خوارزمية شور)، يوضح هذا العمل فائدة تحويلات فورييه غير الأبلية للإحصاء والاستدلال التوليدي، متجاوزًا مشكلة تماثل الرسم البياني (التي ثبت صعوبة حلها باستخدام QFTs).
نموذج جديد للاستدلال: يقترح تحولًا من "حساب الهوامش" (النهج الكلاسيكي) إلى "أخذ عينات من التوزيع اللاحق" (النهج الكمومي)، مما يوفر مسارًا جديدًا لحل مشكلات التحسين التوليفي مثل مشكلة التعيين التربيعي (Quadratic Assignment Problem) أو مهام التصنيف المعقدة.
أساس للعمل المستقبلي: تعمل الورقة كـ "دراسة جدوى"، حيث تضع الأساس النظري للتجارب العددية المستقبلية وتطوير تنفيذات لـ non-Abelian QFTs أكثر كفاءة من حيث الأجهزة.

باختصار، يقدم بليس وآخرون خوارزمية كمومية صارمة تتغلب على القيود الكلاسيكية لنمذجة التباديل من خلال استخدام QFT على $S_n$ لإجراء استدلال طيفي دقيق، مما يوفر تسارعًا محتملاً فائق الأسي لمهام تعلم الآلة الحرجة المتعلقة بالترتيب والتتبع.