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

نظرية التعقيد الكمومي هي فرع من نظرية التعقيد الحسابي، وتتناول فئات التعقيد المُعرَّفة باستخدام الحواسيب الكمومية ، وهي نموذج حسابي قائم على ميكانيكا الكم . وتدرس هذه النظرية صعوبة المسائل الحسابية في ضوء فئات التعقيد هذه، بالإضافة إلى العلاقة بين فئات التعقيد الكمومي وفئات التعقيد الكلاسيكية (أي غير الكمومية).

هناك فئتان مهمتان من فئات التعقيد الكمي وهما BQP و QMA .

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

أحد أسباب دراسة نظرية التعقيد الكمومي هو تداعيات الحوسبة الكمومية على فرضية تشيرش-تورينج الحديثة . باختصار، تنص فرضية تشيرش-تورينج الحديثة على إمكانية محاكاة أي نموذج حسابي في زمن متعدد الحدود باستخدام آلة تورينج احتمالية . ^{[ 1 ] [ 2 ]} ومع ذلك، تبرز تساؤلات حول فرضية تشيرش-تورينج في سياق الحوسبة الكمومية. فمن غير الواضح ما إذا كانت هذه الفرضية تنطبق على نموذج الحوسبة الكمومية. وهناك أدلة كثيرة تشير إلى عدم صحتها. وقد لا يكون من الممكن لآلة تورينج احتمالية محاكاة نماذج الحوسبة الكمومية في زمن متعدد الحدود. ^{[ 1 ]}

غالبًا ما تُعبَّر التعقيدات الحسابية التقاربية لكل من الخوارزميات الكمومية والخوارزميات الكلاسيكية باستخدام الترميز التقاربي . ومن الأشكال الشائعة للترميز التقاربي للدوال ما يلي:${\displaystyle O(T(n))}$،${\displaystyle \Omega (T(n))}$، و${\displaystyle \Theta (T(n))}$.${\displaystyle O(T(n))}$يعبّر عن أن شيئًا ما محدود من الأعلى بواسطة${\displaystyle cT(n)}$أين${\displaystyle c}$ثابت بحيث${\displaystyle c>0}$و${\displaystyle T(n)}$هي وظيفة من${\displaystyle n}$،${\displaystyle \Omega (T(n))}$يعبّر عن أن شيئًا ما محدود من الأسفل بواسطة${\displaystyle cT(n)}$أين${\displaystyle c}$ثابت بحيث${\displaystyle c>0}$و${\displaystyle T(n)}$هي وظيفة من${\displaystyle n}$، و ${\displaystyle \Theta (T(n))}$يتبادلان الرسائل${\displaystyle O(T(n))}$و${\displaystyle \Omega (T(n))}$[ ^{3 ] هذه} الرموز لها أسماءها الخاصة أيضًا.${\displaystyle O(T(n))}$يُطلق عليه اسم ترميز Big O ،${\displaystyle \Omega (T(n))}$يُطلق عليه اسم تدوين أوميغا الكبير، و${\displaystyle \Theta (T(n))}$يُطلق عليه اسم تدوين ثيتا الكبير.

يمكن مقارنة فئات التعقيد المهمة P وBPP وBQP وPP وPSPACE بناءً على مسائل الوعد . مسألة الوعد هي مسألة قرار يُفترض فيها اختيار مُدخل من بين جميع سلاسل الإدخال الممكنة. مسألة الوعد هي زوج من${\displaystyle A=(A_{\text{yes}},A_{\text{no}})}$، أين${\displaystyle A_{\text{yes}}}$هي مجموعة الحالات التي تكون فيها الإجابة بنعم و${\displaystyle A_{\text{no}}}$هي مجموعة لا تحتوي على أي حالات، وتقاطع هذه المجموعات فارغ:${\displaystyle A_{\text{yes}}\cap A_{\text{no}}=\varnothing }$جميع فئات التعقيد السابقة تحتوي على مسائل وعد. ^{[ 4 ]}

