ডয়েচ-জজোসা অ্যালগরিদম ক্ল্যাসিক্যাল ডিটারমিনিস্টিক কম্পিউটারের চেয়ে দ্রুত হলেও, সাধারণ ক্ল্যাসিক্যাল কম্পিউটারে দৈবচয়ন বা র্যান্ডমাইজড স্যাম্পলিং (BPP) ব্যবহার করলে মাত্র অল্প কয়েকটি কুয়েরিতে ডয়েচ-জজোসার উত্তর অনুমান করা যায়। ফলে বিজ্ঞানীদের মনে সংশয় ছিল: কোয়ান্টাম কম্পিউটার কি সব ধরণের ক্ল্যাসিক্যাল অ্যালগরিদমের চেয়ে সত্যই দ্রুত? ১৯৯৪ সালে ড্যানিয়েল সাইমন এই বিতর্কের চূড়ান্ত অবসান ঘটান। সাইমনের অ্যালগরিদম (Simon’s Algorithm) হলো বিজ্ঞানের ইতিহাসের প্রথম অ্যালগরিদম যা যেকোনো র্যান্ডমাইজড ক্ল্যাসিক্যাল কম্পিউটারের চেয়েও অকাট্যভাবে এক্সপোনেনশিয়াল হারে দ্রুততর। সাইমনের এই গাণিতিক কাঠামো দেখেই পিটার শোর অনুপ্রাণিত হয়েছিলেন তাঁর ঐতিহাসিক প্রাইম ফ্যাক্টরাইজেশন অ্যালগরিদম উদ্ভাবন করতে।
১. সাইমনের হিডেন পিরিওডিসিটি সমস্যা
ধরা যাক একটি ফাংশন $f: {0, 1}^n to {0, 1}^n$ আছে যার মধ্যে একটি গোপন $n$-বিটের স্ট্রিং $s$ লুকিয়ে রয়েছে। ফাংশনটির বৈশিষ্ট্য হলো এটি একটি টু-টু-ওয়ান (2-to-1) সিমেট্রি মেনে চলে:
$$f(x) = f(y) iff x oplus y = s quad text{বা} quad y = x oplus s$$
প্রতিটি আউটপুটের বিপরীতে ঠিক দুটি করে ইনপুট থাকে যা গোপন স্ট্রিং $s$ দিয়ে একে অপরের সাথে যুক্ত। আমাদের কাজ হলো এই গোপন স্ট্রিং $s$ খুঁজে বের করা।
ক্ল্যাসিক্যাল জটিলতা: বার্থডে প্যারাডক্স
ক্ল্যাসিক্যাল কম্পিউটারে $s$ বের করতে হলে এমন দুটি ভিন্ন ইনপুট খুঁজে পেতে হবে যাদের আউটপুট এক ($f(x) = f(y)$)। বিখ্যাত বার্থডে প্যারাডক্স (Birthday Paradox) অনুযায়ী, $2^n$ আকারের স্পেসে এমন একটি সংঘর্ষ (Collision) খুঁজে পেতে ক্ল্যাসিক্যাল কম্পিউটারে ন্যূনতম:
$$Q_{text{classical}} = Omegaleft(2^{n/2}right) quad text{কুয়েরি প্রয়োজন}$$
যদি $n = 128$ হয়, তবে ক্ল্যাসিক্যাল কম্পিউটারে প্রায় $1.8 times 10^{19}$ বার হিসাব করতে হবে, যা বাস্তবে অসম্ভব।
২. সাইমনের কোয়ান্টাম সার্কিট আর্কিটেকচার
সাইমনের অ্যালগরিদমে দুটি $n$-কিউবিট রেজিস্টার ব্যবহার করা হয়:
- প্রথম রেজিস্টারে হ্যাডামার্দ গেট প্রয়োগ করে সব ইনপুটের সুপারপজিশন তৈরি করা হয়।
- ওরাকল $U_f$ চালিয়ে দ্বিতীয় রেজিস্টারে $f(x)$ সংরক্ষণ করা হয়।
- দ্বিতীয় রেজিস্টার পরিমাপ করলে ধরা যাক একটি নির্দিষ্ট মান $f(x_0)$ পাওয়া গেল। এর ফলে প্রথম রেজিস্টারটি নিমেষে ঠিক সেই দুটি ইনপুটের সুপারপজিশনে কলাপ্স করে:
$$|psirangle = frac{|x_0rangle + |x_0 oplus srangle}{sqrt{2}}$$ - প্রথম রেজিস্টারে পুনরায় হ্যাডামার্দ গেট প্রয়োগ করে পরিমাপ করা হয়।
৩. কোয়ান্টাম অর্থোগোনালিটি সমীকরণ
দ্বিতীয় হ্যাডামার্দ প্রয়োগের পর ইন্টারফেয়ারেন্সের কারণে যেসব ভেক্টর $y$-এর সাথে গোপন $s$-এর ডট প্রোডাক্ট ১ হয় ($s cdot y equiv 1$), তারা ডেস্ট্রাক্টিভ ইন্টারফেয়ারেন্সে সম্পূর্ণ বাতিল হয়ে যায়।
ফলে পরিমাপে কেবল এমন ভেক্টর $y$ পাওয়া যায় যা গোপন $s$-এর ওপর লম্ব বা অর্থোগোনাল:
$$y cdot s = y_1 s_1 oplus y_2 s_2 oplus dots oplus y_n s_n = 0 pmod 2$$
৪. ক্ল্যাসিক্যাল গাউসিয়ান এলিমিনেশন
সার্কিটটি মাত্র $mathcal{O}(n)$ বার (যেমন $n + 20$ বার) চালালে ক্ল্যাসিক্যাল কম্পিউটার $n-1$ টি স্বাধীন লিনিয়ার সমীকরণ পেয়ে যায়। এরপর সাধারণ গাউসিয়ান এলিমিনেশনের মাধ্যমে মাত্র $mathcal{O}(n^3)$ সময়ে গোপন $s$-এর মান বের করে ফেলা হয়!
৫. শোরের অ্যালগরিদমের ঐতিহাসিক অনুপ্রেরণা
সাইমন প্রমাণ করেছিলেন যে কোয়ান্টাম কম্পিউটার কোনো গ্রুপের অন্তর্গত লুকানো পর্যায়কাল (Hidden Subgroup) খুঁজে বের করতে অতুলনীয় পারদর্শী। ১৯৯৪ সালের বসন্তে পিটার শোর সাইমনের এই গবেষণা পড়ার পরই বুঝতে পারেন যে, মডুলার এক্সপোনেনশিয়েশনের পিরিয়ড খুঁজে বের করতে এই নীতিটি প্রয়োগ করা সম্ভব—যার ফলশ্রুতিতে জন্ম নেয় বিশ্ববিখ্যাত শোরের অ্যালগরিদম।
