قياس التكلفة الحسابية

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

كنقطة بداية، لنتأمل الشكل التالي من الدرس السابق، الذي يمثل تجريدًا رفيع المستوى لعملية حسابية.

يمكن نمذجة العملية الحسابية نفسها أو وصفها بطرق متعددة، كبرنامج مكتوب بلغة Python، أو آلة تورينج، أو دائرة بوليانية، أو دائرة كمومية. سينصبّ تركيزنا على الدوائر (البوليانية والكمومية على حدٍّ سواء).

الترميزات وطول المدخل

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

على سبيل المثال، لترميز الأعداد الصحيحة غير السالبة يمكننا استخدام الترميز الثنائي. يسرد الجدول التالي الترميز الثنائي لأول تسعة أعداد صحيحة غير سالبة، إلى جانب الطول (أي العدد الإجمالي للبتات) لكل ترميز.

العدد	الترميز الثنائي	الطول
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

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

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

العدد	الترميز الأحادي	الترميز المعجمي
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(في هذا الجدول، يمثل الرمز $\varepsilon$ السلسلة الفارغة، التي لا تحتوي على أي رموز وطولها يساوي الصفر. وبطبيعة الحال، لتجنب مصدر واضح للالتباس، نستخدم رمزًا خاصًا مثل $\varepsilon$ للتعبير عن السلسلة الفارغة بدلًا من عدم كتابة شيء حرفيًا.)

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

على سبيل المثال، عدد البتات اللازمة للتعبير عن عدد صحيح غير سالب $N$ في الترميز الثنائي، والذي يُرمز إليه أحيانًا بـ $\operatorname{lg}(N),$ يُعطى بالصيغة التالية.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

بافتراض أننا نستخدم الترميز الثنائي لترميز مدخل مسألة تحليل الأعداد الصحيحة إلى عواملها، يكون طول المدخل للعدد $N$ هو $\operatorname{lg}(N).$ لاحظ تحديدًا أن طول (أو حجم) المدخل $N$ ليس هو $N$ نفسه؛ فحين يكون $N$ كبيرًا لا نحتاج إلى هذا العدد الهائل من البتات للتعبير عن $N$ في الترميز الثنائي.

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

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

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

العمليات الأولية

الآن لنتأمل العملية الحسابية نفسها، الممثَّلة بالمستطيل الأزرق في الشكل أعلاه. الطريقة التي سنقيس بها التكلفة الحسابية هي عدّ العمليات الأولية التي تتطلبها كل عملية حسابية. بشكل حدسي، العملية الأولية هي عملية تتضمن عددًا صغيرًا وثابتًا من البتات أو الكيوبتات، ويمكن تنفيذها بسرعة وسهولة — مثل حساب AND لبتتين. في المقابل، تشغيل الدالة factorint لا يُعدّ بشكل معقول عملية أولية.

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

مجموعات البوابات الشاملة

في نماذج الحوسبة القائمة على الدوائر، من المعتاد اعتبار كل بوابة عملية أولية. هذا يطرح سؤالًا حول البوابات التي نسمح بها تحديدًا في دوائرنا. بالتركيز للحظة على الدوائر الكمومية، رأينا عدة بوابات حتى الآن في هذه السلسلة، بما فيها بوابات $X$ و$Y$ و$Z$ و$H$ و$S$ و$T$، وبوابات التبادل، والإصدارات المتحكَّم بها من البوابات (بما فيها بوابات NOT المتحكَّم بها، وToffoli، وFredkin)، فضلًا عن البوابات التي تمثل قياسات الأساس القياسي. في سياق لعبة CHSH رأينا أيضًا عددًا من بوابات الدوران الإضافية.

ناقشنا أيضًا بوابات الاستعلام في سياق نموذج الاستعلام، ورأينا أن أي عملية أحادية $U$ تعمل على أي عدد من الكيوبتات يمكن اعتبارها بوابة إن اخترنا ذلك — لكننا سنتجاهل كلا الخيارين لأغراض هذا النقاش. لن نعمل في نموذج الاستعلام (وإن كان تنفيذ بوابات الاستعلام باستخدام العمليات الأولية مناقَشًا لاحقًا في الدرس)، كما أن النظر إلى بوابات أحادية عشوائية قد تعمل على ملايين الكيوبتات باعتبارها عمليات أولية لا يفضي إلى مفاهيم ذات معنى أو واقعية للتكلفة الحسابية.

