⚛️ quantum physics

A Polylogarithmic-Depth Quantum Multiplier

تقدم هذه الورقة خوارزمية كمومية لضرب عددين صحيحين مكونين من $n$ بت، تحقق عمق $T$ وعمق دارة بمقدار $O(\log^2 n)$ باستخدام $O(n^2)$ من الموارد، مما يمثل أدنى عمق $T$ معروف لعملية الضرب في نموذج كليفورد + $T$ ويقدم تقدماً كبيراً في إمكانية تحقيق الحوسبة الكمومية ذات القدرة على تحمل الأخطاء واسعة النطاق.

المؤلفون الأصليون: Fred Sun, Anton Borissov

نُشر 2026-04-14

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

CC BY 4.0

المؤلفون الأصليون: Fred Sun, Anton Borissov

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

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

تقدم هذه الورقة البحثية طريقة جديدة وفائقة الكفاءة للقيام بعملية الضرب هذه على حاسوب كمومي. إليك التفاصيل باستخدام تشبيهات بسيطة.

المشكلة: "البطء والثبات" مقابل "السرعة والجنون"

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

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

الحل: "خط تجميع المصنع"

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

إليك كيف يعمل "المضاعف الكمومي السريع" الخاص بهم، خطوة بخطوة:

1. آلة التصوير (النسخ السريع)

تخيل أن لديك مخططاً رئيسياً (الرقم $x$ ) وقائمة تعليمات (الرقم $y$ ). للقيام بالحساب بسرعة، تحتاج إلى صنع نسخ من المخطط لكل تعليمات.

الحيلة: بدلاً من نسخها واحدة تلو الأخرى (وهو ما يستغرق وقتاً طويلاً)، يستخدمون "آلة تصوير سحرية" تضاعف عدد النسخ في كل جزء من الثانية.
- الثانية 1: نسخة واحدة.
- الثانية 2: نسختان.
- الثانية 3: 4 نسخ.
- الثانية 4: 8 نسخ.
النتيجة: في ثوانٍ معدودة فقط (زمن لوغاريتمي)، أصبح لديهم ما يكفي من النسخ لتغذية كل عامل على خط التجميع في آن واحد.

2. النواتج الجزئية (الحسابات الصغيرة)

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

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

3. شجرة الجامعين (هرم الجمع)

هذا هو الجزء الأكثر ذكاءً. الآن لديك آلاف "النواتج الجزئية" (الحسابات الصغيرة) التي يجب جمعها معاً.

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

4. "فريق التنظيف" (إلغاء الحوسبة)

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

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

لماذا يعد هذا أمراً هاماً؟

في عالم الحوسبة الكمومية، هناك نوع محدد من العمليات يسمى بوابة T (أو بوابة توفولي)، وهي مكلفة وبطيئة جداً في التنفيذ. إنها تشبه "الذهب" في العالم الكمومي.

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

المقايضة

هل هناك ثمن؟ نعم. للحصول على هذه السرعة المذهلة، يحتاجون إلى الكثير من المساحة الإضافية (الكيوبتات المساعدة).

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

الملخص

لقد بنى المؤلفون محرك ضرب كمومي هو الأسرع المعروف لضرب الأرقام الكبيرة باستخدام الأدوات الكمومية القياسية.

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

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "مضاعف كمي ذو عمق بولي-لوغاريتمي" (A Polylogarithmic-Depth Quantum Multiplier) للباحثين فريد صن وأنتون بوريسوف.

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

تعد الحسابات الكمية، وخاصة ضرب الأعداد الصحيحة، مكونًا أساسيًا في العديد من الخواروات الكمية الكبرى مثل خوارزمية شور للتحليل إلى عوامل، ومحاكاة الهاملتوني، وخوارزمية HHL للأنظمة الخطية. وفي سياق الحوسبة الكمية المتحملة للخطأ (FTQC)، لا يتحدد أداء الخوارزمية فقط بإجمالي عدد البوابات (عدد البوابات)، بل يعتمد بشكل حاسم على عمق الدائرة (circuit depth)، وبالتحديد عمق T (T-depth).

