কোয়ান্টাম কম্পিউটিংয়ের প্রায় সকল এক্সপোনেনশিয়াল গতির মূলে—শোরের মৌলিক উৎপাদক বিশ্লেষণ থেকে শুরু করে কোয়ান্টাম রসায়নের সিমুলেশন পর্যন্ত—রয়েছে কোয়ান্টাম ফুরিয়ার রূপান্তর (Quantum Fourier Transform বা QFT) এবং এর অনুসারী কোয়ান্টাম ফেজ এস্টিমেশন (Quantum Phase Estimation বা QPE)। যেখানে ক্ল্যাসিক্যাল ফাস্ট ফুরিয়ার ট্রান্সফর্ম (FFT) $N$-উপাদানের ভেক্টরের জন্য $mathcal{O}(N log N)$ ধাপ গ্রহণ করে, সেখানে QFT একটি $n$-কিউবিট কোয়ান্টাম স্টেটে ($N = 2^n$) মাত্র $mathcal{O}(n^2) = mathcal{O}((log N)^2)$ কোয়ান্টাম গেট অপারেশনে সম্পূর্ণ ফ্রিকোয়েন্সি স্পেস রূপান্তর সম্পন্ন করে।
১. বীজগাণিতিক রূপরেখা: DFT থেকে QFT
ক্ল্যাসিক্যাল ডিসক্রিট ফুরিয়ার রূপান্তর (DFT) একটি জটিল ভেক্টর $x = (x_0, x_1, dots, x_{N-1})^T in mathbb{C}^N$-কে রূপান্তরিত করে $y$ ভেক্টরে:
[
y_k = frac{1}{sqrt{N}} sum_{j=0}^{N-1} x_j omega^{j k}, quad text{যেখানে } omega = e^{2pi i / N}
]
কোয়ান্টাম মেকানিক্সে এই রূপান্তরটি $n$-কিউবিট হিলবার্ট স্পেসের অর্থোনরমাল ভিত্তি স্টেট ${|0rangle, dots, |N-1rangle}$-এর ওপর একটি ইউনিটারি অপারেটর হিসেবে ক্রিয়া করে:
[
text{QFT}_N |jrangle = frac{1}{sqrt{N}} sum_{k=0}^{N-1} e^{2pi i j k / 2^n} |krangle
]
যেহেতু রূপান্তর ম্যাট্রিক্স $F_N$-এর ক্ষেত্রে $F_N^dagger F_N = I_N$ সত্য, তাই QFT সম্পূর্ণভাবে ইউনিটারি এবং তথ্য সংরক্ষণকারী। একটি সাধারণ সুপারপজিশন $|psirangle = sum_{j=0}^{N-1} x_j |jrangle$-এর ওপর প্রয়োগ করলে স্টেটটি রূপান্তরিত হয়:
[
text{QFT}_N |psirangle = sum_{k=0}^{N-1} y_k |krangle, quad y_k = frac{1}{sqrt{N}} sum_{j=0}^{N-1} x_j e^{2pi i j k / 2^n}
]
২. প্রোডাক্ট রিপ্রেজেন্টেশন ও সার্কিট গঠন
ডন কপারস্মিথের উদ্ভাবিত QFT সার্কিটের মূল বৈশিষ্ট্য হলো আউটপুট স্টেটটিকে একটি নন-এন্ট্যাঙ্গেল্ড প্রোডাক্ট স্টেট হিসেবে প্রকাশ করা। বাইনারি ভগ্নাংশ নোটেশনে $j = j_1 j_2 dots j_n$ হলে:
[
0.j_l j_{l+1} dots j_n = sum_{m=l}^n j_m 2^{-(m-l+1)}
]
QFT রূপান্তরটিকে প্রতিটি কিউবিটের টেনসর গুণফল আকারে সাজানো যায়:
[
text{QFT}_N |j_1 j_2 dots j_nrangle = frac{1}{sqrt{2^n}} bigotimes_{l=1}^n left( |0rangle + e^{2pi i (0.j_l j_{l+1} dots j_n)} |1rangle right)
]
এই সমীকরণ থেকে স্পষ্ট যে, আউটপুট রেজিস্টারের প্রতিটি পৃথক কিউবিট একটি সুনির্দিষ্ট ফেজ ধারণ করে, যা ইনপুটের বাইনারি ডিজিটের ওপর নির্ভরশীল। এটি বাস্তবায়নে কেবল দুটি মৌলিক গেট ব্যবহৃত হয়:
- হ্যাডামার্ড গেট ($H$): প্রথম সুপারপজিশন এবং প্রধান ফেজ $0.j_l$ তৈরি করে:
[
H |j_lrangle = frac{1}{sqrt{2}} left( |0rangle + (-1)^{j_l} |1rangle right)
] - কন্ট্রোল্ড ফেজ-শিফট গেট ($R_k$): অন্যান্য কন্ট্রোল কিউবিটের ওপর ভিত্তি করে সূক্ষ্ম ফেজ যোগ করে:
[
R_k = begin{pmatrix} 1 & 0 \ 0 & e^{2pi i / 2^k} end{pmatrix}
]
$n$-কিউবিট রেজিস্টারের জন্য:
- ১ম কিউবিটে ১টি Hadamard এবং $n-1$ টি Controlled Phase শিফট ($R_2, dots, R_n$) প্রয়োজন হয়।
- ২য় কিউবিটে ১টি Hadamard এবং $n-2$ টি Controlled Phase শিফট প্রয়োজন হয়।
- মোট দুই-কিউবিট ফেজ গেটের সংখ্যা:
[
sum_{m=1}^{n-1} m = frac{n(n-1)}{2}
] - এর সাথে $n$ টি Hadamard এবং বিট ক্রম উল্টানোর জন্য $lfloor n/2 rfloor$ টি SWAP গেট যোগ করলে মোট জটিলতা দাঁড়ায়:
[
text{Total Gates} = frac{n(n-1)}{2} + n + lfloor n/2 rfloor = mathcal{O}(n^2)
]
$N = 2^{64}$ ($n = 64$ কিউবিট)-এর ক্ষেত্রে ক্ল্যাসিক্যাল FFT-এর প্রয়োজন হয় প্রায় $1.18 times 10^{21}$ অপারেশন, যেখানে QFT সার্কিটে মাত্র ২০৮০টি কোয়ান্টাম গেট প্রয়োজন!
৩. কোয়ান্টাম ফেজ এস্টিমেশন (QPE)
যেহেতু পরিমাপের মাধ্যমে QFT-এর সকল বিস্তার সরাসরি রিড করা সম্ভব নয়, তাই এর প্রকৃত শক্তি উন্মোচিত হয় বিপরীত রূপান্তর ($text{QFT}^dagger$) ব্যবহার করে ফেজ এস্টিমেশন অ্যালগরিদমে।
ধরা যাক একটি ইউনিটারি অপারেটর $U$ এবং এর আইগেনস্টেট $|urangle$ satisfies:
[
U |urangle = e^{2pi i theta} |urangle, quad theta in [0, 1)
]
QPE অ্যালগরিদম অজানা ফেজ $theta = 0.theta_1 theta_2 dots theta_t$-এর বাইনারি মান নির্ণয় করে। এটি দুটি রেজিস্টারে পরিচালিত হয়:
- কাউন্টিং রেজিস্টার (রেজিস্টার ১): $t$ সংখ্যক কিউবিট $|0rangle^{otimes t}$ অবস্থায় শুরু হয়, যা পরিমাপের পর $theta$-র মান প্রকাশ করবে।
- টার্গেট রেজিস্টার (রেজিস্টার ২): আইগেনস্টেট $|urangle$ ধারণ করে।
QPE-এর কার্যপ্রণালী:
- সুপারপজিশন তৈরি: রেজিস্টার ১-এ $H^{otimes t}$ প্রয়োগ করা হয়:
[
|psi_0rangle = frac{1}{sqrt{2^t}} sum_{j=0}^{2^t-1} |jrangle |urangle
] - কন্ট্রোল্ড-ইউনিটারি ক্যাসকেড: রেজিস্টার ১-এর $k$-তম কিউবিট থেকে টার্গেটে নিয়ন্ত্রিত $U^{2^k}$ ক্রিয়া প্রয়োগ করা হয়, যার ফলে ফেজ কিকব্যাক ঘটে:
[
|psi_1rangle = frac{1}{sqrt{2^t}} sum_{j=0}^{2^t-1} e^{2pi i theta j} |jrangle |urangle
] - বিপরীত কোয়ান্টাম ফুরিয়ার রূপান্তর ($text{QFT}^dagger$): লক্ষ্য করুন, $|psi_1rangle$ ঠিক $|2^t thetarangle$ স্টেটের QFT। অতএব এর ওপর $text{QFT}^dagger$ প্রয়োগ করলে আমরা ফিরে পাই:
[
text{QFT}^dagger |psi_1rangle = |2^t thetarangle = |theta_1 theta_2 dots theta_trangle
] - কম্পিউটেশনাল মেজারমেন্ট: রেজিস্টার ১ পরিমাপ করলে সরাসরি $theta$-র বাইনারি ডিজিটগুলো পাওয়া যায়।
৪. নির্ভুলতা ও ত্রুটির সীমা
যদি $theta$-কে নিখুঁতভাবে $t$ বিটে প্রকাশ করা না যায়, তবে নিকটতম বাইনারি ভগ্নাংশে স্টেট কেন্দ্রীভূত হয়। $n$-বিট নির্ভুলতা এবং কমপক্ষে $1 – epsilon$ সাফল্যের সম্ভাবনা নিশ্চিত করতে রেজিস্টার ১-এর কিউবিট সংখ্যা $t$ হতে হয়:
[
t = n + leftlceil log_2 left( 2 + frac{1}{2epsilon} right) rightrceil
]
এই কোয়ান্টাম ফেজ এস্টিমেশনই হলো আধুনিক ক্রিপ্টোগ্রাফি ভেঙে ফেলার হাতিয়ার—শোরের অ্যালগরিদমের মূল চালিকাশক্তি।