بالتمسك ببوابات الكيوبت التي تعمل على أعداد صغيرة منه، أحد الأساليب لتحديد أيها يُعدّ أساسيًا هو استخلاص معيار دقيق — لكن هذا ليس النهج المعتاد ولا النهج الذي سنتبعه. بل نحن ببساطة نتخذ خيارًا.

إليك أحد الخيارات المعيارية الشائعة، وهو ما سنعتمده كمجموعة البوابات الافتراضية للدوائر الكمومية:

• بوابات أحادية الكيوبت من هذه القائمة: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ و $T^{\dagger}$
• بوابات NOT المتحكَّم بها (Controlled-NOT)
• قياسات الأساس القياسي للكيوبت الواحد

بديل شائع آخر هو اعتبار بوابات Toffoli وHadamard و$S$ أساسية، إلى جانب قياسات الأساس القياسي. أحيانًا تُعدّ جميع بوابات الكيوبت الواحد أساسية، وإن كان ذلك يُفضي إلى نموذج بالغ القوة بشكل غير واقعي حين لا تُؤخذ دقة تنفيذ البوابات بعين الاعتبار.

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

بالنسبة للدوائر البوليانية، سنعتبر بوابات AND وOR وNOT وFANOUT هي التي تمثل العمليات الأساسية. في الواقع لسنا بحاجة إلى كلتا بوابتَي AND وOR معًا — يمكننا استخدام قوانين دي مورغان للتحويل من إحداهما إلى الأخرى بوضع بوابات NOT على جميع أسلاك الدخل والخرج الثلاثة — غير أنه من المعتاد والمناسب السماح بكلتيهما. تُشكّل بوابات AND وOR وNOT وFANOUT مجموعة شاملة للحسابات الحتمية، بمعنى أن أي دالة من أي عدد ثابت من بتات الدخل إلى أي عدد ثابت من بتات الخرج يمكن تنفيذها بهذه البوابات.

مبدأ تأجيل القياس

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

تحديدًا، البت الكلاسيكي في الدائرة اليسرى يُستبدل بكيوبت في الدائرة اليمنى (مُهيَّأ في الحالة $\vert 0\rangle$)، وتُستبدل قياسات الأساس القياسي ببوابة NOT متحكَّم بها، يليها قياس أساس قياسي على الكيوبت السفلي. الفكرة هي أن قياس الأساس القياسي في الدائرة اليمنى يمكن دفعه إلى نهاية الدائرة تمامًا. إذا استُخدم البت الكلاسيكي في الدائرة اليسرى لاحقًا كبت تحكم، يمكننا استخدام الكيوبت السفلي في الدائرة اليمنى كمتحكم بدلًا منه، وسيكون التأثير الكلي متطابقًا. (نفترض هنا أن البت الكلاسيكي في الدائرة اليسرى لا يُكتب فوقه بعد إجراء القياس بواسطة قياس آخر — لكن لو حدث ذلك يمكننا دائمًا استخدام بت كلاسيكي جديد بدلًا من الكتابة فوق بت استُخدم لقياس سابق.)

حجم الدائرة وعمقها

حجم الدائرة

العدد الإجمالي للبوابات في دائرة ما يُشار إليه بـ حجم تلك الدائرة. بافتراض أن البوابات في دوائرنا تمثل عمليات أساسية، فإن حجم الدائرة يعكس عدد العمليات الأساسية التي تستلزمها — أو بعبارة أخرى، تكلفتها الحسابية. نكتب $\operatorname{size}(C)$ للإشارة إلى حجم دائرة معينة $C.$

على سبيل المثال، انظر إلى الدائرة البوليانية التالية لحساب XOR لبتين.

حجم هذه الدائرة هو 7 لأن فيها 7 بوابات إجمالًا. (لا تُحسب عمليات FANOUT دائمًا كبوابات، لكن لأغراض هذا الدرس سنحسبها كبوابات.)

الوقت والتكلفة وعمق الدائرة

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

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

