PostBQP

لنفترض أن n يمثل حجم المدخلات، وB = B ( n ) يمثل العدد الإجمالي للكيوبتات في الدائرة (المدخلات، والكيوبتات المساعدة، والمخرجات، وكيوبتات ما بعد الاختيار)، و G = G ( n ) يمثل العدد الإجمالي للبوابات. مثّل البوابة رقم i بمصفوفة الانتقال A _ⁱ (مصفوفة حقيقية وحدوية).${\displaystyle 2^{B}\times 2^{B}}$المصفوفة) ولتكن الحالة الابتدائية${\displaystyle |x\rangle }$(مُضاف إليها أصفار). ثم${\displaystyle \Psi =A^{G}A^{G-1}\dotsb A^{2}A^{1}|x\rangle }$عرّف S1 ₍ أو S0 ) على أنها مجموعة حالات الأساس المقابلة لـ P = 1، Q = 1 (أو P = 1، Q = 0 ) _، وعرّف الاحتمالات .

${\displaystyle \pi _{1}:={\text{Pr}}[P=1,Q=1]=\sum _{\omega \in S_{1}}\Psi _{\omega }^{2}}$

${\displaystyle \pi _{0}:={\text{Pr}}[P=1,Q=0]=\sum _{\omega \in S_{0}}\Psi _{\omega }^{2}.}$

تعريف ⁠${\displaystyle {\mathsf {PostBQP}}}$يضمن أن إما${\displaystyle \pi _{1}\geq 2\pi _{0}}$أو${\displaystyle \pi _{0}\geq 2\pi _{1}}$بحسب ما إذا كان x موجودًا في L أم لا.

خاصتنا​${\displaystyle {\mathsf {PP}}}$ستقوم الآلة بالمقارنة${\displaystyle \pi _{1}}$و${\displaystyle \pi _{0}}$وللقيام بذلك، نقوم بتوسيع تعريف ضرب المصفوفات:

${\displaystyle \Psi _{\omega }=\sum _{\alpha _{1},\ldots ,\alpha _{G}}A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$

حيث يتم حساب المجموع على جميع قوائم متجهات الأساس G${\displaystyle \alpha _{i}}$. الآن${\displaystyle \pi _{1}}$و${\displaystyle \pi _{0}}$يمكن التعبير عنها كمجموع حاصل ضرب هذه الحدود. وبشكل بديهي، نريد تصميم آلة يكون احتمال قبولها شيئًا مثل${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})}$، منذ ذلك الحين${\displaystyle x\in L}$وهذا يعني أن احتمال القبول هو${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})>{\tfrac {1}{2}}}$، بينما${\displaystyle x\not \in L}$وهذا يعني أن احتمال القبول هو${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})<{\tfrac {1}{2}}}$.

نقدم الآن التنفيذ المفصل لـ${\displaystyle {\mathsf {PP}}}$آلة .لنرمز إلى المتتالية بـ α${\displaystyle \{\alpha _{i}\}_{i=1}^{G}}$وحدد رموز الاختصار

