BQP

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 78 صور
الموسوعة الحرة
مخطط فئات التعقيد العشوائي
BQP فيما يتعلق بفئات التعقيد الاحتمالي الأخرى ( ZPP ، RP ، co-RP، BPP ، PP )، والتي تعمم P ضمن PSPACE . من غير المعروف ما إذا كانت أي من هذه القيود صارمة.

في نظرية التعقيد الحسابي ، تُعرف مسائل القرار ذات الوقت الكمومي متعدد الحدود المحدود الخطأ ( BQP ) بأنها فئة من مسائل القرار التي يمكن حلها بواسطة حاسوب كمومي في وقت متعدد الحدود ، باحتمالية خطأ لا تتجاوز 1/3 لجميع الحالات. [ 1 ] وهي النظير الكمومي لفئة التعقيد BPP .

تُعتبر مسألة القرار عضوًا في مجموعة BQP إذا وُجدت خوارزمية كمومية ( خوارزمية تعمل على حاسوب كمومي) تحل مسألة القرار باحتمالية عالية ، ومضمونة التنفيذ في زمن متعدد الحدود. سيحل تشغيل الخوارزمية مسألة القرار بشكل صحيح باحتمالية لا تقل عن 2/3.

خوارزمية BQP (تشغيل واحد)
إجابة
تم إنتاجه
الإجابة الصحيحة
نعملا
نعم≥ 2/3≤ 1/3
لا≤ 1/3≥ 2/3
خوارزمية BQP (عدد مرات التشغيل k )
إجابة
تم إنتاجه
الإجابة الصحيحة
نعملا
نعم> 1 − 2 − ck< 2 − ck
لا< 2 − ck> 1 − 2 − ck
لبعض الثوابت c > 0

تعريف

يمكن اعتبار BQP بمثابة اللغات المرتبطة بعائلات محددة من الدوائر الكمومية ذات الخطأ المحدود والموحدة . [ 1 ] تنتمي اللغة L إلى BQP إذا وفقط إذا وُجدت عائلة موحدة من الدوائر الكمومية ذات زمن متعدد الحدود.{سؤالن:ن∈شمال}{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}بحيث

  • للجميعن∈شمال{\displaystyle n\in \mathbb {N} }تأخذ الدالة Q n عدد n من الكيوبتات كمدخلات وتُخرج بتًا واحدًا
  • لكل x في L ،Pر(سؤال|x|(x)=1)≥23{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}
  • لكل x ليس في L ،Pر(سؤال|x|(x)=0)≥23{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}

بدلاً من ذلك، يمكن تعريف BQP بدلالة آلات تورينج الكمومية . تنتمي اللغة L إلى BQP إذا وفقط إذا وُجدت آلة تورينج كمومية متعددة الحدود تقبل L باحتمالية خطأ لا تتجاوز 1/3 لجميع الحالات. [ 2 ]

على غرار فئات الاحتمالات الأخرى ذات "الخطأ المحدود"، فإن اختيار 1/3 في التعريف اختياري. يمكننا تشغيل الخوارزمية عددًا ثابتًا من المرات، ثم اعتماد تصويت الأغلبية لتحقيق أي احتمال صحة مطلوب أقل من 1، باستخدام حد تشيرنوف . لا تتغير فئة التعقيد سواءً سمحنا بخطأ يصل إلى 1/2 − n − c من جهة، أو اشترطنا خطأً صغيرًا يصل إلى 2 − n c من جهة أخرى، حيث c أي ثابت موجب، و n طول المدخلات. [ 3 ]

العلاقة بفئات التعقيد الأخرى

مشكلة لم تُحل في علوم الحاسوب
ما هي العلاقة بينبسؤالP{\displaystyle {\mathsf {BQP}}}وشمالP{\displaystyle {\mathsf {NP}}}؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب
العلاقة المشتبه بها بين BQP ومساحات المشاكل الأخرى [ 1 ]