فئة التعقيد	معايير
P	مسائل الوعد التي تقبل فيها آلة تورينج الحتمية ذات الوقت متعدد الحدود جميع السلاسل في${\displaystyle A_{\text{yes}}}$ويرفض جميع السلاسل في${\displaystyle A_{\text{no}}}$[ 4 ]
بي بي بي	مسائل الوعد التي تقبل فيها آلة تورينج الاحتمالية ذات الوقت متعدد الحدود كل سلسلة في${\displaystyle A_{\text{yes}}}$باحتمالية لا تقل عن${\displaystyle {\frac {2}{3}}}$ويقبل كل سلسلة نصية في${\displaystyle A_{\text{no}}}$باحتمالية لا تتجاوز${\displaystyle {\frac {1}{3}}}$[ 4 ]
BQP	مشاكل الوعود بحيث بالنسبة للدوال${\displaystyle a,b:\mathbb {N} \to [0,1]}$توجد عائلة من الدوائر الكمومية يتم توليدها في وقت متعدد الحدود${\displaystyle Q={\{Q_{n}:n\in \mathbb {N} \}}}$، أين${\displaystyle Q_{n}}$هي دائرة تقبل${\displaystyle n}$الكيوبتات ويعطي مخرجًا من كيوبت واحد. عنصر${\displaystyle x}$ل${\displaystyle A_{\text{yes}}}$مقبول من قبل${\displaystyle Q}$باحتمالية أكبر من أو تساوي${\displaystyle a(\left\vert x\right\vert )}$عنصر${\displaystyle x}$ل${\displaystyle A_{\text{no}}}$مقبول من قبل${\displaystyle Q}$باحتمالية أقل من أو تساوي${\displaystyle b(\left\vert x\right\vert )}$[ 4 ]​
PP	مسائل الوعد التي تقبل فيها آلة تورينج الاحتمالية ذات الوقت متعدد الحدود كل سلسلة في${\displaystyle A_{\text{yes}}}$باحتمالية أكبر من${\displaystyle {\frac {1}{2}}}$ويقبل كل سلسلة نصية في${\displaystyle A_{\text{no}}}$باحتمالية لا تتجاوز${\displaystyle {\frac {1}{2}}}$[ 4 ]
بي سبيس	مشاكل الوعد التي تقبل فيها آلة تورينج حتمية تعمل في فضاء متعدد الحدود كل سلسلة في${\displaystyle A_{\text{yes}}}$ويرفض جميع السلاسل في${\displaystyle A_{\text{no}}}$[ 4 ]

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

باعتبارها فئة من المسائل الاحتمالية، تُعدّ BQP النظير الكمومي لـ BPP ("خطأ محدود، احتمالي، زمن متعدد الحدود")، وهي فئة من المسائل التي يمكن حلها بكفاءة بواسطة آلات تورينغ الاحتمالية ذات الخطأ المحدود. ^{[ 6 ]} من المعروف أن${\displaystyle {\mathsf {BPP\subseteq BQP}}}$ويشتبه على نطاق واسع، ولكن لم يتم إثبات ذلك، أن${\displaystyle {\mathsf {BQP\nsubseteq BPP}}}$وهذا يعني بديهياً أن الحواسيب الكمومية أقوى من الحواسيب التقليدية من حيث التعقيد الزمني. ^{[ 7 ]} BQP هي مجموعة فرعية من PP .