لكن لاحظ أن حجم الدائرة لا يتوافق بالضرورة مباشرةً مع المدة الزمنية لتشغيلها. في دائرتنا البوليانية لحساب XOR لبتين، مثلًا، يمكن تنفيذ بوابتَي FANOUT في آنٍ واحد، وكذلك بوابتا NOT، فضلًا عن بوابتَي AND. طريقة مختلفة لقياس كفاءة الدوائر تأخذ في الاعتبار هذا الاحتمال بـ التوازي هي قياسها بـ العمق. وهو الحد الأدنى من طبقات البوابات المطلوبة داخل الدائرة، حيث تعمل البوابات في كل طبقة على أسلاك مختلفة. بصياغة أخرى، عمق الدائرة هو الحد الأقصى لعدد البوابات التي تصادفها على أي مسار من سلك دخل إلى سلك خرج. في الدائرة السابقة مثلًا، العمق يساوي 4.

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

تعيين تكاليف لبوابات مختلفة

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

على سبيل المثال، كما ذُكر آنفًا، كثيرًا ما تُعدّ بوابات FANOUT مجانية في الدوائر البوليانية — أي نختار أن تكلفتها صفر. مثال آخر، عند العمل في نموذج الاستعلام ونحسب عدد الاستعلامات التي تُجريها دائرة ما على دالة دخل (في شكل صندوق أسود)، فنحن فعليًا نعيّن تكلفة وحدة لبوابات الاستعلام وتكلفة صفر للبوابات الأخرى كبوابات Hadamard. مثال أخير هو أننا أحيانًا نعيّن تكاليف مختلفة للبوابات بحسب صعوبة تنفيذها، وهو ما قد يتباين تبعًا للعتاد المُستخدم.

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

التكلفة كدالة لطول المدخلات

نحن مهتمون أساسًا بكيفية تصاعد التكلفة الحسابية مع تنامي المدخلات. هذا يدفعنا إلى تمثيل تكاليف الخوارزميات كـ دوال لطول المدخلات.

عائلات الدوائر

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

على سبيل المثال، تخيّل أن لدينا خوارزمية كلاسيكية لتحليل الأعداد الصحيحة إلى عوامل، كتلك التي تستخدمها factorint. كأي خوارزمية كلاسيكية، يمكن تنفيذ هذه الخوارزمية باستخدام دوائر بوليانية — لكن للقيام بذلك سنحتاج إلى دائرة منفصلة لكل طول محتمل للمدخلات. لو نظرنا إلى الدوائر الناتجة عن أطوال مدخلات مختلفة، لرأينا أن أحجامها تنمو بشكل طبيعي مع نمو طول المدخلات — مما يعكس حقيقة أن تحليل الأعداد الصحيحة ذات 4 بتات أسهل بكثير ويتطلب عمليات أساسية أقل بكثير مقارنةً بتحليل الأعداد ذات 1024 بتًا، مثلًا.

هذا يدفعنا إلى تمثيل التكلفة الحسابية لخوارزمية ما بدالة $t,$ مُعرَّفة بحيث يكون $t(n)$ هو عدد البوابات في الدائرة التي تُنفذ الخوارزمية لمدخلات من $n$ بت. بمصطلحات أكثر رسمية، الخوارزمية في نموذج الدائرة البوليانية يصفها متتالية من الدوائر $\{C_1, C_2, C_3,\ldots\},$ حيث تحل $C_n$ أي مسألة نتحدث عنها لمدخلات من $n$ بت (أو بشكل أعم، لمدخلات يُمثَّل حجمها بطريقة ما بـ $n$)، والدالة $t$ التي تمثل تكلفة هذه الخوارزمية مُعرَّفة كالتالي:

$$t(n) = \operatorname{size}(C_n).$$

بالنسبة للدوائر الكمومية، الوضع مشابه، إذ تتطلب مدخلات أطول وأطول دوائر أكبر وأكبر.

مثال: جمع الأعداد الصحيحة

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

جمع الأعداد الصحيحة

المدخلات: أعداد صحيحة $N$ و $M$
المخرجات: $N+M$

كيف يمكننا تصميم دوائر بوليانية لحل هذه المسألة؟