يُعرَّف BQP للحواسيب الكمومية؛ أما فئة التعقيد المقابلة للحواسيب التقليدية (أو بشكل أدق لآلات تورينج الاحتمالية ) فهي BPP . ومثل P و BPP ، فإن BQP منخفض بالنسبة لنفسه، مما يعني أن BQP = BQP . [ 2 ] وبصورة غير رسمية، هذا صحيح لأن خوارزميات الوقت متعدد الحدود مغلقة تحت التركيب. فإذا استدعت خوارزمية ذات وقت متعدد الحدود خوارزميات أخرى ذات وقت متعدد الحدود كإجراءات فرعية، فإن الخوارزمية الناتجة تظل ذات وقت متعدد الحدود.

تتضمن BQP كلاً من P و BPP ، وهي مُضمنة في AWPP [ 4 ] وPP [ 5 ] و PSPACE [ 2 ] . في الواقع، تُعتبر BQP منخفضة بالنسبة لـ PP ، مما يعني أن آلة PP لا تستفيد من قدرتها على حل مسائل BQP بشكل فوري، وهو ما يُشير إلى الاختلاف المُحتمل في الأداء بين هذه الفئات المُتشابهة. العلاقات المعروفة مع فئات التعقيد الكلاسيكية هي:

P⊆بPP⊆بسؤالP⊆أدبليوPP⊆PP⊆PSPأجهـ⊆هـXP{\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}}

باعتبارها مشكلة ⁠P =؟ PSPأجهـ{\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}}لم يتم حل هذه المسألة بعد، ويُفترض أن إثبات عدم المساواة بين BQP والفئات المذكورة أعلاه أمرٌ صعب. [ 2 ] العلاقة بين BQP و NP غير معروفة. في مايو 2018، نشر عالما الحاسوب ران راز من جامعة برينستون وأفيشاي تال من جامعة ستانفورد ورقة بحثية [ 6 ] أظهرت أنه بالنسبة إلى وسيط ، فإن BQP لا تندرج ضمن PH . يمكن إثبات وجود وسيط A بحيثبسؤالPأ⊈Pحأ{\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }}[ 7 ] بمعنى غير رسمي للغاية، يمكن اعتبار هذا بمثابة منح PH وBQP قدرةً متطابقةً، ولكنها إضافية، والتحقق من أن BQP مع الوسيط (BQP A ) قادر على القيام بأمور لا يستطيع PH A القيام بها . مع أن فصل الوسيط قد ثبت، إلا أن عدم احتواء PH على BQP لم يُثبت بعد. فصل الوسيط لا يُثبت ما إذا كانت فئات التعقيد متطابقة أم لا. يُعطي فصل الوسيط حدسًا بأن BQP قد لا يكون مُحتوىً في PH.

لطالما ساد الاعتقاد لسنوات عديدة بأن مشكلة أخذ عينات فورييه تندرج ضمن فئة BQP، ولكنها لا تندرج ضمن التسلسل الهرمي متعدد الحدود. وقد قدمت فرضيات حديثة أدلة على وجود مشكلة مماثلة، وهي التحقق من فورييه، ضمن فئة BQP دون أن تكون جزءًا من التسلسل الهرمي متعدد الحدود . وتكتسب هذه الفرضية أهمية خاصة لأنها تشير إلى إمكانية تصنيف المشكلات الموجودة في BQP على أنها أصعب من مشكلات NP-Complete . وبالنظر إلى الاشتباه في وجود العديد من مشكلات BQP العملية خارج فئة P (وهو احتمال لم يتم التحقق منه لعدم وجود دليل على أن P ≠ NP )، فإن هذا يوضح الإمكانات الهائلة للحوسبة الكمومية مقارنةً بالحوسبة الكلاسيكية. [ 7 ]

تؤدي إضافة عملية الاختيار اللاحق إلى BQP إلى فئة التعقيد PostBQP والتي تساوي PP . [ 8 ] [ 9 ]