العلاقة الدقيقة بين BQP و P و NP و PSPACE غير معروفة. ومع ذلك، من المعروف أن${\displaystyle {\mathsf {P\subseteq BQP\subseteq PSPACE}}}$أي أن فئة المسائل التي يمكن حلها بكفاءة بواسطة الحواسيب الكمومية تشمل جميع المسائل التي يمكن حلها بكفاءة بواسطة الحواسيب الكلاسيكية الحتمية، ولكنها لا تشمل أي مسائل لا يمكن حلها بواسطة الحواسيب الكلاسيكية ذات الموارد المكانية متعددة الحدود. ويُشتبه أيضًا في أن BQP هي مجموعة شاملة صارمة من P، مما يعني وجود مسائل يمكن حلها بكفاءة بواسطة الحواسيب الكمومية ولا يمكن حلها بكفاءة بواسطة الحواسيب الكلاسيكية الحتمية. على سبيل المثال، من المعروف أن تحليل الأعداد الصحيحة إلى عواملها الأولية ومسألة اللوغاريتم المنفصل تنتميان إلى BQP، ويُشتبه في أنهما خارج P. أما فيما يتعلق بعلاقة BQP بـ NP، فلا يُعرف الكثير سوى أن بعض مسائل NP تنتمي إلى BQP (تحليل الأعداد الصحيحة إلى عواملها الأولية ومسألة اللوغاريتم المنفصل تنتميان إلى NP، على سبيل المثال). ويُشتبه في أن${\displaystyle {\mathsf {NP\nsubseteq BQP}}}$أي أنه يُعتقد بوجود مسائل قابلة للتحقق بكفاءة، لكنها غير قابلة للحل بكفاءة بواسطة الحاسوب الكمومي. وكنتيجة مباشرة لهذا الاعتقاد، يُشتبه أيضًا في أن BQP منفصلة عن فئة مسائل NP-الكاملة (إذا كانت أي مسألة NP-كاملة موجودة في BQP، فإنه يترتب على صعوبة NP أن جميع المسائل في NP موجودة في BQP). ^{[ 8 ]}

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

${\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}}$