لنبسّط الأمور، سنقصر اهتمامنا على الحالة التي يكون فيها $N$ و$M$ عددين صحيحين غير سالبين يُمثَّلان بسلاسل بتّية من $n$ بت باستخدام الترميز الثنائي. سنسمح بأي عدد من الأصفار البادئة في هذه الترميزات، بحيث يكون

$$0\leq N,M\leq 2^n - 1.$$

سيكون الناتج سلسلة ثنائية من $(n+1)$ بت تمثّل حاصل الجمع، وهو الحد الأقصى لعدد البتات التي نحتاجها للتعبير عن النتيجة.

نبدأ بخوارزمية — الخوارزمية المعيارية لجمع الأعداد الثنائية — وهي النظير في الأساس 2 للطريقة التي يُدرَّس بها الجمع في المدارس الابتدائية حول العالم. يمكن تنفيذ هذه الخوارزمية بدوائر بوليانية على النحو التالي.

بدءًا من البتات الأقل أهمية، يمكننا حساب XOR الخاص بها لتحديد البت الأقل أهمية في حاصل الجمع. ثم نحسب بت الحمل، وهو AND للبتَّتين الأقل أهمية في $N$ و$M.$ أحيانًا تُعرَف هاتان العمليتان معًا باسم نصف الجامع.

باستخدام دائرة XOR التي رأيناها عدة مرات مع بوابة AND وبوابتَي FANOUT، يمكننا بناء نصف جامع بـ 10 بوابات. لو غيّرنا رأينا لأي سبب وقرّرنا إدراج بوابات XOR في مجموعة عملياتنا الأساسية، سنحتاج إلى بوابة AND واحدة، وبوابة XOR واحدة، وبوابتَي FANOUT لبناء نصف الجامع.

للمضيّ قدمًا نحو البتات الأعلى أهمية، يمكننا استخدام إجراء مشابه، لكن هذه المرة ندرج بت الحمل من كل موضع سابق في حسابنا. بتتالي نصفَي جامعَين وأخذ OR لبتَّتَي الحمل اللتين ينتجانهما، يمكننا إنشاء ما يُعرَف بـ الجامع الكامل.

يتطلب هذا 21 بوابة إجمالاً: بوابتا AND، وبوابتا XOR (كل منهما تتطلب 7 بوابات للتنفيذ)، وبوابة OR واحدة، وأربع بوابات FANOUT.

أخيرًا، بتتالي الجامعات الكاملة، نحصل على دائرة بوليانية لجمع الأعداد الصحيحة غير السالبة. مثلاً، الدائرة التالية تحسب مجموع عددين صحيحين من 4 بتات.

بشكل عام، يتطلب هذا

$$21 (n-1) + 10 = 21 n - 11$$

بوابة. لو قرّرنا إدراج بوابات XOR في مجموعة عملياتنا الأساسية، سنحتاج إلى $2n-1$ بوابة AND، و$2n-1$ بوابة XOR، و$n-1$ بوابة OR، و$4n-2$ بوابة FANOUT، بمجموع $9n-5$ بوابة. وإن قرّرنا أيضًا عدم احتساب بوابات FANOUT، يصبح العدد $5n-3$ بوابة.

الترميز التقريبي

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

من ناحية أخرى، لو أجرينا التحليلات بهذا المستوى من التفصيل لجميع الحسابات التي يهمّنا دراستها، بما فيها تلك الخاصة بمهام أكثر تعقيدًا بكثير من الجمع، سنجد أنفسنا سريعًا مغرقين في التفاصيل. للحفاظ على الأمور قابلة للإدارة، وللتعمّد في إخفاء التفاصيل ذات الأهمية الثانوية، نستخدم عادةً ترميز Big-O عند تحليل الخوارزميات. من خلال هذا الترميز يمكننا التعبير عن رتبة نموّ الدوال.

رسمياً، إذا كانت لدينا دالتان $g(n)$ و$h(n),$ نكتب أن $g(n) = O(h(n))$ إذا وُجد عدد حقيقي موجب $c > 0$ وعدد صحيح موجب $n_0$ بحيث يكون

$$g(n) \leq c\cdot h(n)$$

