To'qnashuv muammosi - Collision problem

The r-to-1 to'qnashuvi muammosi muhim nazariy muammo hisoblanadi murakkablik nazariyasi, kvant hisoblash va hisoblash matematikasi. To'qnashuv muammosi ko'pincha 2 dan 1 gacha bo'lgan versiyaga tegishli:^[1] berilgan ${displaystyle n}$ hatto va funktsiya ${displaystyle f:, {1, ldots, n} kamar {1, ldots, n}}$, bizga f ham va'da qilingan 1dan 1gacha yoki 2 dan 1 gacha. Biz faqat qiymati haqida so'rovlar qilishga ruxsat beramiz ${displaystyle f (i)}$ har qanday kishi uchun ${displaystyle iin {1, ldots, n}}$. Muammo f ning 1 dan 1 gacha yoki 2 dan 1 gacha ekanligini aniqlik bilan aniqlash uchun qancha so'rov qilishimiz kerakligini so'raydi.

Bayagbag holati

Deterministik

2 dan 1 gacha bo'lgan versiyani hal qilish uchun hal qilish talab etiladi ${extstyle {frac {n} {2}} + 1}$ so'rovlar va umuman, r-to-1 funktsiyalarini 1 dan 1 gacha funktsiyalardan ajratish talab etiladi ${extstyle {frac {n} {r}} + 1}$ so'rovlar.

Bu to'g'ridan-to'g'ri dastur kaptar teshigi printsipi: agar funktsiya r-to-1 bo'lsa, u holda keyin ${extstyle {frac {n} {r}} + 1}$ Biz to'qnashuvni topganimizga kafolat beramiz. Agar funktsiya 1 dan 1 gacha bo'lsa, u holda to'qnashuv bo'lmaydi. Shunday qilib, ${extstyle {frac {n} {r}} + 1}$ so'rovlar etarli. Agar omadimiz kelmasa, unda birinchisi ${displaystyle n / r}$ so'rovlar aniq javoblarni qaytarishi mumkin, shuning uchun ${extstyle {frac {n} {r}} + 1}$ so'rovlar ham zarur.

Tasodifiy

Agar tasodifiylikka yo'l qo'ysak, muammo osonroq. Tomonidan tug'ilgan kungi paradoks, agar biz (aniq) so'rovlarni tasodifiy tanlasak, unda yuqori ehtimollik bilan har qanday sobit 2 dan 1 gacha funktsiyalarda to'qnashuvni topamiz ${displaystyle Theta ({sqrt {n}})}$ so'rovlar.

Kvant eritmasi

The BHT algoritmi, ishlatadigan Grover algoritmi, faqat muammoni hal qilish orqali ushbu muammoni maqbul tarzda hal qiladi ${displaystyle O (n ^ {1/3})}$ so'rovlar f.

Adabiyotlar

Bu fizika bilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.