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
