لكل $n \geq n_0.$ عادةً يُختار $h(n)$ ليكون أبسط تعبير ممكن، حتى يمكن استخدام هذا الترميز للكشف عن السلوك الحدّي لدالة ما بصورة مبسّطة. مثلاً، $17 n^3 - 257 n^2 + 65537 = O(n^3).$

يمكن توسيع هذا الترميز ليشمل الدوال ذات المتغيرات المتعددة بطريقة مباشرة نسبيًا. على سبيل المثال، إذا كانت لدينا دالتان $g(n,m)$ و$h(n,m)$ معرَّفتان على الأعداد الصحيحة الموجبة $n$ و$m,$ نكتب أن $g(n,m) = O(h(n,m))$ إذا وُجد عدد حقيقي موجب $c > 0$ وعدد صحيح موجب $k_0$ بحيث يكون

$$g(n,m) \leq c\cdot h(n,m)$$

كلما كان $n+m \geq k_0.$

بربط هذا الترميز بمثال جمع الأعداد الصحيحة غير السالبة، نستنتج أنه توجد عائلة من الدوائر البوليانية $\{C_1, C_2,\ldots,\},$ حيث تجمع $C_n$ عددين صحيحين غير سالبين من $n$ بت، بحيث يكون $\operatorname{size}(C_n) = O(n).$ هذا يكشف الميزة الجوهرية لكيفية تدرُّج تكلفة الجمع مع حجم المدخلات: إنها تتدرَّج خطياً.

لاحظ أيضًا أن هذا لا يعتمد على التفصيلة المحددة المتعلقة بما إذا كنا نعتبر بوابات XOR ذات تكلفة وحدية أو تكلفة $7.$ بشكل عام، يتيح لنا استخدام ترميز Big-O إصدار تصريحات حول التكاليف الحسابية لا تتأثر بمثل هذه التفاصيل الدنيا.

أمثلة إضافية

إليك بعض الأمثلة الإضافية على مسائل من نظرية الأعداد الحسابية، نبدأ بـ الضرب.

Integer multiplication

Input: integers $N$ and $M$
Output: $NM$

إنشاء دوائر بوليانية لهذه المسألة أصعب من إنشائها للجمع — لكن بالتفكير في خوارزمية الضرب المعيارية، يمكننا التوصل إلى دوائر بحجم $O(n^2)$ لهذه المسألة (بافتراض أن $N$ و$M$ مُمثَّلان بتمثيلات ثنائية من $n$ بت). بشكل أعم، إذا كان $N$ يحتوي على $n$ بت و$M$ يحتوي على $m$ بت، توجد دوائر بوليانية بحجم $O(nm)$ لضرب $N$ في $M.$

ثمة في الواقع طرق أخرى للضرب تتدرَّج بصورة أفضل. مثلاً، يمكن استخدام خوارزمية ضرب شونهاغه-ستراسن لإنشاء دوائر بوليانية لضرب عددين صحيحين من $n$ بت بتكلفة $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ بيد أن تعقيد هذه الطريقة يُسبّب الكثير من العبء الإضافي، مما يجعلها عملية فقط للأعداد التي تحتوي على عشرات الآلاف من البتات.

مسألة أساسية أخرى هي القسمة، ونعني بها حساب كلٍّ من الحاصل والباقي معًا عند إعطاء مقسوم عليه ومقسوم.

Integer division

Input: integers $N$ and $M\neq0$
Output: integers $q$ and $r$ satisfying $0\leq r < |M|$ and $N = q M + r$

تكلفة قسمة الأعداد الصحيحة مشابهة للضرب: إذا كان $N$ يحتوي على $n$ بت و$M$ يحتوي على $m$ بت، توجد دوائر بوليانية بحجم $O(nm)$ لحل هذه المسألة. ومثل الضرب تمامًا، تُعرَف طرق أفضل تقاربياً.

يمكننا الآن مقارنة الخوارزميات المعروفة لحساب القواسم المشتركة الأكبر مع تلك الخاصة بالجمع والضرب. تتطلب خوارزمية إقليدس لحساب القاسم المشترك الأكبر لعدد $N$ من $n$ بت وعدد $M$ من $m$ بت دوائر بوليانية بحجم $O(nm)$، مشابهةً للخوارزميات المعيارية للضرب والقسمة. وكذلك الحال بالنسبة للضرب والقسمة، تُوجد خوارزميات للقاسم المشترك الأكبر أسرع تقاربياً — بما فيها تلك التي تتطلب $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ عملية أساسية لحساب القاسم المشترك الأكبر لعددين من $n$ بت.