مشكلة كاملة لـ Promise-BQP

تُعدّ Promise-BQP فئة من مسائل الوعد التي يمكن حلّها بواسطة مجموعة موحدة من الدوائر الكمومية (أي ضمن BQP). [ 10 ] تركز براهين الاكتمال على هذا الإصدار من BQP. على غرار مفهوم اكتمال NP والمسائل الكاملة الأخرى ، يمكننا تعريف المسألة الكاملة بأنها مسألة تنتمي إلى Promise-BQP، وأن كل مسألة أخرى في Promise-BQP تختزل إليها في وقت متعدد الحدود.

APPROX-QCIRCUIT-PROB

تُعدّ مسألة APPROX-QCIRCUIT-PROB كاملةً بالنسبة للحوسبة الكمومية الفعّالة، والنسخة المعروضة أدناه كاملة لفئة تعقيد Promise-BQP (وليس لفئة تعقيد BQP الكاملة، التي لا توجد مسائل كاملة معروفة لها). إنّ اكتمال مسألة APPROX-QCIRCUIT-PROB يجعلها مفيدةً في البراهين التي تُظهر العلاقات بين فئات التعقيد الأخرى وBQP.

بفرض وصف لدائرة كمومية C تعمل على n كيوبت باستخدام m بوابة، حيث m متعددة حدود في n وتعمل كل بوابة على كيوبت واحد أو اثنين، وعددينα،β∈[0،1]،α>β{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }، ميز بين الحالتين التاليتين:

  • قياس الكيوبت الأول للحالةج|0⟩⊗ن{\displaystyle C|0\rangle ^{\otimes n}}العائد|1⟩{\displaystyle |1\rangle }باحتمال≥α{\displaystyle \geq \alpha }
  • قياس الكيوبت الأول للحالةج|0⟩⊗ن{\displaystyle C|0\rangle ^{\otimes n}}العائد|1⟩{\displaystyle |1\rangle }باحتمال≤β{\displaystyle \leq \beta }

هنا، يوجد وعد بشأن المدخلات لأن المشكلة لا تحدد السلوك إذا لم يتم تغطية حالة ما بهاتين الحالتين.

الادعاء. أي مشكلة BQP تختزل إلى APPROX-QCIRCUIT-PROB.

البرهان. لنفترض أن لدينا خوارزمية A تحل مسألة APPROX-QCIRCUIT-PROB، أي، بمعلومية دائرة كمومية C تعمل على n كيوبت، وعددينα،β∈[0،1]،α>β{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }يُفرّق A بين الحالتين المذكورتين أعلاه. يمكننا حل أي مشكلة في BQP باستخدام هذا المرجع، عن طريق ضبطα=2/3،β=1/3{\displaystyle \alpha =2/3,\beta =1/3}.

