مشكلة الاصطدام

تعد مشكلة الاصطدام r-إلى-1 مشكلة نظرية مهمة في نظرية التعقيد والحوسبة الكمومية والرياضيات الحسابية. غالبًا ما تشير مشكلة التصادم إلى الإصدار 2 إلى 1: معطى  زوجي والمعادلة، وبالتالي f هي إما 1 إلى 1 أو 2 إلى 1. يُسمح لنا فقط بإجراء استعلامات حول قيمة  لأي . تسأل المشكلة بعد ذلك عن عدد هذه الاستعلامات التي نحتاج إلى إجرائها لتحديد ما إذا كانت f تساوي 1 إلى 1 أو 2 إلى 1.

 حالة بياجباغ 
حتمي

يتطلب حل الإصدار 2 إلى 1 لاستفسارات . وبشكل عام، يتطلب التمييز بين وظائف r-to-1 من وظائف 1 إلى 1 لاستفسارات .

هذا تطبيق مباشر لمبدأ التصنيف: إذا كانت الوظيفة هي r-to-1، ثم بعد استفسارات  نضمن أننا وجدنا تصادمًا. إذا كانت الوظيفة 1 إلى 1 ، فلا يوجد تضارب. هكذا، استفسارات  تكفي .إذا لم يحالفنا الحظ، فإن أول استفسار  يمكن أن يعرض إجابات مميزة، لذلك استفسارات  ضرورية أيضًا.

عشوائ

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

 الحل الكمي 
تحل خوارزمية BHT ، التي تستخدم خوارزمية جروفرهذه المشكلة على النحو الأمثل من خلال تحويل استفسارات  إلى f.

تصنيف:خوارزميات
تصنيف:ميكانيكا الكم