خوارزمية BHT

في الحوسبة الكمومية ، تُعد خوارزمية براسارد-هوير-تاب ( BHT ) خوارزمية كمومية تحل مشكلة التصادم . في هذه المشكلة، يُعطى عدد صحيح موجب n ودالة تحويل من 2 إلى 1.${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$ويحتاج إلى إيجاد مدخلين يُقابلان نفس المخرج f . خوارزمية BHT تقوم فقط بـ${\displaystyle O(n^{1/3})}$الاستعلامات إلى f ، والتي تتطابق مع الحد الأدنى لـ${\displaystyle \Omega (n^{1/3})}$في نموذج الصندوق الأسود . ^{[ 1 ]} يمكن تعميم الخوارزمية إلى دالة من r إلى 1 بتعقيد قدره${\displaystyle O\left(\left({\frac {n}{r}}\right)^{1/3}\right)}$[ ^{2 ]​}

تم اكتشاف الخوارزمية بواسطة جيل براسارد وبيتر هوير وآلان تاب في عام 1997. ^{[ 3 ]} وهي تستخدم خوارزمية جروفر ، التي تم اكتشافها في العام السابق.

بشكل بديهي، تجمع الخوارزمية بين تسريع الجذر التربيعي من مفارقة عيد الميلاد باستخدام العشوائية (الكلاسيكية) مع تسريع الجذر التربيعي من خوارزمية جروفر (الكمومية).

أولًا، يتم اختيار n ^1/3 مدخلًا للدالة f عشوائيًا، ويتم الاستعلام عن f عند كل منها. إذا وُجد تصادم بين هذه المدخلات، فإننا نعيد زوج المدخلات المتصادم. وإلا، فإن جميع هذه المدخلات تُقابل قيمًا مختلفة بواسطة f . ثم تُستخدم خوارزمية غروفر لإيجاد مدخل جديد لـ f يتصادم. بما أن هناك n مدخلًا لـ f، و n ^1/3 منها قد تُشكّل تصادمًا مع القيم التي تم الاستعلام عنها مسبقًا، فإن خوارزمية غروفر تستطيع إيجاد تصادم مع${\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}$استعلامات إضافية إلى f . ^{[ 3 ]}

• مشكلة تمييز العناصر
• خوارزمية غروفر