لأيل∈بسؤالP{\displaystyle L\in {\mathsf {BQP}}}توجد عائلة من الدوائر الكمومية{سؤالن:ن∈شمال}{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}بحيث يكون ذلك لجميعن∈شمال{\displaystyle n\in \mathbb {N} }، ولاية|x⟩{\displaystyle |x\rangle }ل ن{\displaystyle n} الكيوبتات، إذاx∈ل،Pر(سؤالن(|x⟩)=1)≥2/3{\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3}وإلا إذا x∉ل،Pر(سؤالن(|x⟩)=0)≥2/3{\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3}. أصلح المدخل|x⟩{\displaystyle |x\rangle }من n كيوبت، والدائرة الكمومية المقابلةسؤالن{\displaystyle Q_{n}}يمكننا أولاً إنشاء دائرة كهربائيةجx{\displaystyle C_{x}}بحيثجx|0⟩⊗ن=|x⟩{\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle }يمكن القيام بذلك بسهولة عن طريق التوصيل المباشر.|x⟩{\displaystyle |x\rangle }ونطبق سلسلة من بوابات CNOT لقلب الكيوبتات. ثم يمكننا دمج دائرتين للحصول علىج′=سؤالنجx{\displaystyle C'=Q_{n}C_{x}}والآنج′|0⟩⊗ن=سؤالن|x⟩{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }وأخيراً، بالضرورة نتائجسؤالن{\displaystyle Q_{n}}يتم الحصول على ذلك عن طريق قياس عدة كيوبتات وتطبيق بعض البوابات المنطقية (الكلاسيكية) عليها. يمكننا دائمًا تأجيل القياس [ 11 ] [ 12 ] وإعادة توجيه الدوائر بحيث يتم قياس الكيوبت الأول منج′|0⟩⊗ن=سؤالن|x⟩{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }نحصل على الناتج. ستكون هذه هي الدائرة C ، ونحدد انتماءx∈ل{\displaystyle x\in L}عن طريق الجري أ(ج){\displaystyle A(C)}معα=2/3،β=1/3{\displaystyle \alpha =2/3,\beta =1/3}بحسب تعريف BQP، سنقع إما في الحالة الأولى (القبول)، أو الحالة الثانية (الرفض)، لذلكل∈بسؤالP{\displaystyle L\in {\mathsf {BQP}}}يختزل إلى APPROX-QCIRCUIT-PROB.

BQP و EXP

نبدأ باحتواء أسهل. لنُظهر ذلك.بسؤالP⊆هـXP{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}، يكفي أن نوضح أن APPROX-QCIRCUIT-PROB موجود في EXP لأن APPROX-QCIRCUIT-PROB هو BQP-كامل.

مطالبة -APPROX-QCIRCUIT-PROB∈هـXP{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}

دليل

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

بصورة أكثر رسمية، ليكن C دائرة كمومية ذات حجم متعدد الحدود على n كيوبت و m بوابة، حيث m متعدد الحدود في n.|ψ0⟩=|0⟩⊗ن{\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}}و|ψأنا⟩{\displaystyle |\psi _{i}\rangle }ليكن هذا هو الوضع بعد تطبيق البوابة رقم i في الدائرة على|ψأنا-1⟩{\displaystyle |\psi _{i-1}\rangle }كل ولاية|ψأنا⟩{\displaystyle |\psi _{i}\rangle }يمكن تمثيلها في الحاسوب الكلاسيكي كمتجه وحدة فيج2ن{\displaystyle \mathbb {C} ^{2^{n}}}علاوة على ذلك، يمكن تمثيل كل بوابة بمصفوفة في ج2ن×2ن{\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}وبالتالي، الحالة النهائية|ψم⟩{\displaystyle |\psi _{m}\rangle }يمكن حسابها فييا(م⋅22ن){\displaystyle O(m\cdot 2^{2n})}مع مرور الوقت، وبالتالي جميعنا معًا، لدينا2يا(ن){\displaystyle 2^{O(n)}}خوارزمية زمنية لحساب الحالة النهائية، وبالتالي احتمال أن تكون قيمة الكيوبت الأول واحدًا. وهذا يعني أنAPPROX-QCIRCUIT-PROB∈هـXP{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}.

لاحظ أن هذه الخوارزمية تتطلب أيضًا2يا(ن){\displaystyle 2^{O(n)}}مساحة لتخزين المتجهات والمصفوفات. سنوضح في القسم التالي أنه يمكننا تحسين تعقيد المساحة.

BQP و PSPACE

تُعدّ تقنية مجموع التواريخ أسلوبًا ابتكره الفيزيائي ريتشارد فاينمان لصياغة التكامل المساري . ويمكن صياغة مسألة APPROX-QCIRCUIT-PROB باستخدام تقنية مجموع التواريخ لإثبات أنبسؤالP⊆PSPأجهـ{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}[ 13 ]​

شجرة مجموع التواريخ

