هل هناك فئة التعقيد QPP؟

Question

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

هل هناك فئة تعقيد مماثلة محددة جيدا "QPP" للمشاكل التي يحتوي كمبيوتر الكم على فرصة أكبر من 50٪ للحل بشكل صحيح في وقت متعدد الأصناف؟أفهم أنه إذا كان الأمر كذلك، فلن تكون هذه الفئة من المشكلات غير ممكنة على كمبيوتر الكم، ولكنها أي شموع من فئات التعقيد "الأكثر تقليدية" إما مثبتة أو مشتبه بها؟كيف "كبيرة" هل نعتقد أن الفئة QPP هي؟

Answer 1

أظهر Yamakami في ورقتهم تحليل وظائف الكم أن التناظرية الكموميةمن PP هو نفس PP الكلاسيكي.تم ذكر ذلك في مقالة Wikipedia في PP.