তাত্ত্বিক কম্পিউটার বিজ্ঞানে কোনো কম্পিউটারের ক্ষমতা তার ক্লক স্পিড দিয়ে মাপা হয় না, বরং মাপা হয় অ্যাসিম্পটোটিক কম্পিউটেশনাল কমপ্লেক্সিটি ক্লাস দিয়ে। ক্লাসিক্যাল চার্চ-টুরিং থিসিস দাবি করেছিল যে, বাস্তব পৃথিবীতে যেকোনো ভৌত অ্যালগরিদমকে ক্ল্যাসিক্যাল সম্ভাবনাময় টুরিং মেশিন ($text{BPP}$) দিয়ে পলিনমিয়াল সময়ে অনুকরণ করা যায়। কিন্তু ১৯৯৩ সালে উমেশ ওয়াজিরানি এবং ইথান বার্নস্টাইন কোয়ান্টাম সার্কিটের আনুষ্ঠানিক কাঠামো তৈরি করে উপস্থাপন করেন নতুন জটিলতা শ্রেণী BQP (Bounded-Error Quantum Polynomial-Time)। BQP মূলত নির্ধারণ করে কোয়ান্টাম কম্পিউটার ঠিক কোন কোন সমস্যা পলিনমিয়াল সময়ে কার্যকরভাবে সমাধান করতে পারে এবং এটি ক্লাসিক্যাল গণনার ধারণাকে চিরতরে বদলে দিয়েছে।
১. BQP ক্লাসের আনুষ্ঠানিক সংজ্ঞা
একটি সিদ্ধান্ত সমস্যা BQP শ্রেণীর অন্তর্ভুক্ত হবে যদি এমন একটি কোয়ান্টাম সার্কিট পরিবার $C_n$ তৈরি করা যায় যা তিনটি শর্ত পূরণ করে:
- ইউনিফর্মিটি: একটি সাধারণ ক্ল্যাসিক্যাল টুরিং মেশিন পলিনমিয়াল সময়ে সার্কিটটির নকশা তৈরি করতে পারে।
- পলিনমিয়াল গেট সংখ্যা: সার্বজনীন সেট ${H, S, text{CNOT}, T}$ থেকে ব্যবহৃত মোট গেটের সংখ্যা ইনপুটের আকারের পলিনমিয়াল ($text{poly}(n)$)-এর বেশি হবে না।
- ভুলের সীমাবদ্ধতা: সঠিক উত্তরের সম্ভাবনা অন্তত ২/৩ (বা ৬৭%) হতে হবে এবং ভুলের সম্ভাবনা ১/৩-এর কম হতে হবে।
সার্কিটটিকে মাত্র কয়েকবার চালিয়ে সংখ্যাগরিষ্ঠ ভোট (Majority Vote) গ্রহণ করলে এই ভুলের হার নিমেষেই শূন্যের কাছাকাছি নামিয়ে আনা যায়।
২. কমপ্লেক্সিটি চিড়িয়াখানায় BQP-এর অবস্থান
ক্লাসিক্যাল জটিলতা কাঠামোর সাথে BQP-এর সম্পর্ক:
$$text{P} subseteq text{BPP} subseteq text{BQP} subseteq text{PSPACE}$$
- BPP $subseteq$ BQP: যেকোনো ক্ল্যাসিক্যাল র্যান্ডমাইজড অ্যালগরিদমকে কোয়ান্টাম কম্পিউটারে টোফোলি ও হ্যাডামার্দ গেট দিয়ে অবিকল চালানো যায়।
- BQP $subseteq$ PSPACE: একটি কোয়ান্টাম সার্কিটের প্রতিটি সম্ভাব্য পথের বিস্তার পলিনমিয়াল মেমোরি ব্যবহার করে ডেপথ-ফার্স্ট সার্চের মাধ্যমে হিসাব করা সম্ভব। ফলে BQP কখনোই PSPACE-কে অতিক্রম করতে পারে না।
৩. BQP বনাম NP: একটি বহুল প্রচলিত বিভ্রান্তি
অনেকেই ভাবেন যে কোয়ান্টাম কম্পিউটার সব সুপারপজিশন একসাথে হিসেব করে সব ধরণের কঠিন NP-Complete সমস্যা (যেমন ট্রাভেলিং সেলসম্যান বা 3-SAT) নিমেষে সমাধান করে ফেলবে। কিন্তু তাত্ত্বিক কম্পিউটার বিজ্ঞান প্রমাণ করেছে যে এই ধারণাটি ভুল।
BBBV উপপাদ্য (1997)
চার্লস বেনেট, ইথান বার্নস্টাইন, জিল ব্রাসার এবং উমেশ ওয়াজিরানি অকাট্যভাবে প্রমাণ করেন যে, কোনো সাধারণ ডেটাবেসের $N = 2^n$ আইটেমের মধ্যে খোঁজার জন্য যেকোনো কোয়ান্টাম অ্যালগরিদমে ন্যূনতম:
$$Omegaleft(sqrt{N}right) quad text{ওরাকল কুয়েরি প্রয়োজন}$$
গ্রোভারের অ্যালগরিদম এই গতি অর্জন করে। কিন্তু $2^n$-এর বর্গমূল হলো $2^{n/2}$, যা কিছুটা দ্রুত হলেও ইনপুট $n$-এর সাপেক্ষে এখনও এক্সপোনেনশিয়াল। ফলে কোয়ান্টাম কম্পিউটার দিয়েও সাধারণ NP-Complete সমস্যার কোনো পলিনমিয়াল শর্টকাট পাওয়া যায় না।
BQP এবং NP-এর প্রকৃত মেলবন্ধন
তাত্ত্বিক বিজ্ঞানীদের মতে BQP এবং NP দুটি ভিন্ন গোলার্ধের বাসিন্দা। প্রাইম ফ্যাক্টরাইজেশন (Shor’s Algorithm) BQP-এর ভেতর অবস্থান করে কিন্তু ক্ল্যাসিক্যাল BPP-তে নেই। অন্যদিকে 3-SAT-এর মতো কঠিন সমস্যাগুলো NP-তে আছে কিন্তু BQP-এর বাইরে রয়ে গেছে।