${\displaystyle \Pi (A,\omega ,\alpha ,x):=A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$،

ثم

${\displaystyle \pi _{1}-\pi _{0}=\sum _{\omega \in S_{1}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)-\sum _{\omega \in S_{0}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x).}$

نحن نحدد ⁠${\displaystyle {\mathsf {PP}}}$آلة إلى

• اختر حالة أساسية ω بشكل عشوائي منتظم
• لو${\displaystyle \omega \not \in S_{0}\cup S_{1}}$ثم توقف واقبل باحتمالية 1/2، وارفض باحتمالية 1/2
• اختر سلسلتين${\displaystyle \alpha ,\alpha '}$من حالات الأساس G بشكل عشوائي منتظم
• حساب${\displaystyle X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)}$(وهو كسر ذو مقام${\displaystyle 2^{2f(n)G(n)}}$بحيث${\displaystyle -1\leq X\leq 1}$)
• لو${\displaystyle \omega \in S_{1}}$ثم اقبل باحتمالية${\displaystyle {\tfrac {1+X}{2}}}$ورفض باحتمالية${\displaystyle {\tfrac {1-X}{2}}}$(والذي يستغرق على الأكثر ⁠${\displaystyle 2f(n)G(n)+1}$( رمي العملة المعدنية)
• وإلا (ثم${\displaystyle \omega \in S_{0}}$) قبول باحتمالية${\displaystyle {\tfrac {1-X}{2}}}$ورفض باحتمالية${\displaystyle {\tfrac {1+X}{2}}}$(والذي يستغرق مرة أخرى على الأكثر ⁠${\displaystyle 2f(n)G(n)+1}$( رمي العملة المعدنية)

ومن ثم، يصبح من السهل حساب احتمال قبول هذه الآلة ${\displaystyle {\frac {1}{2}}+{\frac {\pi _{1}-\pi _{0}}{2^{1+B(n)+2B(n)G(n)}}},}$ هذا هو ⁠${\displaystyle {\mathsf {PP}}}$آلة للغة L ، حسب الحاجة.

خوارزمية آرونسون لحل هذه المشكلة هي كما يلي. ولتبسيط الأمر، سنكتب جميع الحالات الكمومية على أنها غير مُعَيَّرة. أولًا، نقوم بتحضير الحالة${\displaystyle |x\rangle \otimes \sum _{r\in \{0,1\}^{T}}|r\rangle |f(x,r)\rangle }$ثانيًا، نُطبّق بوابات هادامارد على السجل الثاني (كل من الكيوبتات T الأولى )، ونقيس السجل الثاني، ثم نُجري عملية اختيار لاحقة للتأكد من كونه سلسلة أصفار بالكامل. من السهل التحقق من أن هذا يُبقي السجل الأخير (الكيوبت الأخير) في الحالة المتبقية.

${\displaystyle |\psi \rangle$ :=(2^{T}-s)|0\rangle +s|1\rangle .}

حيث يرمز H إلى بوابة هادامارد، نقوم بحساب الحالة

${\displaystyle H|\psi \rangle =(2^{T}|0\rangle +(2^{T}-2s)|1\rangle )/{\sqrt {2}}}$.

أين${\displaystyle \alpha ,\beta }$هي أعداد حقيقية موجبة سيتم اختيارها لاحقًا${\displaystyle \alpha ^{2}+\beta ^{2}=1}$، نقوم بحساب الحالة${\displaystyle \alpha |0\rangle |\psi \rangle +\beta |1\rangle |H\psi \rangle }$ثم قياس الكيوبت الثاني، مع اختيار لاحق بناءً على قيمته التي تساوي 1، مما يترك الكيوبت الأول في حالة متبقية تعتمد على${\displaystyle \beta /\alpha }$والتي نرمز إليها

${\displaystyle |\phi _{\beta /\alpha }\rangle$ :=\alpha s|0\rangle +{\frac {\beta }{\sqrt {2}}}(2^{T}-2s)|1\rangle } .

بتصور الحالات الممكنة للكيوبت على شكل دائرة، نرى أنه إذا${\displaystyle s>2^{T-1}}$(أي إذا${\displaystyle x\in L}$) ثم${\displaystyle \phi _{\beta /\alpha }}$يقع في الربع المفتوح${\displaystyle Q_{acc}:=(-|1\rangle ,|0\rangle )}$بينما إذا${\displaystyle s<2^{T-1}}$(أي إذا${\displaystyle x\not \in L}$) ثم${\displaystyle \phi _{\beta /\alpha }}$يقع في الربع المفتوح${\displaystyle Q_{rej}:=(|0\rangle ,|1\rangle )}$في الواقع، لأي قيمة ثابتة لـ x (وقيمتها المقابلة s )، عندما نغير النسبة${\displaystyle \beta /\alpha }$في${\displaystyle (0,\infty )}$لاحظ أن صورة${\displaystyle |\phi _{\beta /\alpha }\rangle }$وهو الربع المفتوح المقابل تمامًا. وفي بقية البرهان، نوضح فكرة أنه يمكننا التمييز بين هذين الربعين.

يترك${\displaystyle |+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}}$، وهو مركز${\displaystyle Q_{rej}}$ودع${\displaystyle |-\rangle }$يكون متعامدًا مع${\displaystyle |+\rangle }$أي كيوبت في${\displaystyle Q_{acc}}$، عند قياسها على أساس${\displaystyle \{|+\rangle ,|-\rangle \}}$، يعطي القيمة${\displaystyle |+\rangle }$أقل من نصف الوقت. من ناحية أخرى، إذا${\displaystyle x\not \in L}$وقد اخترنا${\displaystyle \beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)}$ثم القياس${\displaystyle |\phi _{\beta /\alpha }\rangle }$في الأساس${\displaystyle \{|+\rangle ,|-\rangle \}}$سيعطي القيمة${\displaystyle |+\rangle }$طوال الوقت. بما أننا لا نعرف قيمة s، فإننا لا نعرف أيضًا القيمة الدقيقة لـ r* ، ولكن يمكننا تجربة عدة قيم مختلفة (عددها كثير الحدود) لـ${\displaystyle \beta /\alpha }$على أمل الحصول على واحدة "قريبة" من r* .

على وجه التحديد، لاحظ${\displaystyle 2^{-T}<r*<2^{T}}$ولنقم تباعاً${\displaystyle \beta /\alpha }$لكل قيمة من الشكل${\displaystyle 2^{i}}$ل${\displaystyle -T\leq i\leq T}$ثم تُظهر الحسابات الأولية أنه بالنسبة لإحدى هذه القيم لـ i ، فإن احتمال أن يكون قياس${\displaystyle |\phi _{2^{i}}\rangle }$في الأساس${\displaystyle \{|+\rangle ,|-\rangle \}}$العائد${\displaystyle |+\rangle }$هو على الأقل${\displaystyle (3+2{\sqrt {2}})/6\approx 0.971.}$

بشكل عام ،${\displaystyle {\mathsf {PostBQP}}}$الخوارزمية كالتالي. ليكن k أي ثابت يقع تمامًا بين 1/2 و${\displaystyle (3+2{\sqrt {2}})/6}$نقوم بالتجربة التالية لكل${\displaystyle -T\leq i\leq T}$: بناء وقياس${\displaystyle |\phi _{2^{i}}\rangle }$في الأساس${\displaystyle \{|+\rangle ,|-\rangle \}}$إجمالي${\displaystyle C\log T}$مرات حيث C ثابت. إذا كانت نسبة${\displaystyle |+\rangle }$إذا كانت القياسات أكبر من k ، نرفض الاحتمال. أما إذا لم نرفضه لأي قيمة لـ i ، نقبله. تُظهر حدود تشيرنوف أنه بالنسبة لثابت عالمي كبير بما فيه الكفاية C ، فإننا نصنف x بشكل صحيح باحتمالية لا تقل عن 2/3.

لاحظ أن هذه الخوارزمية تفي بالافتراض التقني القائل بأن احتمالية ما بعد الاختيار الإجمالية ليست صغيرة جدًا: كل قياس فردي لـ${\displaystyle |\phi _{2^{i}}\rangle }$احتمالية ما بعد الاختيار${\displaystyle 1/2^{O(T)}}$وبالتالي فإن الاحتمالية الإجمالية هي${\displaystyle 1/2^{O(T^{2}\log T)}}$.