حساب أكثر تكلفةً نسبياً يظهر في نظرية الأعداد هو الرفع الأسي المعياري.

Integer modular exponentiation

Input: integers $N,$ $K,$ and $M$ with $K\geq 0$ and $M\geq 1$
Output: $N^K \hspace{1mm} (\text{mod }M)$

بـ $N^K\hspace{1mm} (\text{mod }M)$ نعني الباقي عند قسمة $N^K$ على $M$، أي العدد الصحيح الفريد $r$ الذي يحقق $0\leq r < M$ و$N^K = q M + r$ لبعض الأعداد الصحيحة $q.$

إذا كان $N$ يحتوي على $n$ بت، و$M$ يحتوي على $m$ بت، و$K$ يحتوي على $k$ بت، يمكن حل هذه المسألة بدوائر بوليانية بحجم $O(k m^2 + nm).$ هذا ليس واضحًا على الإطلاق. الحل ليس حساب $N^K$ أولاً ثم أخذ الباقي، إذ سيستلزم ذلك استخدام عدد أسي من البتات فقط لتخزين العدد $N^K.$ بدلاً من ذلك، يمكننا استخدام خوارزمية القوة (المعروفة أيضًا بـ الطريقة الثنائية والتربيع المتكرر)، التي تستفيد من التمثيل الثنائي لـ $K$ لإجراء الحساب كله بالتلافي مع $M.$ بافتراض أن $N$ و$M$ و$K$ كلها أعداد من $n$ بت، نحصل على خوارزمية $O(n^3)$ — أو خوارزمية تكعيبية الزمن. ومرة أخرى، تُعرَف خوارزميات أكثر تعقيدًا لكنها أسرع تقاربياً.

تكلفة تحليل الأعداد إلى عوامل

على النقيض من الخوارزميات التي ناقشناها للتوّ، فإن الخوارزميات المعروفة لتحليل الأعداد الصحيحة إلى عوامل أكثر تكلفةً بكثير — كما قد نتوقع من المناقشة السابقة في هذا الدرس.

أحد الأساليب البسيطة للتحليل هو قسمة التجربة، حيث تبحث الخوارزمية في القائمة $2,\ldots,\sqrt{N}$ للعثور على عامل أولي لعدد المدخل $N.$ يتطلب هذا $O(2^{n/2})$ تكرارًا في أسوأ الحالات عندما يكون $N$ عددًا من $n$ بت. كل تكرار يتطلب قسمة تجريبية، مما يعني $O(n^2)$ عملية أساسية لكل تكرار (باستخدام خوارزمية معيارية لقسمة الأعداد الصحيحة). ننتهي بدوائر بحجم $O(n^2 2^{n/2})$، وهو حجم أسي بالنسبة لحجم المدخل $n.$

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

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

عملية أساسية لتحليل الأعداد من $n$ بت باحتمال عالٍ. بينما من المهم جداً أن $n$ مرفوع للأس $1/3$ في مؤشر هذا التعبير، فإن ظهوره في المؤشر لا يزال يُمثّل مشكلة تتسبب في تدرُّج سيئ — وهذا يُفسّر جزئياً لماذا لا يزال RSA1024 خارج نطاق تطبيقه.

التكلفة متعددة الحدود مقابل الأسية

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

كل هذه أمثلة على خوارزميات ذات تكلفة متعددة الحدود، مما يعني أن تكلفتها $O(n^c)$ لاختيار ثابت ثابت $c > 0.$ كتقريب أولي وتقريبي، تُنظَر الخوارزميات ذات التكلفة متعددة الحدود على أنها تمثّل خوارزميات فعّالة.

في المقابل، الخوارزميات الكلاسيكية المعروفة لتحليل الأعداد الصحيحة إلى عوامل لها تكلفة أسية. أحيانًا تُوصَف تكلفة غربال حقل الأعداد بأنها دون الأسية لأن $n$ مرفوع للأس $1/3$ في المؤشر، لكن في نظرية التعقيد الحسابي يُفضَّل حجز هذا المصطلح للخوارزميات التي تكون تكلفتها

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