لنفترض وجود دائرة كمومية C ، تتكون من t بوابة.ز1،ز2،⋯،زم{\displaystyle g_{1},g_{2},\cdots ,g_{m}}حيث كلزج{\displaystyle g_{j}}ينشأ من مجموعة بوابات عامة ويؤثر على اثنين من الكيوبتات على الأكثر. لفهم معنى مجموع المسارات، نتصور تطور الحالة الكمومية في دائرة كمومية على شكل شجرة. الجذر هو المدخل.|0⟩⊗ن{\displaystyle |0\rangle ^{\otimes n}}وكل عقدة في الشجرة تحتوي على2ن{\displaystyle 2^{n}}الأطفال، كل منهم يمثل ولاية فيجن{\displaystyle \mathbb {C} ^{n}}الوزن على حافة الشجرة من عقدة في المستوى j الذي يمثل حالة|x⟩{\displaystyle |x\rangle }إلى عقدة فيج+1{\displaystyle j+1}المستوى -th الذي يمثل حالة|y⟩{\displaystyle |y\rangle }يكون⟨y|زج+1|x⟩{\displaystyle \langle y|g_{j+1}|x\rangle }، سعة|y⟩{\displaystyle |y\rangle }للتقديمزج+1{\displaystyle g_{j+1}}على|x⟩{\displaystyle |x\rangle }سعة الانتقال لمسار من الجذر إلى الورقة هي حاصل ضرب جميع الأوزان على الحواف على طول المسار. للحصول على احتمال أن تكون الحالة النهائية|ψ⟩{\displaystyle |\psi \rangle }نقوم بجمع سعات جميع المسارات من الجذر إلى المخرج التي تنتهي عند عقدة تمثل|ψ⟩{\displaystyle |\psi \rangle }.

بصورة أكثر رسمية، بالنسبة للدائرة الكمومية C ، فإن شجرة مجموع تاريخها هي شجرة بعمق m ، مع مستوى واحد لكل بوابة.زأنا{\displaystyle g_{i}}بالإضافة إلى الجذر، ومع عامل التفرع2ن{\displaystyle 2^{n}}.

تعريف — التاريخ هو مسار في شجرة مجموع التواريخ. سنرمز إلى التاريخ بتسلسل.(u0=|0⟩⊗ن→u1→⋯→uم-1→uم=x){\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)}بالنسبة لحالة نهائية ما x .

عرّف — دعu،v∈{0،1}ن{\displaystyle u,v\in \{0,1\}^{n}}لنفترض أن سعة الحافة(|u⟩،|v⟩){\displaystyle (|u\rangle ,|v\rangle )}في المستوى j من شجرة مجموع التواريخ beαج(u→v)=⟨v|زج|u⟩{\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle }لأي تاريخح=(u0→u1→⋯→uم-1→uم){\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})}سعة الانتقال في التاريخ هي حاصل ضربαح=α1(|0⟩⊗ن→u1)α2(u1→u2)⋯αم(uم-1→x){\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)}.

مطالبة — للتاريخ(u0→⋯→uم){\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})}. يمكن حساب سعة الانتقال للتاريخ في وقت متعدد الحدود.

دليل

كل بوابةزج{\displaystyle g_{j}}يمكن تحليلها إلىزج=أنا⊗ز~ج{\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}}بالنسبة لبعض المشغلات الوحدويةز~ج{\displaystyle {\tilde {g}}_{j}}يؤثر على كيوبتين، واللذين يمكن اعتبارهما أول كيوبتين دون فقدان للعمومية. ومن ثم،⟨v|زج|u⟩=⟨v1،v2|ز~ج|u1،u2⟩⟨v3،⋯،vن|u3،⋯،uن⟩{\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle }والتي يمكن حسابها في وقت متعدد الحدود في n . وبما أن m متعدد الحدود في n ، فإنه يمكن حساب سعة الانتقال للتاريخ في وقت متعدد الحدود.

