وحدة المعالجة الكمية
علاقتها بنظرية الحوسبة والتعقيد > نظرية التعقيد الكمي

بينما لا تستطيع أجهزة الكمبيوتر الكمومية حل أي مشاكل لا تستطيع أجهزة الكمبيوتر الكلاسيكية حلها بالفعل، يُشتبه في قدرتها على حل مشكلات معينة بشكل أسرع من أجهزة الكمبيوتر التقليدية. على سبيل المثال، من المعروف أن أجهزة الكمبيوتر الكمومية يمكنها تحليل الأعداد الصحيحة بكفاءة، بينما لا يُعتقد أن هذا هو الحال بالنسبة لأجهزة الكمبيوتر الكلاسيكية.
تسمى فئة المشكلات التي يمكن حلها بكفاءة بواسطة كمبيوتر كمي مع وجود خطأ محدود بـ BQP، من أجل «الخطأ المحدود، الوقت الكمي، متعدد الحدود». بشكل أكثر رسمية، BQP هي فئة المشاكل التي يمكن حلها بواسطة آلة تورينج الكمومية متعددة الحدود مع احتمال خطأ يبلغ 1/3 على الأكثر. كفئة من المشاكل الاحتمالية، BQP هو النظير الكمي لـ BPP («الخطأ المحدود، الاحتمالي، الوقت متعدد الحدود»)، فئة المشاكل التي يمكن حلها بواسطة آلات تورينج الاحتمالية ذات الوقت متعدد الحدود مع الخطأ المحدود. من المعروف أن BPP  \subseteq  BQP ويشتبه على نطاق واسع أن BQP  \subsetneq  BPP، والتي تعني بشكل بديهي أن أجهزة الكمبيوتر الكمومية أقوى من أجهزة الكمبيوتر التقليدية من حيث تعقيد الوقت.
العلاقة الدقيقة لـ BQP بـ P وNP وPSPACE غير معروفة. ومع ذلك، فمن المعروف أن P.  \subseteq  BQP  \subseteq  PSPACE ؛ أي أن جميع المشكلات التي يمكن حلها بكفاءة بواسطة كمبيوتر كلاسيكي حتمي يمكن أيضًا حلها بكفاءة عن طريق الكمبيوتر الكمي، ويمكن أيضًا حل جميع المشكلات التي يمكن حلها بكفاءة عن طريق الكمبيوتر الكمي عن طريق كمبيوتر كلاسيكي حتمي مع موارد مساحة متعددة الحدود . ومن المشتبه فيه أيضًا أن BQP عبارة عن مجموعة شاملة صارمة من P، مما يعني أن هناك مشكلات يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكمومية التي لا يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكلاسيكية الحتمية. على سبيل المثال، من المعروف أن تحليل العوامل الصحيحة ومشكلة اللوغاريتم المنفصلة موجودان في BQP ويُشتبه في أنهما خارج P. فيما يتعلق بعلاقة BQP بـ NP، لا يُعرف سوى القليل بخلاف حقيقة أن بعض مشكلات NP التي يُعتقد أنها ليست في P هي أيضًا في BQP (التحليل الأعداد الصحيح ومسألة اللوغاريتم المنفصلة كلاهما في NP، على سبيل المثال). يشتبه في أن NP  \nsubseteq
\nsubseteq  BQP. أي أنه من المعتقد أن هناك مشاكل يمكن التحقق منها بكفاءة ولا يمكن حلها بكفاءة بواسطة الكمبيوتر الكمومي. كنتيجة مباشرة لهذا الاعتقاد، يُشتبه أيضًا في أن BQP منفصل عن فئة مشكلات NP الكاملة (إذا كانت مشكلة NP كاملة في BQP، فسيتبع ذلك من صلابة NP أن جميع المشكلات في NP موجودة BQP).
يمكن تلخيص علاقة BQP بفئات التعقيد الكلاسيكية الأساسية على النحو التالي:
 {\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}
ومن المعروف أيضًا أن BQP موجود في فئة التعقيد #P (أو بشكل أكثر دقة في فئة مشكلات القرار المرتبطة P #P)،  وهي فئة فرعية من PSPACE.
لقد تم التكهن بأن المزيد من التقدم في الفيزياء يمكن أن يؤدي إلى حواسيب أسرع. على سبيل المثال، لقد ثبت أن جهاز كمبيوتر كمي متغير مخفي غير محلي يعتمد على نظرية ميكانيكا دي بروي-بوم والتي يمكنها تنفيذ بحث عن  N -قاعدة بيانات بالعناصر على الأكثر  O({\sqrt[{3}]{N}}) خطوات، وهو تسريع طفيف على خوارزمية جروفر، والتي تعمل في  O({\sqrt {N}}) خطوات. لاحظ، مع ذلك، أن أيا من طرق البحث لن تسمح لأجهزة الكمبيوتر الكمومية بحل مشاكل NP الكاملة في وقت متعدد الحدود. قد تسمح نظريات الجاذبية الكمومية، مثل نظرية M والجاذبية الكمية الحلقية، ببناء حواسيب أسرع. ومع ذلك، فإن تحديد الحساب في هذه النظريات هو مشكلة مفتوحة بسبب مشكلة الوقت؛ أي أنه لا توجد حاليًا طريقة واضحة ضمن هذه النظريات الفيزيائية لوصف ما يعنيه أن يقوم المراقب بإرسال مدخلات إلى جهاز كمبيوتر في وقت واحد ثم تلقي الإخراج في وقت لاحق.