যেখানে শোরের অ্যালগরিদম কেবল বিশেষ গ্রুপ কাঠামোর ওপর এক্সপোনেনশিয়াল গতি প্রদান করে, সেখানে ১৯৯৬ সালে ল্যাভ গ্রোভার উদ্ভাবিত গ্রোভারের অ্যালগরিদম (Grover’s Algorithm) সম্পূর্ণ অসংগঠিত বা আনস্ট্রাকচার্ড অনুসন্ধানের ক্ষেত্রে প্রযোজ্য। $N$ টি উপাদান বিশিষ্ট একটি অবিন্যস্ত ডেটাবেসে নির্দিষ্ট একটি আইটেম খুঁজে পেতে যেকোনো ক্ল্যাসিক্যাল অ্যালগরিদমে গড়ে $N/2$ এবং সর্বোচ্চ $N$ টি কুয়েরি প্রয়োজন হয়। গ্রোভার অ্যালগরিদম কোয়ান্টাম মেকানিক্সের নিয়ম মেনে ঠিক $mathcal{O}(sqrt{N})$ কুয়েরিতে এই অনুসন্ধান সম্পন্ন করে, যা গণিতবিদদের দ্বারা প্রমাণিত কোয়ান্টাম অনুসন্ধানের চরম তাত্ত্বিক সীমা।
১. অসংগঠিত অনুসন্ধান সমস্যা ও কোয়ান্টাম ওরাকল
ধরা যাক $N = 2^n$ আকারের একটি ডেটাবেস রয়েছে যার উপাদানগুলোকে $n$-বিট স্ট্রিং $x in {0, 1}^n$ দ্বারা চিহ্নিত করা যায়। একটি বুলিয়ান ব্ল্যাক-বক্স ওরাকল ফাংশন $f(x)$ সংজ্ঞায়িত করা হলো:
[
f(x) = begin{cases} 1 & text{যদি } x = omega text{ (কাঙ্ক্ষিত উপাদান)} \ 0 & text{যদি } x neq omega end{cases}
]
কোয়ান্টাম কম্পিউটারে এই ফাংশনটি ফেজ ওরাকল $O_omega$ হিসেবে কাজ করে, যা কাঙ্ক্ষিত স্টেটের ফেজ ১৮০ ডিগ্রি উল্টে দেয়:
[
O_omega |xrangle = (-1)^{f(x)} |xrangle implies O_omega = I – 2|omegaranglelangleomega|
]
এটি জ্যামিতিকভাবে $|omegarangle$-এর লম্ব হাইপারপ্লেনের সাপেক্ষে একটি প্রতিফলন (Reflection)।
২. জ্যামিতিক ভিত্তি: দ্বিমাত্রিক সাবস্পেসে ঘূর্ণন
গ্রোভার অ্যালগরিদমের মূল সৌন্দর্য হলো, $2^n$ মাত্রার বিশাল হিলবার্ট স্পেসের ক্রিয়াটিকে একটি সরল ২-মাত্রিক সমতলের ঘূর্ণন হিসেবে উপস্থাপন করা যায়।
শুরুতে সকল স্টেটের সুষম সুপারপজিশন $|srangle$ তৈরি করা হয়:
[
|srangle = H^{otimes n} |0rangle^{otimes n} = frac{1}{sqrt{N}} sum_{x=0}^{N-1} |xrangle
]
এই স্টেটটিকে কাঙ্ক্ষিত স্টেট $|omegarangle$ এবং অবশিষ্টাংশ $|s’rangle$-এর রৈখিক সমন্বয়ে প্রকাশ করা যায়:
[
|s’rangle = frac{1}{sqrt{N-1}} sum_{x neq omega} |xrangle
]
[
|srangle = cosleft(frac{theta}{2}right) |s’rangle + sinleft(frac{theta}{2}right) |omegarangle, quad text{যেখানে } sinleft(frac{theta}{2}right) = frac{1}{sqrt{N}}
]
বৃহৎ $N$-এর জন্য প্রারম্ভিক কোণ $theta approx 2/sqrt{N}$।
৩. গ্রোভার ইটারেশন ও ডিফিউশন অপারেটর
একটি একক গ্রোভার ইটারেশন $G$ দুটি ধারাবাহিক প্রতিফলন নিয়ে গঠিত:
[
G = D cdot O_omega
]
এখানে $D$ হলো গ্রোভার ডিফিউশন অপারেটর (Inversion about the mean):
[
D = 2|sranglelangle s| – I
]
জ্যামিতির সাধারণ নিয়ম অনুযায়ী, দুটি রেখার মধ্যবর্তী কোণ যদি $theta/2$ হয়, তবে তাদের সাপেক্ষে পরপর দুটি প্রতিফলন একটি পূর্ণ $theta$ কোণের ঘূর্ণন তৈরি করে! অতএব ${|s’rangle, |omegarangle}$ সমতলে $G$ একটি রোটেশন ম্যাট্রিক্স:
[
G = begin{pmatrix} costheta & -sintheta \ sintheta & costheta end{pmatrix}
]
$k$ বার এই গ্রোভার অপারেটর প্রয়োগ করলে স্টেট ভেক্টরটি কোণ বাড়িয়ে কাঙ্ক্ষিত স্টেটের দিকে অগ্রসর হয়:
[
G^k |srangle = cosleft(frac{2k+1}{2} thetaright) |s’rangle + sinleft(frac{2k+1}{2} thetaright) |omegarangle
]
স্টেট ভেক্টরটিকে $|omegarangle$-এর সমান্তরাল করতে ঘূর্ণন কোণটিকে $pi/2$-এর সমান হতে হবে:
[
frac{2R + 1}{2} theta approx frac{pi}{2} implies R approx leftlfloor frac{pi}{4} sqrt{N} rightrceil
]
ঠিক $R approx frac{pi}{4}sqrt{N}$ বার পরিভ্রমণের পর পরিমাপ করলে কাঙ্ক্ষিত উপাদান পাওয়ার সম্ভাবনা দাঁড়ায় $P ge 1 – 1/N$। এর বেশি ইটারেশন চালালে স্টেটটি ওভার-রোটেট হয়ে লক্ষ্যভ্রষ্ট হয়!
৪. BBBV উপপাদ্য: কোয়ান্টাম চরম সীমার প্রমাণ
১৯৯৭ সালে বেনেট, বার্নস্টাইন, ব্রাসার্ড এবং ভাজিরানি (BBBV) কঠোর গাণিতিক প্রমাণ উপস্থাপন করেন যে, কোনো ব্ল্যাক-বক্স ওরাকল ভিত্তিক কোয়ান্টাম অ্যালগরিদম $Omega(sqrt{N})$-এর চেয়ে দ্রুত অসংগঠিত অনুসন্ধান সম্পন্ন করতে পারে না। ফলে গ্রোভার অ্যালগরিদম কেবল শক্তিশালীই নয়, এটি প্রকৃতির নিয়মের চরম সীমানায় অবস্থিত।
