زمن متعدد الحدود الكمومي الدقيق

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
الموسوعة الحرة

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

في التعريف الأصلي لمسألة البرمجة الكمومية الموسعة (EQP)، كانت كل لغة تُحسب بواسطة آلة تورينج كمومية واحدة (QTM)، باستخدام مجموعة بوابات محدودة يمكن حساب سعاتها في زمن متعدد الحدود. مع ذلك، تطلبت بعض النتائج استخدام مجموعة بوابات غير محدودة. عادةً ما تكون سعات مجموعة البوابات أعدادًا جبرية.

مراجع