الخوارزمية الكمومية

تحل خوارزمية دويتش-جوزا مشكلة الصندوق الأسود التي تتطلب عددًا هائلاً من الاستعلامات لأي حاسوب كلاسيكي حتمي، بينما يمكن للحاسوب الكمومي حلها باستعلام واحد فقط. مع ذلك، عند مقارنة الخوارزميات الكلاسيكية والكمومية ذات الخطأ المحدود، لا يوجد تسارع ملحوظ، إذ يمكن للخوارزمية الاحتمالية الكلاسيكية حل المشكلة بعدد ثابت من الاستعلامات مع احتمال خطأ ضئيل. تحدد الخوارزمية ما إذا كانت الدالة f ثابتة (تساوي 0 لجميع المدخلات أو 1 لجميع المدخلات) أو متوازنة (تساوي 1 لنصف نطاق المدخلات و0 للنصف الآخر).

تُعدّ خوارزمية برنشتاين-فازيراني أول خوارزمية كمومية تحلّ مشكلة بكفاءة أعلى من أفضل الخوارزميات الكلاسيكية المعروفة. وقد صُممت لإنشاء فصل مثالي بين خوارزميتي BQP و BPP .

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

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

تحل خوارزمية شور مسألة اللوغاريتم المتقطع ومسألة تحليل الأعداد الصحيحة إلى عواملها الأولية في زمن متعدد الحدود، ^{[ 9 ]} بينما تستغرق أفضل الخوارزميات الكلاسيكية المعروفة زمنًا فائقًا متعدد الحدود. ولا يُعرف ما إذا كانت هاتان المسألتان تندرجان ضمن فئة P أو NP-complete . كما أنها من بين الخوارزميات الكمومية القليلة التي تحل مسألة غير صندوق أسود في زمن متعدد الحدود، في حين أن أفضل الخوارزميات الكلاسيكية المعروفة تعمل في زمن فائق متعدد الحدود.

تُعدّ مسألة الزمرة الفرعية المخفية الأبيلية تعميمًا للعديد من المسائل التي يُمكن حلّها بواسطة الحاسوب الكمومي، مثل مسألة سيمون، وحلّ معادلة بيل ، واختبار المثالي الرئيسي للحلقة R، وتحليل العناصر . توجد خوارزميات كمومية فعّالة معروفة لمسألة الزمرة الفرعية المخفية الأبيلية. ^{[ 10 ]} أما مسألة الزمرة الفرعية المخفية الأكثر عمومية، حيث لا تكون الزمرة بالضرورة أبيلية، فهي تعميم للمسائل المذكورة سابقًا، بالإضافة إلى تماثل الرسوم البيانية وبعض مسائل الشبكة . توجد خوارزميات كمومية فعّالة معروفة لبعض الزمر غير الأبيلية. مع ذلك، لا توجد خوارزميات فعّالة معروفة للزمرة المتناظرة ، والتي من شأنها أن تُقدّم خوارزمية فعّالة لتماثل الرسوم البيانية ^{[ 11 ]} ، ولا للزمرة ثنائية السطوح ، والتي من شأنها أن تحلّ بعض مسائل الشبكة. ^{[ 12 ]}

مجموع غاوس هو نوع من المجاميع الأسية . أفضل خوارزمية كلاسيكية معروفة لتقدير هذه المجاميع تستغرق وقتًا أسيًا. بما أن مسألة اللوغاريتم المتقطع تُختزل إلى تقدير مجموع غاوس، فإن وجود خوارزمية كلاسيكية فعالة لتقدير مجاميع غاوس يستلزم وجود خوارزمية كلاسيكية فعالة لحساب اللوغاريتمات المتقطعة، وهو أمر يُعتبر غير مرجح. مع ذلك، تستطيع الحواسيب الكمومية تقدير مجاميع غاوس بدقة متعددة الحدود في وقت متعدد الحدود. ^{[ 13 ]}

