خوارزمية HHL

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 68 صور
الموسوعة الحرة

خوارزمية هارو -حسيديم-لويد ( HHL ) هي خوارزمية كمومية للحصول على معلومات محدودة حول حل نظام من المعادلات الخطية ، وقد قدمها آرام هارو ، وأفيناتان حسيديم، وسيث لويد . وتحديدًا، تُقدّر الخوارزمية الدوال التربيعية لمتجه الحل لنظام معين. [ 1 ]

تُعدّ هذه الخوارزمية إحدى الخوارزميات الأساسية الرئيسية التي يُتوقع أن تُحسّن سرعة الحل مقارنةً بنظيراتها التقليدية، إلى جانب خوارزمية شور للتحليل إلى عوامل وخوارزمية جروفر للبحث . وبافتراض أن النظام متفرق ، فإن [ 2 ] يتميز برقم حالة منخفض.κ{\displaystyle \kappa }وبما أن المستخدم مهتم فقط بمعلومات معينة حول متجه الحل وليس المتجه بأكمله، فإن وقت تشغيل الخوارزمية هويا(سجل⁡(شمال)κ2){\displaystyle O(\log(N)\kappa ^{2})}، أينشمال{\displaystyle N}يمثل عدد المتغيرات. وهذا يوفر تسارعًا هائلاً مقارنةً بأسرع خوارزمية كلاسيكية، والتي تعمل فييا(شمالκ){\displaystyle O(N\kappa )}(أويا(شمالκ){\displaystyle O(N{\sqrt {\kappa }})}(للمصفوفات شبه المحددة الموجبة).

تم عرض تطبيق خوارزمية HHL لأول مرة في عام 2013 من خلال ثلاثة منشورات مستقلة، تتألف من أنظمة بسيطة على أجهزة مصممة خصيصًا. [ 3 ] [ 4 ] [ 5 ] وظهر أول عرض توضيحي لنسخة عامة الأغراض من الخوارزمية في عام 2018. [ 6 ]

ملخص

بالنظر إلىشمال×شمال{\displaystyle N\times N}مصفوفة هيرميتيةأ{\displaystyle A}ومتجه الوحدةب→∈Rشمال{\displaystyle {\vec {b}}\in \mathbb {R} ^{N}}تقوم خوارزميات HHL بتحضير الحالة الكمومية|x⟩{\displaystyle |x\rangle }والتي تمثل سعاتها مدخلات الحلx→∈Rشمال{\displaystyle {\vec {x}}\in \mathbb {R} ^{N}}إلى النظام الخطيأx→=ب→{\displaystyle A{\vec {x}}={\vec {b}}}لا تستطيع الخوارزمية إخراج الحل x نفسه بكفاءة، ولكنها تسمح بتقديره بكفاءة.x→تيمx→{\displaystyle {\vec {x}}^{T}M{\vec {x}}}للمصفوفة الهرميتيةم{\displaystyle M}.

تقوم الخوارزمية أولاً بإعداد الحالة الكمومية|ب⟩{\displaystyle |b\rangle }والتي تساوي سعتها مدخلاتب→{\displaystyle {\vec {b}}}باستخدام محاكاة هاميلتونية ، المؤثر الوحدويهـأناأت{\displaystyle e^{iAt}}ينطبق على|ب⟩{\displaystyle |b\rangle }بالنسبة لتراكب أزمنة مختلفة t . ثم تستخدم الخوارزمية تقدير الطور الكمومي لتحليلها|ب⟩{\displaystyle |b\rangle }في الأساس الذاتي لـأ{\displaystyle A}ثم أوجد القيم الذاتية المناظرةλج{\displaystyle \lambda _{j}}تكون حالة النظام بعد هذه الخطوة تقريبًا

∑ج=⁡1شمالβج|uج⟩|λج⟩،{\displaystyle \sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle |\lambda _{j}\rangle ,}

أينuج{\displaystyle u_{j}}هي المتجهات الذاتية للمصفوفة A وβج{\displaystyle \beta _{j}}يمثل المعامل j للمتغير b في الأساس الذاتي للمصفوفة A.

ثم نرغب في تطبيق التحويل الخطي|λج⟩{\displaystyle |\lambda _{j}\rangle }لجλج-1|λج⟩{\displaystyle C\lambda _{j}^{-1}|\lambda _{j}\rangle }لثابت ما C. هذه الخريطة ليست وحدوية، ويجب تنفيذها باستخدام قياس كمومي باحتمالية فشل غير صفرية. بعد نجاحها، نكون قد ألغينا حساب|λج⟩{\displaystyle |\lambda _{j}\rangle }التسجيل والحصول على حالة تتناسب مع

∑أنا=⁡1شمالβأناλج-1|uج⟩=أ-1|ب⟩=|x⟩.{\displaystyle \sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle .}

بإجراء القياس الكمومي المقابل لـ M ، نحصل على تقدير لـx→تيمx→{\displaystyle {\vec {x}}^{T}M{\vec {x}}}يمكن للمرء استخدام التصوير المقطعي الكمي لاستعادة جميع مكونات x ، ولكن هذا سيتطلب تكرار الخوارزمية N مرة تقريبًا.

وصف تفصيلي

الافتراضات والتهيئة

تتطلب الخوارزمية تحقق الافتراضات التالية:

  1. تتطلب الخوارزمية أن تكون المصفوفة A هيرميتية حتى يمكن تحويلها إلى مؤثر وحدوي . إذا لم تكن A هيرميتية، فيمكن تعريف مصفوفة هيرميتية.ج=[0أأ†0]{\displaystyle \mathbf {C} ={\begin{bmatrix}0&A\\A^{\dagger }&0\end{bmatrix}}}وحلجy=[ب0]{\displaystyle Cy={\begin{bmatrix}b\\0\end{bmatrix}}}للحصول علىy=[0x]{\displaystyle y={\begin{bmatrix}0\\x\end{bmatrix}}}.
  2. تتطلب الخوارزمية إجراءً فعالاً للتحضير|ب⟩{\displaystyle |b\rangle }يُفترض أن إما|ب⟩{\displaystyle |b\rangle }تم تحضيرها بالفعل أو يوجد شيء ما B يتخذ حالة كمومية معينة|أنانأناتأناأل⟩{\displaystyle |\mathrm {initial} \rangle }ل|ب⟩{\displaystyle |b\rangle }بكفاءة. أي خطأ في إعداد|ب⟩{\displaystyle |b\rangle }يتم تجاهلها.
  3. تفترض الخوارزمية أن الحالة|ψ0⟩{\displaystyle |\psi _{0}\rangle }يمكن إعدادها بكفاءة، حيث|ψ0⟩:=2/تي∑τ=⁡0تي-1الخطيئة⁡π(τ+12تي)|τ⟩{\displaystyle |\psi _{0}\rangle :={\sqrt {2/T}}\sum _{\tau \mathop {=} 0}^{T-1}\sin \pi \left({\tfrac {\tau +{\tfrac {1}{2}}}{T}}\right)|\tau \rangle } لبعض قيم T الكبيرة . معاملات|ψ0⟩{\displaystyle |\psi _{0}\rangle }يتم اختيارها لتقليل دالة خسارة تربيعية معينة تؤدي إلى حدوث خطأ فييوأنانvهـرت{\displaystyle U_{\mathrm {invert} }}الروتين الفرعي الموصوف أدناه.
  4. تفترض الخوارزمية أن المؤثر الوحدويهـأناأت{\displaystyle e^{iAt}}يمكن تطبيق ذلك بكفاءة. وهذا ممكن باستخدام محاكاة هاميلتونية إذا كانت المصفوفة A متفرقة من الدرجة s وقابلة للحساب الصفي بكفاءة، أي أنها تحتوي على s عنصرًا غير صفري على الأكثر لكل صف، ويمكن حسابها في زمن O( s ) عند إعطاء فهرس الصف. ويمكن بعد ذلك تطبيقهـأناأت{\displaystyle e^{iAt}}في الوقت المناسبيا(سجل⁡(شمال)s2ت){\displaystyle O(\log(N)s^{2}t)}.

روتين فرعي لعكس U

الروتين الفرعي الرئيسي للخوارزمية، المشار إليه بـيوأنانvهـرت{\displaystyle U_{\mathrm {invert} }}يتم تعريفها على النحو التالي باستخدام تقدير الطور :

  1. يحضر|ψ0⟩ج{\displaystyle |\psi _{0}\rangle ^{C}}في السجل ج
  2. تطبيق تطور الهاميلتوني الشرطي (المجموع)
  3. قم بتطبيق تحويل فورييه على المسجل C. وارمز إلى حالات الأساس الناتجة بـ |ك⟩{\displaystyle |k\rangle }لـ k  =  0،  ...، T − 1. عرّف   λك:=2πك/ت0{\displaystyle \lambda _{k}:=2\pi k/t_{0}}.
  4. قم بإلحاق سجل ثلاثي الأبعاد S في الحالة
|ح(λك)⟩S:=1-و(λك)2-ز(λك)2|نoتحأنانز⟩S+و(λك)|wهـلل⟩S+ز(λك)|أنالل⟩S،{\displaystyle |h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|\mathrm {nothing} \rangle ^{S}+f(\lambda _{k})|\mathrm {well} \rangle ^{S}+g(\lambda _{k})|\mathrm {ill} \rangle ^{S},}
  1. اعكس الخطوات من 1 إلى 3، مع إلغاء حساب أي بيانات غير ضرورية تم إنتاجها على طول الطريق.

تقوم عملية تقدير الطور في الخطوات من 1 إلى 3 بتقدير القيم الذاتية للمصفوفة A بدقة تصل إلى حد الخطأϵ{\displaystyle \epsilon }.

يُستخدم سجل المساعدة في الخطوة 4 لإنشاء حالة ذات قيم ذاتية معكوسة تُطابق المعكوس القطري للمصفوفة A. تُستخدم الحالات "لا شيء" و"جيد" و"سيئ" لتوجيه جسم الحلقة؛ تشير "لا شيء" إلى أن عملية عكس المصفوفة لم تتم بعد، وتشير "جيد" إلى أنها قد تمت ويجب إيقاف الحلقة، وتشير "سيئ" إلى أن جزءًا من|ب⟩{\displaystyle |b\rangle }تقع هذه الحالة في الفضاء الفرعي سيئ التكييف للمصفوفة A ، ولا تستطيع الخوارزمية إنتاج الانعكاس المطلوب. يتطلب إنتاج حالة تتناسب مع معكوس A قياس "جيد"، وبعد ذلك تنهار الحالة الكلية إلى الناتج المطلوب.

الحلقة الرئيسية

تتبع الحلقة الرئيسية تضخيم السعة : بدءًا منيوأنانvهـرتب|أنانأناتأناأل⟩{\displaystyle U_{\mathrm {invert} }B|\mathrm {initial} \rangle }، تطبيق متكرر

يوأنانvهـرتب(أنا-2|أنانأناتأناأل⟩⟨أنانأناتأناأل|)ب†يوأنانvهـرت†(أنا-2|wهـلل⟩⟨wهـلل|).{\displaystyle U_{\mathrm {invert} }B(I-2|\mathrm {initial} \rangle \langle \mathrm {initial} |)B^{\dagger }U_{\mathrm {invert} }^{\dagger }(I-2|\mathrm {well} \rangle \langle \mathrm {well} |).}

بعد كل تكرار،S{\displaystyle S}يتم قياسها وستُنتج قيمة "لا شيء" أو "جيد" أو "مريض". تُكرر الحلقة حتى يتم قياس "جيد"، وهو ما يحدث باحتمالية معينة.ص{\displaystyle p}باستخدام تضخيم السعة، يتم تحقيق خطأ معين باستخداميا(1/ص){\displaystyle O(1/{\sqrt {p}})}الاستفسارات، على عكس1/ص{\displaystyle 1/p}باستخدام التكرار البسيط.

بعد نجاح القياس "جيدًا" علىS{\displaystyle S}سيكون النظام في حالة تتناسب مع

∑أنا=⁡1شمالβأناλج-1|uج⟩=أ-1|ب⟩=|x⟩.{\displaystyle \sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle .}

ثم يعطي القياس الكمي المقابل لـ M تقديرًا لـx→تيمx→{\displaystyle {\vec {x}}^{T}M{\vec {x}}}.

تحليل

الكفاءة الكلاسيكية

أفضل خوارزمية كلاسيكية تنتج متجه الحل الفعليx→{\displaystyle {\vec {x}}}هي عملية الحذف الغاوسي ، والتي تعمل فييا(شمال3){\displaystyle O(N^{3})}وقت.

إذا كانت المصفوفة A متفرقة من الدرجة s وشبه موجبة، فيمكن استخدام طريقة التدرج المترافق لإيجاد متجه الحل.x→{\displaystyle {\vec {x}}}والتي يمكن العثور عليها فييا(شمالsκ){\displaystyle O(Ns\kappa )}الوقت عن طريق تقليل الدالة التربيعية‖أx→-ب→‖2{\displaystyle \lVert A{\vec {x}}-{\vec {b}}\rVert ^{2}}.

عندما تكون مجرد إحصائية موجزة لمتجه الحلx→{\displaystyle {\vec {x}}}إذا لزم الأمر، كما هو الحال بالنسبة لخوارزمية HHL، يمكن للحاسوب التقليدي إيجاد تقدير لـx→†مx→{\displaystyle {\vec {x}}^{\dagger }M{\vec {x}}}فييا(شمالκ){\displaystyle O(N{\sqrt {\kappa }})}.

الكفاءة الكمية

تبين أن وقت تشغيل الخوارزمية التي اقترحها هارو وآخرون في الأصل هويا(κ2سجل⁡شمال/ε){\displaystyle O(\kappa ^{2}\log N/\varepsilon )}، أينε>0{\displaystyle \varepsilon >0}هو معامل الخطأ وκ{\displaystyle \kappa }هو رقم الحالة لـأ{\displaystyle A}ثم جرى تحسين ذلك إلىيا(κسجل3⁡κسجل⁡شمال/ε3){\displaystyle O(\kappa \log ^{3}\kappa \log N/\varepsilon ^{3})}بقلم أندريس أمباينيس [ 7 ] و إلىيا(κسجل⁡شمال/ε){\displaystyle O(\kappa \log N/\varepsilon )}بالنسبة لحالات أرقام الحالة الكبيرة، قام بينيل تسيمو وآخرون [ 8 ] بدراسة خوارزمية كمومية ذات وقت تشغيل متعدد الحدود فيسجل⁡(1/ε){\displaystyle \log(1/\varepsilon )}طُوِّرَت هذه الخوارزمية بواسطة تشايلدز وآخرون [ 9 ] . ونظرًا لأن خوارزمية HHL تحافظ على مقياسها اللوغاريتمي فيشمال{\displaystyle N}بالنسبة للمصفوفات المتفرقة أو منخفضة الرتبة فقط، قام ووسنيج وآخرون [ 10 ] بتوسيع خوارزمية HHL بناءً على تقنية تقدير القيم المفردة الكمومية، وقدموا خوارزمية نظام خطي للمصفوفات الكثيفة التي تعمل فييا(شمالسجل⁡شمالκ2){\displaystyle O({\sqrt {N}}\log N\kappa ^{2})}الوقت مقارنة بـيا(شمالسجل⁡شمالκ2){\displaystyle O(N\log N\kappa ^{2})}من خوارزمية HHL القياسية.

الأمثلية

يعتمد أداء خوارزمية عكس المصفوفة على رقم الحالةκ{\displaystyle \kappa }من A ، وهي نسبة أكبر وأصغر القيم الذاتية.κ{\displaystyle \kappa }كلما زادت قيمة A، اقتربت من كونها غير قابلة للعكس، وبالتالي أصبح متجه الحل أقل استقرارًا، وانخفض أداء طرق التدرج الهبوطي. تفترض خوارزمية HHL أن جميع القيم المفردة لـأ{\displaystyle A}استلقِ في[1/κ،1]{\displaystyle [1/\kappa ,1]}وفي هذه الحالة، يكون وقت التشغيل متناسبًا معκ2{\displaystyle \kappa ^{2}}مما يحسن السرعة بشكل أكبر عندماκ{\displaystyle \kappa }يكونصoلy(سجل⁡(شمال)){\displaystyle \mathrm {poly} (\log(N))}[ 1 ]​

خوارزمية كمومية للأنظمة الخطية ذات زمن تشغيل متعدد اللوغاريتمات فيκ{\displaystyle \kappa }سيؤدي ذلك إلى افتراض أن BQP يساوي PSPACE ، وهو ما يُعتقد أنه غير صحيح. [ 1 ]

تحليل الأخطاء

المصدر الرئيسي للخطأ هو تطبيقهـأناأت{\displaystyle e^{iAt}}باستخدام محاكاة هاميلتوني. إذاأ{\displaystyle A}إذا كانت البيانات من النوع s-sparse، فيمكن القيام بذلك مع خطأ محدود بقيمة ثابتة معينة.ε{\displaystyle \varepsilon }مما سيؤدي إلى خطأ تراكمي في حالة الإخراج|x⟩{\displaystyle |x\rangle }.

خطأ في خطوة تقدير الطور بمقداريا(1/ت0){\displaystyle O(1/t_{0})}في التقديرλ{\displaystyle \lambda }مما ينتج عنه خطأ نسبي قدرهيا((λت0)-1){\displaystyle O((\lambda t_{0})^{-1})}في1/λ{\displaystyle 1/\lambda }. لوλ≥1/κ{\displaystyle \lambda \geq 1/\kappa }، يأخذت0=يا(κε){\displaystyle t_{0}=O(\kappa \varepsilon )}يؤدي إلى خطأ نهائي قدرهε{\displaystyle \varepsilon }يتطلب ذلك زيادة وقت التشغيل الإجمالي بما يتناسب معيا(1/ε){\displaystyle O(1/\varepsilon )}وذلك لتقليل الخطأ إلى أدنى حد.

التنفيذ التجريبي

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

في الخامس من فبراير/شباط 2013، أعلن فريق بقيادة ستيفاني بارز عن تطبيق خوارزمية HHL على حاسوب كمومي ضوئي. استخدم التطبيق بوابتي تشابك متتاليتين على نفس زوج الكيوبتات المشفرة بالاستقطاب. تم تحقيق بوابتي NOT يتم التحكم بهما بشكل منفصل، حيث تم التنبؤ بنجاح عمل الأولى بقياس فوتونين مساعدين. تراوحت القياسات التجريبية لدقة حالة الخرج المُحَصَّلة بين 64.7% و98.1% نتيجة لتأثير الانبعاثات ذات الرتبة الأعلى الناتجة عن التحويل البارامتري التلقائي للترددات المنخفضة. [ 4 ]

في 8 فبراير 2013، نشر بان وزملاؤه تقريرًا تجريبيًا لإثبات صحة مفهوم الخوارزمية الكمومية باستخدام حاسوب كمومي يعمل بتقنية الرنين المغناطيسي النووي (NMR) رباعي الكيوبتات. تم اختبار التطبيق باستخدام أنظمة خطية ذات متغيرين. ومن خلال ثلاث تجارب، تم الحصول على متجه الحل بدقة تزيد عن 96%. [ 5 ]

في 18 فبراير 2013، نشر كاي وزملاؤه عرضًا تجريبيًا لحل أنظمة المعادلات الخطية ثنائية الأبعاد. تم تحسين الدائرة الكمومية وتجميعها في شبكة بصرية خطية تضم أربعة كيوبتات ضوئية وأربع بوابات منطقية متحكم بها، والتي استُخدمت لتنفيذ إجراءات خوارزمية HHL بشكل متماسك. بالنسبة لمتجهات إدخال متنوعة، أعطى التطبيق حلولًا بدقة تتراوح بين 0.825 و0.993. [ 11 ]

تم الإبلاغ عن عرض تجريبي آخر باستخدام الرنين المغناطيسي النووي لحل نظام 8*8 بواسطة وين وآخرون [ 12 ] في عام 2018 باستخدام الخوارزمية التي طورها سوباشي وآخرون [ 13 ].

الطلبات المقترحة

تم اقتراح العديد من التطبيقات الملموسة لخوارزمية HHL، والتي تحلل افتراضات الإدخال للخوارزمية وضمانات الإخراج لمشاكل معينة.

التشتت الكهرومغناطيسي
قدّم كلادر وآخرون نسخةً من خوارزمية HHL تسمح بتضمين مُهيئ مسبق ، يُمكن استخدامه لتحسين الاعتماد على رقم الحالة . طُبّقت الخوارزمية لحساب المقطع العرضي الراداري لشكل مُعقّد، وكان ذلك من أوائل الأمثلة على تطبيق خوارزمية HHL على مشكلة مُحدّدة. [ 14 ]
حل المعادلات التفاضلية الخطية
اقترح بيري خوارزمية لحل مسائل القيمة الأولية الخطية المعتمدة على الزمن باستخدام خوارزمية HHL. [ 15 ]
حل المعادلات التفاضلية غير الخطية
اقترحت مجموعتان [ 16 ] خوارزميات فعّالة للتكامل العددي للمعادلات التفاضلية العادية غير الخطية المبددة للطاقة. استخدم ليو وآخرون [ 17 ] طريقة كارلمان الخطية للمعادلات من الرتبة الثانية، بينما استخدم لويد وآخرون [ 18 ] طريقة خطية للمجال المتوسط ​​مستوحاة من معادلة شرودنغر غير الخطية للمعادلات غير الخطية من الرتبة العامة. تُحل المعادلات الخطية الناتجة باستخدام خوارزميات الكم للمعادلات التفاضلية الخطية.
طريقة العناصر المحدودة
تُقارب طريقة العناصر المحدودة المعادلات التفاضلية الجزئية الخطية باستخدام أنظمة كبيرة من المعادلات الخطية. وقد أثبت مونتانارو وباليستر أن خوارزمية HHL قادرة على تحقيق تسريع كمي متعدد الحدود للأنظمة الخطية الناتجة. ولا يُتوقع تحقيق تسريع أُسّي للمسائل ذات البُعد الثابت أو التي يستوفي حلها شروطًا معينة للسلاسة، مثل بعض المسائل ذات الرتبة العالية في ديناميكيات الأجسام المتعددة، أو بعض المسائل في التمويل الحسابي . [ 19 ]
طريقة المربعات الصغرى
قدّم ويبي وآخرون خوارزمية كمومية لتحديد جودة مطابقة المربعات الصغرى . لا يمكن حساب المعاملات المثلى مباشرةً من مخرجات الخوارزمية الكمومية، ولكن الخوارزمية لا تزال تُخرج خطأ المربعات الصغرى الأمثل. [ 20 ]
التعلم الآلي
طُوِّرت العديد من خوارزميات التعلّم الآلي الكمومي ، ويستخدم عدد كبير منها خوارزمية HHL كإجراء فرعي. غالبًا ما يكون زمن تشغيل بعض الخوارزميات الكلاسيكية متعدد الحدود بالنسبة لحجم وأبعاد مجموعة البيانات، بينما يمكن لخوارزمية HHL أن تُحقق تسارعًا أُسّيًا في بعض الحالات. مع ذلك، كشف بحثٌ أجراه إيوين تانغ أن هناك خوارزميات كلاسيكية تُحقق نفس التسارع الأُسّي مع افتراضات إدخال مماثلة، وذلك بالنسبة لمعظم خوارزميات التعلّم الآلي الكمومي.
تمويل
تشمل المقترحات لاستخدام HHL في التمويل حل المعادلات التفاضلية الجزئية لمعادلة بلاك-شولز وتحديد تحسين المحفظة الاستثمارية من خلال حل ماركويتز . [ 21 ]
الكيمياء الكمية
يمكن إعادة صياغة طريقة التجميع المقترن الخطية في الكيمياء الكمومية كنظام من المعادلات الخطية. في عام 2023، اقترح باسكران وآخرون استخدام خوارزمية HHL لحل الأنظمة الخطية الناتجة. [ 22 ] عدد الكيوبتات في سجل الحالة في الخوارزمية الكمومية هو لوغاريتم عدد الإثارات، مما يوفر انخفاضًا أُسّيًا في عدد الكيوبتات المطلوبة مقارنةً باستخدام محلل القيم الذاتية الكمومي التبايني أو تقدير الطور الكمومي .

صعوبات التنفيذ

إدراكًا لأهمية خوارزمية HHL في مجال التعلم الآلي الكمي ، قام سكوت آرونسون [ 23 ] بتحليل المحاذير والعوامل التي يمكن أن تحد من الميزة الكمية الفعلية للخوارزمية.

  1. متجه الحل،|ب⟩{\displaystyle |b\rangle }يجب تحضيرها بكفاءة في الحالة الكمومية. إذا لم يكن المتجه قريبًا من الانتظام، فمن المرجح أن يكون تحضير الحالة مكلفًا، وإذا استغرق الأمريا(نج){\displaystyle O(n^{c})}ستختفي الميزة الأسية لـ HHL عند هذه الخطوات.
  2. تتطلب مراحل QPE توليد الوحدةهـأناأت{\displaystyle e^{iAt}}وتطبيقه المتحكم فيه. وتعتمد كفاءة هذه الخطوة علىأ{\displaystyle A}المصفوفة متفرقة و"جيدة التكييف" (منخفضة)κ{\displaystyle \kappa }وإلا، فإن تطبيقهـأناأت{\displaystyle e^{iAt}}سينمو معيا(نج){\displaystyle O(n^{c})}ومرة أخرى، ستختفي الميزة الكمومية للخوارزمية.
  3. وأخيرًا، المتجه،|x⟩{\displaystyle |x\rangle }لا يمكن الوصول إليها بسهولة. تُمكّن خوارزمية HHL من تعلم "ملخص" للمتجه، أي نتيجة قياس القيمة المتوقعة للمؤثر.⟨x|م|x⟩{\displaystyle \langle x|M|x\rangle }إذا كانت القيم الفعلية لـx→{\displaystyle {\vec {x}}}إذا كانت هناك حاجة لذلك، فسيتعين تكرار HHLيا(ن){\displaystyle O(n)}مرات، مما يُعيق التسارع الأسي. مع ذلك، اقتُرحت ثلاث طرق لتجنب الحصول على القيم الفعلية: أولًا، إذا كانت هناك حاجة إلى بعض خصائص الحل فقط؛ [ 24 ] ثانيًا، إذا كانت النتائج مطلوبة فقط لتغذية عمليات المصفوفات اللاحقة؛ ثالثًا، إذا كانت هناك حاجة إلى عينة من الحل فقط. [ 25 ]

انظر أيضاً

مراجع

  1. هارو ، آرام دبليو ؛ حسيديم، أفيناتان؛ لويد، سيث (2008). "خوارزمية كمومية لأنظمة المعادلات الخطية". رسائل المراجعة الفيزيائية . 103 (15) 150502. arXiv : 0811.3171 . Bibcode : 2009PhRvL.103o0502H . doi : 10.1103/PhysRevLett.103.150502 . PMID 19905613. S2CID 5187993 .  
  2. ↑ جونستون، إريك (2019-07-03). برمجة الحواسيب الكمومية: خوارزميات أساسية ونماذج برمجية . دار نشر أورايلي ميديا . ص 267. ISBN  978-1-4920-3965-5.
  3. ↑ كاي، إكس.-دي؛ ويدبروك، سي؛ سو، زد.-إي؛ تشين، إم.-سي؛ غو، مايل؛ تشو، إم.-جيه؛ لي، لي؛ ليو، ناي-لي؛ لو، تشاو-يانغ؛ بان، جيان-وي (2013). "الحوسبة الكمومية التجريبية لحل أنظمة المعادلات الخطية". رسائل المراجعة الفيزيائية . 110 (23) 230501. arXiv : 1302.4310 . Bibcode : 2013PhRvL.110w0501C . doi : 10.1103/PhysRevLett.110.230501 . PMID 25167475. S2CID 20427454 .  
  4. 1 2 بارز، ستيفاني؛ كاسال، إيفان؛ رينغباور، مارتن؛ ليب، يانيك أولي؛ داكيتش، بوريفوي؛ أسبورو-غوزيك، آلان؛ والثر، فيليب (2014). "معالج كمومي ضوئي ثنائي الكيوبت وتطبيقه في حل أنظمة المعادلات الخطية" . التقارير العلمية . 4 6115. arXiv : 1302.1210 . Bibcode : 2014NatSR...4.6115B . doi : 10.1038/srep06115 . ISSN 2045-2322 . PMC 4137340. PMID 25135432 .   
  5. 1 2 بان، جيان؛ كاو، يودونغ؛ ياو، شيوي؛ لي، تشاوكاي؛ جو، تشين يونغ؛ بنغ، شينخوا؛ كايس، سابر؛ دو، جيانغ فنغ؛ دو، جيانغ فنغ (2014). "التطبيق العملي للخوارزمية الكمومية لحل أنظمة المعادلات الخطية". مجلة Physical Review A. 89 ( 2) 022313. arXiv : 1302.1946 . Bibcode : 2014PhRvA..89b2313P . doi : 10.1103/PhysRevA.89.022313 . S2CID 14303240 . 
  6. ↑ تشاو، تشيكوان؛ بوزاس-كيرستجينز، أليخاندرو؛ ريبنتروست، باتريك؛ ويتيك، بيتر (2019). "التعلم العميق البايزي على حاسوب كمومي". ذكاء الآلة الكمومية . 1 ( 1-2 ): 41-51 . arXiv : 1806.11463 . doi : 10.1007/s42484-019-00004-7 . S2CID 49554188 . 
  7. ↑ أمبينيس، أندريس (2010). "تضخيم السعة المتغيرة زمنيًا وخوارزمية كمومية أسرع لحل أنظمة المعادلات الخطية". arXiv : 1010.4458 [ quant-ph ].
  8. ^ تسيمو، بينيل؛ جاياشانكار، أكشايا؛ سوجيساكي ، ك. باسكاران، نيشانث؛ تشاكرابورتي، سايان؛ براسانا، VS (2025). "تعزيز خوارزمية HHL في الأنظمة ذات الأرقام الشرطية الكبيرة" . أبحاث المراجعة البدنية . 7 (2): 023270. أرخايف : 2407.21641 . دوى : 10.1103/msvx-1drx .
  9. ↑ تشايلدز، أندرو م.؛ كوثاري، روبن؛ سوما، رولاندو د. (2017). "خوارزمية كمومية لأنظمة المعادلات الخطية مع تحسين أسي في الاعتماد على الدقة". مجلة SIAM للحوسبة . 46 (6): 1920-1950 . arXiv : 1511.02306 . doi : 10.1137/16m1087072 . ISSN 0097-5397 . S2CID 3834959 .  
  10. ↑ ووسنيغ، ليونارد؛ تشاو، تشيكوان؛ براكاش، أنوبام (2018). "خوارزمية نظام خطي كمومي للمصفوفات الكثيفة". رسائل المراجعة الفيزيائية . 120 (5) 050502. arXiv : 1704.06174 . Bibcode : 2018PhRvL.120e0502W . doi : 10.1103/PhysRevLett.120.050502 . PMID 29481180. S2CID 3714239 .  
  11. ↑ كاي، إكس. -دي؛ ويدبروك، كريستيان؛ سو، زد. -إي؛ تشين، إم. -سي؛ غو، مايل؛ تشو، إم. -جيه؛ لي، إل؛ ليو، إن. -إل؛ لو، تشاو-يانغ؛ بان، جيان-وي (2013). "الحوسبة الكمومية التجريبية لحل أنظمة المعادلات الخطية". رسائل المراجعة الفيزيائية . 110 (23) 230501. arXiv : 1302.4310 . Bibcode : 2013PhRvL.110w0501C . doi : 10.1103/PhysRevLett.110.230501 . PMID 25167475. S2CID 20427454 .  
  12. ↑ جينغوي وين، شيانغيو كونغ، شيجي وي، بيكسوي وانغ، تاو شين، وغيلو لونغ (2019). "التطبيق التجريبي للخوارزميات الكمومية لنظام خطي مستوحى من الحوسبة الكمومية الأديباتية". مجلة الفيزياء أ 99 ، 012320.
  13. ↑ سوباشي، يغيت؛ سوما، رولاندو د.؛ أورسوتشي، دافيد (14 فبراير 2019). "خوارزميات كمومية لأنظمة المعادلات الخطية مستوحاة من الحوسبة الكمومية الأديباتية". رسائل المراجعة الفيزيائية . 122 (6) 060504. arXiv : 1805.10549 . Bibcode : 2019PhRvL.122f0504S . doi : 10.1103/physrevlett.122.060504 . ISSN 0031-9007 . PMID 30822089. S2CID 73493666 .   
  14. ↑ كلادر، ب. د؛ جاكوبس، ب. س؛ سبراوس، س. ر (2013). "خوارزمية النظام الخطي الكمومي المُهيأ مسبقًا". رسائل المراجعة الفيزيائية . 110 (25) 250504. arXiv : 1301.2340 . Bibcode : 2013PhRvL.110y0504C . doi : 10.1103/PhysRevLett.110.250504 . PMID 23829722. S2CID 33391978 .  
  15. ↑ بيري، دومينيك و. (2010). "خوارزمية كمومية عالية الرتبة لحل المعادلات التفاضلية الخطية". مجلة الفيزياء أ: الرياضية والنظرية . 47 (10) 105301. arXiv : 1010.2745 . Bibcode : 2014JPhA...47j5301B . doi : 10.1088/1751-8113/47/10/105301 . S2CID 17623971 . 
  16. ↑ ليفي، ماكس ج. (5 يناير 2021). "خوارزميات كمومية جديدة تحل أخيرًا المعادلات غير الخطية" . مجلة كوانتا . تم الاطلاع عليه في 31 ديسمبر 2022 .
  17. ↑ ليو، جيه بي؛ كولدين، إتش أو؛ كروفي، إتش كيه؛ لوريرو، إن إف؛ تريفيسا، كيه؛ تشايلدز، إيه إم (2021). "خوارزمية كمومية فعالة للمعادلات التفاضلية غير الخطية المبددة" . وقائع الأكاديمية الوطنية للعلوم . 118 (35) e2026805118. arXiv : 2011.03185 . Bibcode : 2021PNAS..11826805L . doi : 10.1073/pnas.2026805118 . PMC 8536387. PMID 34446548 .  
  18. ↑ لويد، إس.؛ دي بالما، جي.؛ جوكلر، سي.؛ كياني، بي.؛ ليو، زد دبليو.؛ مارفيان، إم.؛ تيني، إف.؛ بالمر، تي. (2020). "خوارزمية كمومية للمعادلات التفاضلية غير الخطية". arXiv : 2011.06571 [ quant-ph ].
  19. ↑ مونتانارو، آشلي؛ باليستر، سام (2016). "الخوارزميات الكمومية وطريقة العناصر المحدودة". مجلة Physical Review A. 93 ( 3) 032324. arXiv : 1512.05903 . Bibcode : 2016PhRvA..93c2324M . doi : 10.1103/PhysRevA.93.032324 . S2CID 44004935 . 
  20. ↑ ويبي، ناثان؛ براون، دانيال؛ لويد، سيث (2012). "ملاءمة البيانات الكمومية". رسائل المراجعة الفيزيائية . 109 (5) 050505. arXiv : 1204.5242 . Bibcode : 2012PhRvL.109e0505W . doi : 10.1103/ PhysRevLett.109.050505 . PMID 23006156. S2CID 118439810 .  
  21. ↑ جاكييه، أنطوان (31 أكتوبر 2022). التعلم الآلي الكمي والتحسين في التمويل: على طريق الميزة الكمية . باكت . ص 349. ISBN  978-1-80181-787-5.
  22. ↑ باسكران، ن. (2023). "تكييف خوارزمية هارو-هاسيديم-لويد لنظرية الكم متعددة الأجسام" . مجلة Physical Review Research . 5 (4) 043113. Bibcode : 2023PhRvR...5d3113B . doi : 10.1103/PhysRevResearch.5.043113 .
  23. ↑ آرونسون، سكوت (2015). "اقرأ التفاصيل الدقيقة" . مجلة نيتشر فيزيكس . 11 (4): 291-293 . رمز Bibcode : 2015NatPh..11..291A . doi : 10.1038/nphys3272 . S2CID 122167250. تاريخ الاسترجاع: 9 مايو 2023 . 
  24. ↑ شولد، ماريا (2018). التعلم الخاضع للإشراف باستخدام الحواسيب الكمومية . دار نشر سبرينغر . ص 218. ISBN  978-3-319-96424-9.
  25. ↑ شولد، ماريا (2018). التعلم الخاضع للإشراف باستخدام الحواسيب الكمومية . دار نشر سبرينغر . ص 219. ISBN  978-3-319-96424-9.