لـ كل $\varepsilon > 0.$ تُشكّل مسائل ما يُعرَف بـ NP-complete فئة من المسائل غير المعروف عنها (ويُعتقد على نطاق واسع أنها لا تمتلك) خوارزميات بتكلفة متعددة الحدود. صياغة قائمة على الدوائر لـ فرضية الزمن الأسي تُقرّر شيئًا أقوى من هذا، وهو أن لا مسألة NP-complete يمكن أن تمتلك خوارزمية بتكلفة دون أسية.

يجب فهم ربط الخوارزميات ذات التكلفة متعددة الحدود بالخوارزميات الفعّالة على أنه تجريد فضفاض. بالطبع، لو كانت تكلفة خوارزمية ما تتدرَّج كـ $n^{1000}$ أو $n^{1000000}$ للمدخلات بحجم $n$، فإن وصف تلك الخوارزمية بالفعّالة يُعدّ مبالغةً. بيد أنه حتى الخوارزمية ذات التكلفة التي تتدرَّج كـ $n^{1000000}$ يجب أن تكون تفعل شيئًا ذكياً لتجنُّب التكلفة الأسية، وهو ما نتوقعه عمومًا من الخوارزميات القائمة بطريقة ما على "القوة الغاشمة" أو "البحث الشامل." حتى التحسينات المتطورة لغربال حقل الأعداد، على سبيل المثال، تفشل في تجنُّب هذا التدرُّج الأسي في التكلفة. الخوارزميات ذات التكلفة متعددة الحدود، من جهة أخرى، تنجح في الاستفادة من بنية المسألة بطريقة ما تتجنَّب فيها التدرُّج الأسي.

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

عند النظر في مزايا الحوسبة الكمية على الكلاسيكية، تتوجّه أنظارنا أولاً عمومًا نحو المزايا الأسية، أو على الأقل المزايا فوق متعددة الحدود — مع السعي المثالي لإيجاد خوارزميات كمية بتكلفة متعددة الحدود لمسائل لا تُعرَف لها خوارزميات كلاسيكية بتكلفة متعددة الحدود. المزايا النظرية بهذا الحجم تمتلك أكبر فرص للتحوّل إلى مزايا عملية فعلية — لكن تحديد هذه المزايا تحدٍّ بالغ الصعوبة. لا تُعرَف سوى أمثلة قليلة حتى الآن، لكن البحث مستمر.

المزايا متعددة الحدود (لكن ليس فوق متعددة الحدود) في التكلفة الحسابية للكمية على الكلاسيكية مثيرة للاهتمام أيضًا ولا ينبغي إهمالها — لكن نظرًا للفجوة الحالية بين تقنيتَي الحوسبة الكمية والكلاسيكية، يبدو أنها أقل إقناعًا في الوقت الراهن. لكن يومًا ما، يمكن أن تصبح مهمة. خوارزمية غروفر، على سبيل المثال، التي تُغطَّى في درس لاحق، توفّر ميزةً تربيعية للكمية على الكلاسيكية لما يُسمى البحث غير المهيكل، ولديها إمكانية تطبيقات واسعة.

تكلفة خفية في الحوسبة بالدوائر

ثمة مسألة أخيرة تستحق الذكر، وإن كنا لن نشغل أنفسنا بها في هذا الكورس. هناك تكلفة حسابية "خفية" عند التعامل مع الدوائر، وتتعلق بمواصفات الدوائر ذاتها. مع تطوّل المدخلات، تُطلَب دوائر أكبر وأكبر — لكننا بحاجة للحصول على أوصاف هذه الدوائر بطريقة ما إذا كنا سننفّذها.

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

لكن ماذا يحدث لو كانت هناك تكاليف حسابية باهظة مرتبطة بالأنماط في الدوائر نفسها؟ فعلى سبيل المثال، يمكن من حيث المبدأ أن يُحدَّد وصف كل عضو $C_n$ في عائلة دوائر بواسطة دالة يصعب حسابها جداً من $n.$

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