ومن المعروف أيضاً أن BQP تندرج ضمن فئة التعقيد ⁠${\displaystyle \color {Blue}{\mathsf {\#P}}}$( أو بتعبير أدق في فئة مشاكل القرار المرتبطة بها )${\displaystyle {\mathsf {P^{\#P}}}}$) ، ^{[ 8 ]} وهو مجموعة فرعية من PSPACE .

لا توجد طريقة معروفة لمحاكاة نموذج حسابي كمومي بكفاءة باستخدام حاسوب تقليدي. هذا يعني أن الحاسوب التقليدي لا يستطيع محاكاة نموذج حسابي كمومي في وقت متعدد الحدود. ومع ذلك، فإن الدائرة الكمومية من${\displaystyle S(n)}$الكيوبتات مع${\displaystyle T(n)}$يمكن محاكاة البوابات الكمومية بواسطة دائرة كلاسيكية مع${\displaystyle O(2^{S(n)}T(n)^{3})}$البوابات الكلاسيكية . ^{[ 3 ]} يُحدد عدد البوابات الكلاسيكية بتحديد عدد عمليات البت اللازمة لمحاكاة الدائرة الكمومية. وللقيام بذلك، تُحسب أولًا السعات المرتبطة بـ${\displaystyle S(n)}$يجب أخذ الكيوبتات في الحسبان. كل حالة من حالات${\displaystyle S(n)}$يمكن وصف الكيوبتات بمتجه مركب ثنائي الأبعاد، أو متجه حالة. ويمكن أيضًا وصف متجهات الحالة هذه بتركيبة خطية من متجهاتها المكونة لها ، بمعاملات تُسمى السعات. هذه السعات أعداد مركبة مُعَيَّرة إلى واحد، أي أن مجموع مربعات القيم المطلقة للسعات يجب أن يساوي واحدًا. ^{[ 3 ]} عناصر متجه الحالة هي هذه السعات. كل سعة، تعمل كمعاملات في وصف التركيبة الخطية، تُقابل مكونًا غير صفري من متجه الحالة. ويُعبَّر عن ذلك بالمعادلة التالية:${\displaystyle \alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$أو${\displaystyle \alpha \left\vert 1\right\rangle +\beta \left\vert 0\right\rangle ={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$باستخدام ترميز ديراك . حالة الكل${\displaystyle S(n)}$يمكن وصف نظام الكيوبتات بمتجه حالة واحد. هذا المتجه، الذي يصف النظام بأكمله، هو حاصل الضرب الموتري لمتجهات الحالة التي تصف الكيوبتات الفردية في النظام. نتيجة حاصل الضرب الموتري لـ${\displaystyle S(n)}$الكيوبت هو متجه حالة واحد يحتوي على${\displaystyle 2^{S(n)}}$الأبعاد والمدخلات التي تمثل السعات المرتبطة بكل حالة أساسية أو متجه مكون. لذلك،${\displaystyle 2^{S(n)}}$يجب مراعاة السعات باستخدام${\displaystyle 2^{S(n)}}$متجه معقد ذو أبعاد، وهو متجه الحالة لـ${\displaystyle S(n)}$نظام الكيوبت. ^{[ 9 ]} من أجل الحصول على حد أعلى لعدد البوابات المطلوبة لمحاكاة دائرة كمومية، نحتاج إلى حد أعلى كافٍ لكمية البيانات المستخدمة لتحديد المعلومات المتعلقة بكل منها.${\displaystyle 2^{S(n)}}$السعات. للقيام بذلك${\displaystyle O(T(n))}$تكفي وحدات الدقة لترميز كل سعة. ^{[ 3 ]} لذا يتطلب الأمر${\displaystyle O(2^{S(n)}T(n))}$البتات الكلاسيكية لحساب متجه الحالة لـ${\displaystyle S(n)}$نظام الكيوبت. ثم تطبيق${\displaystyle T(n)}$البوابات الكمومية على ${\displaystyle 2^{S(n)}}$يجب مراعاة السعات. يمكن تمثيل البوابات الكمومية على النحو التالي:${\displaystyle 2^{S(n)}\times 2^{S(n)}}$المصفوفات المتفرقة . ^{[ 3 ]} لذا، لشرح تطبيق كل منها${\displaystyle T(n)}$في البوابات الكمومية، يجب ضرب متجه الحالة بـ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$مصفوفة متفرقة لكل من${\displaystyle T(n)}$البوابات الكمومية. في كل مرة يتم فيها ضرب متجه الحالة بـ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$المصفوفة المتفرقة،${\displaystyle O(2^{S(n)})}$يجب إجراء العمليات الحسابية. ^{[ 3 ]} لذلك، هناك${\displaystyle O(2^{S(n)}T(n)^{2})}$عمليات البت لكل بوابة كمومية مطبقة على متجه الحالة. لذا${\displaystyle O(2^{S(n)}T(n)^{2})}$البوابات الكلاسيكية ضرورية للمحاكاة${\displaystyle S(n)}$دائرة كيوبت ببوابة كمومية واحدة فقط. لذلك،${\displaystyle O(2^{S(n)}T(n)^{3})}$البوابات الكلاسيكية ضرورية لمحاكاة دارة كمومية من${\displaystyle S(n)}$الكيوبتات مع${\displaystyle T(n)}$البوابات الكمومية. ^{[ 3 ]} في حين أنه لا توجد طريقة معروفة لمحاكاة حاسوب كمومي بكفاءة باستخدام حاسوب كلاسيكي، فمن الممكن محاكاة حاسوب كلاسيكي بكفاءة باستخدام حاسوب كمومي. ويتضح ذلك من حقيقة أن${\displaystyle {\mathsf {BPP\subseteq BQP}}}$[ ^{4 ]​}

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

تعقيد الاستعلام الكمومي لأنواع معينة من مسائل الرسم البياني

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

تعقيد الاستعلام الكمومي لأنواع معينة من مسائل الرسم البياني

مشكلة	نموذج المصفوفة	نموذج المصفوفة
شجرة ذات امتدادات دنيا	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Theta ({\sqrt {nm}})}$
الاتصال	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Theta (n)}$
اتصال قوي	${\displaystyle \Theta (n^{3/2})}$	${\displaystyle \Omega ({\sqrt {nm}})}$،${\displaystyle O({\sqrt {nm\log(n)}})}$
أقصر مسار من مصدر واحد	${\displaystyle \Omega (n^{3/2})}$،${\displaystyle O(n^{3/2}\log ^{2}n)}$	${\displaystyle \Omega ({\sqrt {nm}})}$،${\displaystyle O({\sqrt {nm}}\log ^{2}(n))}$

لاحظ التباين بين تعقيدات الاستعلام الكمومي المرتبطة بنوع معين من المسائل، وذلك تبعًا لنموذج الاستعلام المستخدم لتحديد التعقيد. على سبيل المثال، عند استخدام نموذج المصفوفة، يكون التعقيد الكمومي لنموذج الاتصال في ترميز Big O هو${\displaystyle \Theta (n^{3/2})}$لكن عند استخدام نموذج المصفوفة، يكون التعقيد${\displaystyle \Theta (n)}$بالإضافة إلى ذلك، وللاختصار، نستخدم الاختصار${\displaystyle m}$في حالات معينة، حيث${\displaystyle m=\Theta (n^{2})}$[ ^{11 ] إن} الدلالة المهمة هنا هي أن كفاءة الخوارزمية المستخدمة لحل مشكلة الرسم البياني تعتمد على نوع نموذج الاستعلام المستخدم لنمذجة الرسم البياني.

يُعتقد أن المزيد من التطورات في الفيزياء قد تؤدي إلى حواسيب أسرع. على سبيل المثال، ثبت أن حاسوبًا كميًا غير محلي، ولكنه لا يُرسل إشارات، يعتمد على متغيرات خفية، يمكنه تنفيذ عملية بحث في قاعدة بيانات تحتوي على N عنصرًا في زمن لا يتجاوز${\displaystyle O({\sqrt[{3}]{N}})}$خطوات، مما يُحقق تسارعًا طفيفًا مقارنةً بخوارزمية جروفر ، التي تعمل في${\displaystyle O({\sqrt {N}})}$خطوات. مع ذلك، تجدر الإشارة إلى أن أيًا من طريقتي البحث لا تسمح لأجهزة الكمبيوتر الكمومية بحل مسائل NP-complete في وقت متعدد الحدود. ^{[ 13 ]} قد تسمح نظريات الجاذبية الكمومية ، مثل نظرية M وجاذبية الحلقات الكمومية ، ببناء أجهزة كمبيوتر أسرع. ومع ذلك، فإن تعريف الحوسبة في هذه النظريات يمثل مشكلة مفتوحة بسبب مشكلة الزمن ؛ أي أنه ضمن هذه النظريات الفيزيائية، لا توجد حاليًا طريقة واضحة لوصف ما يعنيه بالنسبة للمراقب أن يُدخل بيانات إلى جهاز كمبيوتر في لحظة زمنية معينة ثم يتلقى مخرجات في لحظة زمنية لاحقة. ^{[ 14 ] [ 15 ]}

• الحوسبة الكمومية
• آلة تورينج الكمومية
• التسلسل الهرمي متعدد الحدود (PH)

• نيلسن، مايكل ؛ تشوانغ، إسحاق (2000). الحوسبة الكمومية والمعلومات الكمومية . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-63503-5. OCLC 174527496 . 
• أرورا، سانجيف ؛ باراك، بواز (2016). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج. ص 201-236 . ISBN  978-0-521-42426-4.
• واتروس، جون (2008). "التعقيد الحسابي الكمي". arXiv : 0804.3401v1 [ quant-ph ].
• واتروس، ج. (2009) . التعقيد الحسابي الكمي . في: مايرز، ر. (محرر). موسوعة التعقيد وعلوم الأنظمة. سبرينغر، نيويورك، نيويورك.

• محاضرات سكوت آرونسون في معهد ماساتشوستس للتكنولوجيا