لنفترض وجود أوراكل يتكون من n دالة منطقية عشوائية تربط سلاسل نصية مكونة من n بت بقيمة منطقية، بهدف إيجاد n سلسلة نصية مكونة _من n بت z₁ , ..., zₙ بحيث يحقق تحويل هادامارد-فورييه على الأقل 3/4 من هذه السلاسل الشرط التالي _:

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

ويرضي ذلك ربع العدد على الأقل

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2.}$

يمكن القيام بذلك في وقت متعدد الحدود الكمومي ذي الخطأ المحدود (BQP). ^{[ 14 ]}

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

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

يُعالج العدّ الكمومي تعميمًا لمشكلة البحث. فهو يُعالج مشكلة عدّ عدد العناصر المُعلّمة في قائمة غير مُرتبة، بدلاً من مجرد اكتشاف وجودها. تحديدًا، يحسب عدد العناصر المُعلّمة في${\displaystyle N}$قائمة من العناصر تحتوي على خطأ لا يتجاوز${\displaystyle \varepsilon }$عن طريق صنع فقط${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$الاستعلامات، حيث${\displaystyle k}$يمثل عدد العناصر المميزة في القائمة. ^{[ 17 ] [ 18 ]} وبشكل أدق، تُخرج الخوارزمية تقديرًا.${\displaystyle k'}$ل${\displaystyle k}$عدد الإدخالات المميزة، بدقة${\displaystyle |kk'|\leq \varepsilon k}$.

تفترض مسألة أخذ عينات البوزونات في التكوين التجريبي ^{[ 22 ]} مدخلات من البوزونات (مثل الفوتونات) ذات عدد معتدل، تتشتت عشوائيًا في عدد كبير من أنماط الإخراج، مقيدة بوحدة محددة . عند استخدام فوتونات منفردة، تصبح المسألة متماثلة مع مسار كمومي متعدد الفوتونات. ^{[ 23 ]} تكمن المسألة حينها في إنتاج عينة عادلة من التوزيع الاحتمالي للإخراج، والذي يعتمد على ترتيب البوزونات المدخلة والوحدة. ^{[ 24 ]} يتطلب حل هذه المسألة باستخدام خوارزمية حاسوبية تقليدية حساب الثابت لمصفوفة التحويل الوحدوي، وهو ما قد يستغرق وقتًا طويلًا للغاية أو يكون مستحيلًا تمامًا. في عام 2014، اقتُرح ^{[ 25 ]} أنه يمكن استخدام التقنيات الحالية والأساليب الاحتمالية القياسية لتوليد حالات الفوتون الواحد كمدخلات في شبكة بصرية خطية قابلة للحوسبة الكمومية مناسبة ، وأن أخذ عينات من التوزيع الاحتمالي للإخراج سيكون متفوقًا بشكل واضح باستخدام الخوارزميات الكمومية. في عام 2015، توقعت التحقيقات ^{[ 26 ]} أن مشكلة أخذ العينات لها تعقيد مماثل للمدخلات الأخرى غير فوتونات حالة فوك وحددت انتقالًا في التعقيد الحسابي من قابل للمحاكاة الكلاسيكية إلى صعوبة مماثلة لمشكلة أخذ عينات البوزون، اعتمادًا على حجم مدخلات السعة المتماسكة.

تُعرف مشكلة تمييز العناصر بأنها مشكلة تحديد ما إذا كانت جميع عناصر القائمة متميزة. تقليديًا،${\displaystyle \Omega (N)}$يلزم إجراء استعلامات لقائمة بحجم${\displaystyle N}$ومع ذلك، يمكن حلها في${\displaystyle \Theta (N^{2/3})}$استعلامات على حاسوب كمومي. طُرحت الخوارزمية المثلى بواسطة أندريس أمبينيس ^{[ 27 ]} ، وأثبت ياويون شي لأول مرة حدًا أدنى دقيقًا عندما يكون حجم النطاق كبيرًا بما فيه الكفاية ^{[ 28 ]} . قام أمبينيس ^{[ 29 ]} وكوتين ^{[ 30 ]} بشكل مستقل (وعبر براهين مختلفة) بتوسيع هذا العمل للحصول على الحد الأدنى لجميع الدوال.

تُعرف مشكلة إيجاد المثلثات بأنها تحديد ما إذا كان رسم بياني مُعطى ذو N رأسًا يحتوي على مثلث ( زمرة من الحجم 3). بافتراض إمكانية الوصول إلى مصفوفة التجاور للرسم البياني، فإن تعقيد الاستعلام الكلاسيكي هو${\displaystyle \Theta (N^{2})}$لأن هذا يمثل تعقيد الاستعلام اللازم لإيجاد أي حافة على الإطلاق في رسم بياني يحتوي على مثلث واحد فقط. في المقابل، بالنسبة للخوارزميات الكمومية، فإن الحد الأدنى هو${\displaystyle \Omega (N)}$عدد الاستعلامات اللازمة للعثور على أي حافة باستخدام خوارزمية غروفر. مع ذلك، فإن العثور على أي حافة لا يضمن العثور على مثلث، إن وُجد. يُجري غروفر بحثًا على جميع${\displaystyle \Theta (N^{3})}$تُحل المثلثات المحتملة المشكلة، ولكن يمكن تحسين تعقيد الاستعلام، O( N ^{3/2 ). [ 31 ]}

بينما${\displaystyle \Omega (N)}$لا يزال هذا هو الحد الأدنى الأكثر شهرة للخوارزميات الكمومية، حيث تتطلب أفضل خوارزمية معروفة O( N ^5/4 ) استعلامًا، ^{[ 32 ]} وهو تحسن عن أفضل خوارزمية سابقة O( N ^1.3 ) استعلامًا. ^{[ 21 ] [ 33 ]}

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

تُعدّ شجرة الدوائر الثنائية المتوازنة التي تحتوي على بوابات NAND فقط صيغةً مدروسةً جيداً. ^{[ 34 ]} يتطلب هذا النوع من الصيغ${\displaystyle \Theta (N^{c})}$الاستعلامات باستخدام العشوائية، ^{[ 35 ]} حيث${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$لكن باستخدام خوارزمية كمومية، يمكن حلها في${\displaystyle \Theta (N^{1/2})}$الاستفسارات. لم تكن هناك خوارزمية كمومية أفضل معروفة لهذه الحالة حتى تم العثور على واحدة لنموذج أوراكل هاميلتوني غير التقليدي. ^{[ 7 ]} وسرعان ما تبع ذلك نفس النتيجة للإعداد القياسي. ^{[ 36 ]}

كما تُعرف خوارزميات كمومية سريعة لصيغ أكثر تعقيدًا. ^{[ 37 ]}

تكمن المشكلة في تحديد ما إذا كانت مجموعة الصندوق الأسود ، المعطاة بـ k مولدات، تبديلية . مجموعة الصندوق الأسود هي مجموعة مزودة بدالة وسيطة، يجب استخدامها لإجراء عمليات المجموعة (الضرب، والمعكوس، والمقارنة مع العنصر المحايد). يكمن الاهتمام في هذا السياق في تعقيد الاستعلام، وهو عدد استدعاءات الدالة الوسيطة اللازمة لحل المشكلة. تعقيد الاستعلام الحتمي والعشوائي هما${\displaystyle \ثيتا (ك^{2})}$و${\displaystyle \Theta (k)}$على التوالي. ^{[ 38 ]} تتطلب الخوارزمية الكمومية${\displaystyle \Omega (ك^{2/3})}$الاستعلامات، بينما تستخدم الخوارزمية الكلاسيكية الأكثر شهرة${\displaystyle O(k^{2/3}\log k)}$استفسارات. ^{[ 39 ]}

أثبت ويتن أن نظرية تشيرن-سيمونز الطوبولوجية للحقل الكمومي (TQFT) يمكن حلها بدلالة كثيرات حدود جونز . يستطيع الحاسوب الكمومي محاكاة نظرية TQFT، وبالتالي تقريب كثيرة حدود جونز، ^{[ 41 ]} والتي يصعب حسابها كلاسيكيًا في أسوأ الحالات، على حد علمنا.

نشأت فكرة تفوق الحواسيب الكمومية على الحواسيب التقليدية من ملاحظة ريتشارد فاينمان بأن الحواسيب التقليدية تستغرق وقتًا أُسّيًا لمحاكاة الأنظمة الكمومية متعددة الجسيمات، بينما تستطيع الأنظمة الكمومية متعددة الأجسام "حل نفسها بنفسها". ^{[ 42 ]} ومنذ ذلك الحين، تطورت فكرة قدرة الحواسيب الكمومية على محاكاة العمليات الفيزيائية الكمومية بسرعة أُسّية تفوق سرعة الحواسيب التقليدية، وتوسعت بشكل كبير. وقد طُوّرت خوارزميات كمومية فعّالة (أي تعمل في زمن متعدد الحدود) لمحاكاة كل من الأنظمة البوزونية والفيرميونية، ^{[ 43 ]} بالإضافة إلى محاكاة التفاعلات الكيميائية التي تتجاوز قدرات الحواسيب العملاقة التقليدية الحالية باستخدام بضع مئات من الكيوبتات فقط. ^{[ 44 ]} كما تستطيع الحواسيب الكمومية محاكاة نظريات الحقول الكمومية الطوبولوجية بكفاءة عالية. ^{[ 45 ]} بالإضافة إلى أهميتها الجوهرية، أدت هذه النتيجة إلى خوارزميات كمومية فعالة لتقدير الثوابت الطوبولوجية الكمومية مثل كثيرات حدود جونز ^{[ 46 ]} و HOMFLY ، ^{[ 47 ]} وثابت توراييف-فيرو للمشعبات ثلاثية الأبعاد. ^{[ 48 ]}

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

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

تستلهم خوارزمية التحسين التقريبي الكمومي من عملية التلدين الكمومي، حيث تُجري تقريبًا متقطعًا لهذه العملية باستخدام دارة كمومية. ويمكن استخدامها لحل مسائل في نظرية المخططات. ^{[ 51 ]} وتستفيد الخوارزمية من التحسين الكلاسيكي للعمليات الكمومية لتعظيم "دالة الهدف".

تُطبّق خوارزمية حلّ القيم الذاتية الكمومية التباينية (VQE) التحسين الكلاسيكي لتقليل القيمة المتوقعة للطاقة لحالة افتراضية ، وذلك لإيجاد الحالة الأرضية لمؤثر هيرميتي، مثل هاميلتونيان الجزيء. ^{[ 52 ]} ويمكن توسيع نطاقها أيضًا لإيجاد طاقات الإثارة لهاميلتونيانات الجزيئات. ^{[ 53 ]}

تعمل خوارزمية حل القيم الذاتية الكمومية المنكمشة (CQE) على تقليل الباقي الناتج عن انكماش (أو إسقاط) معادلة شرودنغر على فضاء إلكترونين (أو أكثر) لإيجاد طاقة الحالة الأرضية أو المثارة ومصفوفة الكثافة المختزلة للإلكترونين لجزيء ما. ^{[ 54 ]} وهي تعتمد على الطرق الكلاسيكية لحل الطاقات ومصفوفات الكثافة المختزلة للإلكترونين مباشرةً من معادلة شرودنغر المنكمشة المضادة للهرميتية. ^{[ 55 ]}

• دالزيل، ألكسندر م.؛ وآخرون  . (2025). الخوارزميات الكمومية . arXiv : 2310.03011 . doi : 10.1017/9781009639651 . ISBN 978-1-009-63965-1.
• سميث، ج.؛ موسكا، م. (2012). "خوارزميات للحواسيب الكمومية". دليل الحوسبة الطبيعية . ص 1451-1492 . arXiv : 1001.0767 . doi : 10.1007/978-3-540-92910-9_43 . ISBN  978-3-540-92909-3. S2CID 16565723 . 
• تشايلدز، أ.م.؛ فان دام، و. (2010). "الخوارزميات الكمومية للمسائل الجبرية". مراجعات الفيزياء الحديثة . 82 (1): 1-52 . arXiv : 0812.0380 . Bibcode : 2010RvMP...82....1C . doi : 10.1103/RevModPhys.82.1 . S2CID 119261679 .