عنق الزجاجة: تعتبر البوابات غير كليفوردية (وتحديداً بوابة $T$ ) هي الموارد الأكثر تكلفة في الحوسبة الكمية المتحملة للخطأ بسبب التكاليف الإضافية لتقطير الحالة السحرية (magic state distillation).
التحدي: تواجه خوارزميات الضرب الحالية مقايضة؛ فأساليب "المدرسة التقليدية" (الإزاحة والجمع) تتميز بعدد كيو بتات منخفض ولكن بعمق تربيعي ( $O(n^2)$ ). أما الطرق التكرارية مثل Karatsuba أو Toom-Cook فتحسن تعقيد البوابات، لكنها غالبًا ما تحتفظ بعمق عالٍ أو تتطلب هياكل معقدة. أما خوارزمية Schönhage–Strassen فتحقق عمقًا لوغاريتميًا، لكنها تُصنف كـ "خوارزمية مجرية" (galactic algorithm)؛ حيث إن ثوابتها الكبيرة جدًا تجعلها عملية فقط لأحجام مدخلات فلكية ( $n \ge 2^{40}$ ).
الهدف: يهدف المؤلفان إلى تصميم مضاعف كمي يحقق عمقًا بولي-لوغاريتميًا (تحديدًا $O(\log^2 n)$ ) وأدنى عمق لـ T، مع البقاء عمليًا لأحجام المدخلات المتوسطة، حتى لو تطلب ذلك عددًا أكبر من الكيو بتات المساعدة (ancillary qubits).

2. المنهجية

تبني الخوارزمية المقترحة حاصل ضرب عددين صحيحين مكونين من $n$ بت، $x$ و $y$ ، عن طريق توليد نواتج جزئية وجمعها باستخدام هيكل شجرة ثنائية متوازية. يعتمد النهج على ثلاث وحدات فرعية رئيسية:

أ. النسخ السريع (التوازي)

لتعظيم التوازي، تقوم الخوارضة أولاً بإنشاء $n$ نسخة من سجلات المدخلات $|x\rangle$ و $|y\rangle$ .

الآلية: تستخدم خوارزمية "النسخ السريع" (الخوارزمية 1) استراتيجية المضاعفة. في كل خطوة زمنية، تُستخدم النسخ الموجودة كمصادر لإنشاء نسخ جديدة عبر بوابات CNOT متوازية.
التعقيد: تولد $n$ نسخة بعمق $O(\log n)$ باستخدام $O(n^2)$ من الكيو بتات المساعدة.
الغرض: يسمح هذا لجميع حسابات النواتج الجزئية اللاحقة بالحدوث في وقت واحد بدلاً من حدوثها بالتتابع.

ب. النسخ الشرطي (توليد النواتج الجزئية)

بمجرد توفر $n$ نسخة من $x$ و $y$ ، تحسب الخوارزمية النواتج الجزئية $\alpha_{(0,i)} = y_i \cdot x$ .

الآلية: تستخدم روتينًا فرعيًا لـ "النسخ الشرطي". لكل بت $y_i$ ، إذا كانت $y_i=1$ ، يتم نسخ السجل $x$ إلى سجل مستهدف؛ وإلا يظل السجل المستهدف صفرًا. يتم تنفيذ ذلك باستخدام $n$ من بوابات Toffoli تعمل على مجموعات كيو بتات منفصلة.
التعقيد: نظرًا لأن جميع بوابات Toffoli تعمل على كيو بتات منفصلة، فإن هذه الخطوة لها عمق Toffoli قدره 1 وعدد T يبلغ $n^2$ .

ج. شجرة الجامع المتوازي (التراكم)

الابتكار الجوهري يكمن في جمع النواتج الجزئية الـ $n$ . بدلاً من سلسلة خطية من الجامعات، يستخدم المؤلفون بنية شجرة ثنائية.

الهيكل: النواتج الجزئية هي أوراق الشجرة. في كل مستوى $d$ ، يتم جمع أزواج من المجموعات الجزئية لتشكيل المستوى التالي من المجموعات.
QCLA المعدل: يستخدم المؤلفون نسخة معدلة من جامع Carry Lookahead الكمي (QCLA) لـ Draper وآخرون.
- التحسين: الجمع القياسي للأرقام المزاحة يتضمن إضافة أصفار بادئة/لاحقة. يتجنب QCLA المعدل تخصيص كيو بتات لهذه الأصفار صراحةً. يقوم بتقسيم عملية الجمع إلى ثلاث مراحل: نسخ اللاحقة (نسخ البتات غير المتداخلة)، المجموع المتداخل (QCLA قياسي على منطقة التداخل)، وانتشار الحمل (إضافة الحمل إلى البتات المتبقية).
إلغاء الحساب (Uncomputation): للحفاظ على القابلية للانعكاس وتحرير الكيو بتات المساعدة، تقوم الخوارزمية بإلغاء حساب النتائج الوسيطة. تسمح بنية الشجرة بـ "إلغاء حساب متسلسل" (pipelined): أثناء حساب المستوى $d$ ، تقوم الخوارزمية في الوقت نفسه بإلغاء حساب المستوى $d-2$ . يضمن هذا إعادة استخدام الكيو بتات المساعدة بكفاءة دون زيادة العمق التقاربي.

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