المطالبة — السماحج|0⟩⊗ن=∑x∈{0،1}نαx|x⟩{\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle }لتكن الحالة النهائية للدائرة الكمومية. لبعضx∈{0،1}ن{\displaystyle x\in \{0,1\}^{n}}، السعةαx{\displaystyle \alpha _{x}}يمكن حسابها بواسطةαx=∑ح=(|0⟩⊗ن→u1→⋯→uت-1→|x⟩)αح{\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}}.

دليل

لديناαx=⟨x|ج|0⟩⊗ن=⟨x|زتزت-1⋯ز1|ج|0⟩⊗ن{\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}}. وتأتي النتيجة مباشرة عن طريق الإدخالأنا=∑x∈{0،1}ن|x⟩⟨x|{\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|}بينز1،ز2{\displaystyle g_{1},g_{2}}، وز2،ز3{\displaystyle g_{2},g_{3}}وهكذا، ثم يتم توسيع المعادلة. عندئذٍ يتوافق كل حد معαح{\displaystyle \alpha _{h}}، أينح=(|0⟩⊗ن→u1→⋯→uت-1→|x⟩){\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}

مطالبة -APPROX-QCIRCUIT-PROB∈PSPأجهـ{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}}

لاحظ في خوارزمية الجمع على السجلات حساب بعض السعةαx{\displaystyle \alpha _{x}}يتم تخزين سجل تاريخي واحد فقط في أي مرحلة من مراحل الحساب. ولذلك، تستخدم خوارزمية الجمع على السجلات التاريخيةيا(نم){\displaystyle O(nm)}مساحة للحسابαx{\displaystyle \alpha _{x}}لأي قيمة لـ x بمايا(نم){\displaystyle O(nm)}هناك حاجة إلى وحدات بت لتخزين السجلات بالإضافة إلى بعض متغيرات مساحة العمل.

لذلك، في فضاء كثير الحدود، يمكننا حساب∑x|αx|2{\displaystyle \sum _{x}|\alpha _{x}|^{2}}على جميع قيم x مع اعتبار الكيوبت الأول هو1 ، وهو احتمال أن يتم قياس الكيوبت الأول ليكون 1 بنهاية الدائرة.

لاحظ أنه بالمقارنة مع المحاكاة المقدمة لإثبات أنبسؤالP⊆هـXP{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}خوارزميتنا هنا تستهلك مساحة أقل بكثير، لكنها تستغرق وقتًا أطول بكثير. في الواقع، إنها تستغرقيا(م⋅2من){\displaystyle O(m\cdot 2^{mn})}حان وقت حساب سعة واحدة!

BQP و PP

يمكن استخدام حجة مماثلة تعتمد على مجموع السجلات التاريخية لإثبات ذلك.بسؤالP⊆PP{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}[ 14 ]​

P و BQP

نحن نعلمP⊆بسؤالP{\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}}، حيث يمكن محاكاة كل دائرة كلاسيكية بواسطة دائرة كمومية. [ 15 ]

يُفترض أن BQP يحل مسائل صعبة خارج نطاق P، وتحديدًا مسائل في NP. هذا الادعاء غير مؤكد لأننا لا نعلم ما إذا كانت P=NP، وبالتالي لا نعلم ما إذا كانت هذه المسائل تنتمي فعلاً إلى P. فيما يلي بعض الأدلة على هذا الافتراض:

انظر أيضاً

