শোরের অ্যালগরিদম দিয়ে ব্যাংকিং ক্রিপ্টোগ্রাফি ভাঙার অনেক আগেই তাত্ত্বিক পদার্থবিজ্ঞানীরা কোয়ান্টাম কম্পিউটিংয়ের গাণিতিক শ্রেষ্ঠত্ব প্রমাণের সন্ধান করছিলেন। ১৯৯২ সালে ডেভিড ডয়েচ এবং রিচার্ড জজোসা প্রথম এমন একটি কোয়ান্টাম অ্যালগরিদম আবিষ্কার করেন যা ক্ল্যাসিক্যাল কম্পিউটারের চেয়ে অসীম গুণ দ্রুত শতভাগ নির্ভুল ফলাফল দিতে পারে। পরবর্তীতে ১৯৯৭ সালে ইথান বার্নস্টাইন এবং উমেশ ওয়াজিরানি এর উন্নত সংস্করণ তৈরি করেন। ডয়েচ-জজোসা এবং বার্নস্টাইন-ভাজিরানি অ্যালগরিদম আধুনিক কোয়ান্টাম প্রোগ্রামিংয়ের সবচেয়ে গুরুত্বপূর্ণ অস্ত্র—ফেজ কিকব্যাক (Phase Kickback) এবং কোয়ান্টাম ইন্টারফেয়ারেন্সের দিগন্ত উন্মোচন করে।
১. ডয়েচ-জজোসা ওরাকল সমস্যা
ধরা যাক একটি ব্ল্যাক-বক্স ফাংশন বা ওরাকল $f(x)$ আছে যা $n$-বিট ইনপুট নিয়ে ১-বিট আউটপুট দেয়। আমাদের নিশ্চিত করা আছে যে ফাংশনটি দুটি শ্রেণীর যেকোনো একটির অন্তর্ভুক্ত:
- ধ্রুবক (Constant): সব ইনপুটের জন্যই আউটপুট একই (হয় সবার জন্য ০, নয়তো সবার জন্য ১)।
- সুষম (Balanced): ঠিক অর্ধেক ইনপুটের জন্য আউটপুট ০ এবং বাকি অর্ধেক ইনপুটের জন্য আউটপুট ১।
ক্ল্যাসিক্যাল জটিলতা
ক্ল্যাসিক্যাল ডিটারমিনিস্টিক কম্পিউটারে এই প্রশ্নের উত্তর নিশ্চিতভাবে জানতে হলে চরম প্রতিকূল অবস্থায় মোট $2^{n-1} + 1$ বার ফাংশনটি চালাতে হবে। যদি $n = 64$ বিট হয়, তবে মহাবিশ্বের বয়স পার হয়ে গেলেও ক্ল্যাসিক্যাল কম্পিউটারে এই হিসাব শেষ করা সম্ভব নয়।
২. ফেজ কিকব্যাক (Phase Kickback)-এর জাদু
টার্গেট কিউবিটকে যদি সুপারপজিশন অবস্থা $|-rangle = frac{|0rangle – |1rangle}{sqrt{2}}$-এ রাখা হয়, তবে ওরাকল $U_f$ চালানোর পর ঘটে এক বিস্ময়কর ঘটনা:
$$U_f |xrangle |-rangle = (-1)^{f(x)} |xrangle |-rangle$$
টার্গেট কিউবিট অপরিবর্তিত থাকে, কিন্তু ফাংশনের আউটপুট $f(x)$ একটি ফেজ ফ্যাক্টর $(-1)^{f(x)}$ হিসেবে ইনপুট কিউবিটের মাথায় লাফিয়ে পড়ে! একেই বলা হয় ফেজ কিকব্যাক।
৩. অ্যালগরিদমের কার্যপ্রণালী ও শতভাগ ইন্টারফেয়ারেন্স
- সমস্ত ইনপুট কিউবিটকে হ্যাডামার্দ গেট দিয়ে $2^n$ সংখ্যক অবস্থার সমান সুপারপজিশনে রূপান্তর করা হয়।
- একবার ওরাকল $U_f$ চালানো হয়, যার ফলে প্রতি স্টেটের সাথে $(-1)^{f(x)}$ ফেজ যুক্ত হয়।
- পুনরায় সমস্ত ইনপুট কিউবিটের ওপর হ্যাডামার্দ গেট প্রয়োগ করে পরিমাপ করা হয়।
ফলাফলের গাণিতিক বিভাজন
- যদি ফাংশনটি ধ্রুবক (Constant) হয়: সমস্ত স্টেটগুলোর ফেজ এক হওয়ায় তারা কনস্ট্রাক্টিভ ইন্টারফেয়ারেন্স তৈরি করে এবং পরিমাপে ১০০% নিশ্চিতভাবে $|00dots 0rangle$ পাওয়া যায়।
- যদি ফাংশনটি সুষম (Balanced) হয়: অর্ধেক প্লাস এবং অর্ধেক মাইনাস টার্ম পরস্পরকে ডেস্ট্রাক্টিভ ইন্টারফেয়ারেন্সে বাতিল করে দেয়। ফলে $|00dots 0rangle$-এর সম্ভাবনা শূন্য হয়ে যায় এবং অন্য যেকোনো স্টেট পাওয়া যায়।
যেখানে ক্ল্যাসিক্যাল কম্পিউটারে কোটি কোটি বছর লাগত, সেখানে কোয়ান্টাম কম্পিউটার মাত্র ১টি একক কুয়েরিতে (Single Query) শতভাগ নির্ভুলভাবে বলে দেয় ফাংশনটি ধ্রুবক নাকি সুষম!
৪. বার্নস্টাইন-ভাজিরানি অ্যালগরিদম
বার্নস্টাইন-ভাজিরানি সমস্যায় একটি গোপন $n$-বিটের স্ট্রিং $s$ লুকিয়ে থাকে যেখানে $f(x) = s cdot x pmod 2$। ক্ল্যাসিক্যাল কম্পিউটারে এই গোপন পাসওয়ার্ডটি বের করতে $n$ বার কুয়েরি করতে হয়। কিন্তু একই কোয়ান্টাম সার্কিট ব্যবহার করে মাত্র ১টি কুয়েরিতে সরাসরি সম্পূর্ণ গোপন পাসওয়ার্ড $s$ আউটপুট রেজিস্টারে ফুটে ওঠে।
