مفهوم نظرية التعقيد الكمي

نظرية التعقيد الكمي هي الحقل الفرعي لنظرية التعقيد الحسابي التي تتعامل مع فئات التعقيد المحددة باستخدام أجهزة الكمبيوتر الكمومية، وهو نموذج حسابي يعتمد على ميكانيكا الكم، حيث يدرس صلابة المشكلات الحسابية فيما يتعلق بفئات التعقيد هذه، وكذلك العلاقة بين فئات التعقيد الكمي وفئات التعقيد الكلاسيكية، ويوجد هناك فئتان مهمتان من فئات التعقيد الكمومي هما (BQP) و (QMA).

نظرية التعقيد الكمي

فئة التعقيد عبارة عن مجموعة من المشكلات الحسابية التي يمكن حلها بواسطة نموذج حسابي في ظل قيود موارد معينة، على سبيل المثال تُعرَّف فئة التعقيد (P) بأنها مجموعة المشكلات التي يمكن حلها بواسطة آلة تورينج في وقت متعدد الحدود. وبالمثل يمكن تعريف فئات التعقيد الكمومي باستخدام النماذج الكمية للحساب مثل نموذج الدائرة الكمومية أو آلة تورينج الكمومية المكافئة، إذ يتمثل أحد الأهداف الرئيسية لنظرية التعقيد الكمومي في معرفة كيفية ارتباط هذه الفئات بفئات التعقيد الكلاسيكية مثل (P) و (NP) و (BPP) و(PSPACE).

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

فئة المشكلات التي تحل بواسطة الكمبيوتر الكمي BQP

فئة المشكلات التي يمكن حلها بكفاءة بواسطة كمبيوتر كمي مع وجود خطأ محدود تسمى (BQP)، يعني خطأ محدود، زمن كمي، وقت متعدد الحدود، (BQP) هي فئة المشاكل التي يمكن حلها بواسطة آلة تورينج الكمومية متعددة الحدود مع احتمال خطأ يبلغ 1/3 على الأكثر.

كفئة من المشاكل الاحتمالية، (BQP) هو النظير الكمي لـ (BQP)، يعني الخطأ المحدود والاحتمالية والوقت متعدد الحدود وفئة المشكلات التي يمكن حلها بكفاءة بواسطة آلات تورينج الاحتمالية ذات الخطأ المحدود.

ومن المعروف أن () ويشتبه على نطاق واسع في ذلك، ولكن لم يتم إثبات ( )وهو ما يعني بشكل بديهي أن أجهزة الكمبيوتر الكمومية أقوى من أجهزة الكمبيوتر التقليدية من حيث تعقيد الوقت، حيث أن BQP هي مجموعة فرعية من (PP).

إن العلاقة الدقيقة لـ (BQP) بـ (P) و (NP) و (PSPACE) غير معروفة، ومع ذلك فمن المعروف أن ( )؛ أي أن فئة المشكلات التي يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكمومية تشمل جميع المشكلات التي يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكلاسيكية الحتمية، ولكنها لا تتضمن أي مشكلات لا يمكن حلها بواسطة أجهزة الكمبيوتر الكلاسيكية ذات موارد الفضاء متعددة الحدود، ومن المشتبه فيه أيضًا أن (BQP) عبارة عن مجموعة شاملة صارمة من (P).

مما يعني أن هناك مشكلات يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكمومية التي لا يمكن حلها بكفاءة بواسطة أجهزة الكمبيوتر الكلاسيكية الحتمية، على سبيل المثال تحليل العوامل الصحيحة ومسألة اللوغاريتم المنفصل من المعروف أنها موجودة في (BQP) ويُشتبه في أنها خارج (P)، وفيما يتعلق بعلاقة (BQP) بـ (NP)، حيث لا يُعرف الكثير بخلاف حقيقة أن بعض مشكلات (NP) موجودة في (BQP).

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

يمكن تلخيص علاقة BQP بفئات التعقيد الكلاسيكية الأساسية على النحو التالي:

• ( )، ومن المعروف أيضًا أن (BQP) موجود في فئة التعقيد أو بشكل أكثر دقة في فئة مشاكل القرار المرتبطة ،وهي مجموعة فرعية من (PSPACE).

تعقيد الاستعلام الكمي

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

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

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