أدنى عمق T معروف: تحقق الخوارزمية عمق T قدره $O(\log^2 n)$ ، وهو الأدنى بين جميع خوارزميات الضرب المعروفة باستخدام نموذج Clifford+T.
عمق بولي-لوغاريتمي عملي: على عكس خوارزمية Schönhage–Strassen، يمتلك هذا التصميم ثوابت يمكن التحكم فيها، مما يجعله قابلاً للتطبيق للمدخلات التي يكون فيها $n$ في مئات أو آلاف، بدلاً من اشتراط $n \ge 2^{40}$ .
تحليل صريح للموارد: توفر الورقة حدودًا ملموسة وغير تقاربية لجميع الموارد (العمق، عدد البوابات، عدد Toffoli، وعدد الكيو بتات المساعدة)، بدلاً من الاعتماد فقط على ترميز Big-O.
تصميم معياري: يتم تقسيم البناء إلى وحدات فرعية واضحة وقابلة لإعادة الاستخدام (النسخ السريع، النواتج الجزئية، شجرة الجامع المتوازي)، مما يسهل دمجها في دوائر كمية أكبر.

4. النتائج وتكاليف الموارد

يقدم المؤلفون تفصيلًا دقيقًا لتكاليف الموارد لضرب رقمين مكونين من $n$ بت.

المقياس	التعقيد التقاربي	الحد الأعلى الملموس (تقريبي)
عمق الدائرة	$O(\log^2 n)$	$3 \log^2 n + 17 \log n + 20$
عمق T	$O(\log^2 n)$	$3 \log^2 n + 7 \log n + 14$
عدد Toffoli	$O(n^2)$	$12n^2 - n \log n$
إجمالي عدد البوابات	$O(n^2)$	$26n^2 + 2n \log n$
الكيو بتات المساعدة	$O(n^2)$	$3n^2$ (تحديدًا $3n^2 - 2n$ )

المقايضة: تضحي الخوارزمية بعدد تربيعي من الكيو بتات المساعدة ( $O(n^2)$ ) وبوابات T مقابل تقليل هائل في العمق مقارنة بطرق المدرسة التقليدية ( $O(n^2)$ عمق) وأكثر عملية من Schönhage–Strassen.
المقارنة:
- الإزاحة والجمع (Shift-and-Add): عمق $O(n^2)$ ، كيو بتات $O(n)$ .
- Karatsuba/Toom-Cook: عدد T أقل من التربيع، ولكن عمق أعلى من هذا العمل.
- Schönhage–Strassen: عمق $O(\log^2 n)$ ولكن ثوابت غير عملية وتكاليف كيو بتات أعلى لـ $n$ الصغيرة.

5. الأهمية

يمثل هذا العمل خطوة كبيرة للأمام في الحوسبة الكمية المتحملة للخطأ.

تمكين الخوارزميات واسعة النطاق: من خلال تقليل عمق T، تقلل الخوارزمية من الوقت المطلوب لتقطير الحالة السحرية، وهو العائق الأساسي لتشغيل خوارزمية شور وغيرها من المهام المتعلقة بالتشفير أو المحاكاة.
العملية: تسمح الحدود الصريحة للموارد للمهندسين بتقدير جدوى تنفيذ هذه المضاعفات على أجهزة كمية قريبة المستقبل مصححة الأخطاء.
نموذج التحسين: يوضح العمل أن التضحية بعدد الكيو بتات (باستخدام $O(n^2)$ من الكيو بتات المساعدة) هي استراتيجية قابلة للتطبيق وضرورية لتحقيق التنفيذ منخفض التأخير المطلوب لتحقيق التفوق الكمي العملي.

باخت ملخص، يقدم صن وبوريسوف مضاعفًا كميًا معياريًا ومحسنًا للغاية يعطي الأولوية لوقت التنفيذ (العمق) على المساحة (الكيو بتات)، مما يوفر الحل الأكثر كفاءة المعروف للضرب المتوازي في نموذج Clifford+T.