مراجع

  1. 1 2 3 مايكل نيلسن وإسحاق تشوانغ (2000). الحوسبة الكمومية والمعلومات الكمومية . كامبريدج: مطبعة جامعة كامبريدج. ISBN 0-521-63503-9.
  2. 1 2 3 4 بيرنشتاين، إيثان؛ وزيراني ، أوميش (أكتوبر 1997). “نظرية التعقيد الكمي”. مجلة SIAM للحوسبة . 26 (5): 1411- 1473. CiteSeerX 10.1.1.655.1186 . دوى : 10.1137/S0097539796300921 . 
  3. ↑ باراك، سانجيف أرورا، بواز (2009). التعقيد الحسابي: منهج حديث / سانجيف أرورا وبواز باراك . كامبريدج. ص 122. تم الاطلاع عليه بتاريخ 24 يوليو 2018 . {{cite book}}: صيانة CS1: موقع الناشر مفقود ( رابط ) صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  4. ↑ فورتناو، لانس؛ روجرز، جون (1999). "قيود التعقيد على الحوسبة الكمومية" (ملف PDF) . مجلة علوم أنظمة الحاسوب . 59 (2): 240-252 . arXiv : cs/9811023 . doi : 10.1006/jcss.1999.1651 . ISSN 0022-0000 . S2CID 42516312. مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.  
  5. ^ إل أدلمان، جيه ديماريه، وم.-د. هوانغ. الحوسبة الكمومية. سيام جي كومبيوتر، 26(5):1524-1540، 1997.
  6. ^ جورج، مايكل جودرباور، ستيفان. "إي سي سي سي - TR18-107" . eccc.weizmann.ac.il . تم الاسترجاع 2018-08-03 .{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  7. 1 2 آرونسون، سكوت (2010). "BQP والتسلسل الهرمي متعدد الحدود" (ملف PDF) . وقائع مؤتمر ACM STOC 2010. مؤرشف ( ملف PDF) من الأصل بتاريخ 2022-10-09.
  8. ↑ آرونسون، سكوت (2005). "الحوسبة الكمومية، والاختيار اللاحق، والوقت متعدد الحدود الاحتمالي". وقائع الجمعية الملكية أ . 461 (2063): 3473-3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . النسخة الأولية متاحة على الرابط التالي:
  9. ↑ آرونسون، سكوت (11 يناير 2004). "درس التعقيد لهذا الأسبوع: PP" . مدونة التعقيد الحسابي . تم الاطلاع عليه بتاريخ 2 مايو 2008 .
  10. ↑ جانزينغ، دومينيك؛ ووجان، باول (30 مارس 2007). "مسألة مصفوفة بسيطة من نوع PromiseBQP-complete" (ملف PDF) . نظرية الحوسبة . 3 (4): 61-79 . doi : 10.4086/toc.2007.v003a004 . تاريخ الاسترجاع : 18 أبريل 2024 .
  11. ↑ مايكل أ. نيلسن؛ إسحاق ل. تشوانغ (9 ديسمبر 2010). "4.4 القياس". الحوسبة الكمومية والمعلومات الكمومية: الطبعة العاشرة . مطبعة جامعة كامبريدج. ص 186. ISBN  978-1-139-49548-6.
  12. ↑ أوديل أ. كروس (5 نوفمبر 2012). "5.2.2 القياس المؤجل". مواضيع في الحوسبة الكمومية . أوديل أ. كروس. ص 348. ISBN  978-1-4800-2749-7.
  13. ↑ إي. بيرنشتاين ويو. فازيراني. نظرية التعقيد الكمي، مجلة SIAM للحوسبة، 26(5):1411-1473، 1997.
  14. ↑ L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Computing 26:1524-1540, 1997.
  15. ↑ نيلسن، مايكل أ.؛ تشوانغ، إسحاق ل. (2000)، الحوسبة الكمومية والمعلومات الكمومية، كامبريدج: مطبعة جامعة كامبريدج، ISBN 0-521-63235-8، MR 1796805.
  16. 1 2 arXiv:quant-ph/9508027v2 خوارزميات زمنية متعددة الحدود لتحليل الأعداد إلى عواملها الأولية واللوغاريتمات المنفصلة على حاسوب كمومي ، بيتر دبليو. شور
  • رابط Complexity Zoo إلى BQP مؤرشف بتاريخ 3 يونيو 2013 على موقع Wayback Machine