কোয়ান্টাম অ্যালগোরিদম

কোয়ান্টাম কম্পিউটিং এর ক্ষেত্রে কোয়ান্টাম এলগরিদম বলতে এমন একটি এলগরিদম বোঝায় যা কোয়ান্টাম কম্পিউটিং এর সত্যিকার মডেলের উপর ভর করে চলে, যা পরিমাপের কোয়ান্টাম সার্কিট মডেলে বহুল ব্যবহৃত হয়। চিরায়ত এলগরিদম নির্দেশাবলীর সীমিত ধারা, অথবা একটি সমস্যা সমাধানের ক্রমশ ধারা, যেখানে ধারার প্রত্যেক অংশ সাধারণ কম্পিউটার দিয়ে তৈরী করা যায়। কোয়ান্টাম এলগরিদমও একই ব্যবস্থা যার ধারার প্রত্যেক অংশ কোয়ান্টাম কম্পিউটার দিয়ে করা হয়। যাদিও কোয়ান্টাম কম্পিউটার দিয়ে সাধারণ কম্পিউটারের সব কাজ করা যায়, কোয়ান্টাম এলগরিদম শব্দটি ব্যবহার করার কারণ সেসব এলগরিদম এর জন্যে যা কোয়ান্টাম লেভেলের জন্য প্রযোজ্য, অথবা যেটা কোয়ান্টাম কম্পিউটিং যেমন কোয়ান্টাম সুপারপজিশন বা কোয়ান্টাম এন্ট্যাঙ্গলমেন্ট এর কিছু প্রয়োজনীয় বৈশিষ্ট্য ব্যবহারের জন্য। 
যেসব সমস্যা সাধারণ কম্পিউটার দিয়ে সমাধান করা যায়না সেসব সমস্যা কোয়ান্টাম কম্পিউটার দিয়েও সমাধান করা যায়না। কিন্তু কোয়ান্টাম এলগরিদম সাধারণ এলগরিদমের চেয়ে দ্রুত কাজ করবে।
সবচেয়ে পরিচিত এলগরিদম হল ফ্যাক্টরিং এর জন্য শরের এলগরিদম, এবং অনির্মীত ডাটাবেজের জন্য গ্রোভারের এলগরিদম। শরের এলগরিদম সবচেয়ে ভাল সাধারণ এলগরিদম জেনারেল নাম্বার ফিল্ড সিয়েভ এর তুলনায় এক্সপোনেনশিয়ালি দ্রুত কাজ করে, আর গ্রোভারের এলগরিদম একইভাবে কোয়াড্র্যাটিক্যালি দ্রুত কাজ করে।
কোয়ান্টাম কম্পিউটিং এর ক্ষেত্রে কোয়ান্টাম এলগরিদম বলতে এমন একতি এলগরিদম বোঝায় যা কোয়ান্টাম কম্পিউটিং এর সত্যিকার মডেলের উপর ভর করে চলে, যা পরিমাপের কোয়ান্টাম সার্কিট মডেলে বহুল ব্যবহৃত হয়। চিরায়ত এলগরিদম নির্দেশাবলীর সীমিত ধারা, অথবা একটি সমস্যা সমাধানের ক্রমশ ধারা, যেখানে ধারার প্রত্যেক অংশ সাধারণ কম্পিউটার দিয়ে তৈরী করা যায়। কোয়ান্টাম এলগরিদমও একই ব্যবস্থা যার ধারার প্রত্যেক অংশ কোয়ান্টাম কম্পিউটার দিয়ে করা হয়। যদিও কোয়ান্টাম কম্পিউটার দিয়ে সাধারণ কম্পিউটারের সব কাজ করা যায়, কোয়ান্টাম এলগরিদম শব্দটি ব্যবহার করার কারণ সেসব এলগরিদম এর জন্যে যা কোয়ান্টাম লেভেলের জন্য প্রযোজ্য, অথবা যেটা কোয়ান্টাম কম্পিউটিং যেমন কোয়ান্টাম সুপারপজিশন বা কোয়ান্টাম এন্ট্যাঙ্গলমেন্ট এর কিছু প্রয়োজনীয় বৈশিষ্ট্য ব্যবহারের জন্য। 
যেসব সমস্যা সাধারণ কম্পিউটার দিয়ে সমাধান করা যায়না সেসব সমস্যা কোয়ান্টাম কম্পিউটার দিয়েও সমাধান করা যায়না। কিন্তু কোয়ান্টাম এলগরিদম সাধারণ এলগরিদমের চেয়ে দ্রুত কাজ করবে।
সবচেয়ে পরিচিত এলগরিদম হল ফ্যাক্টরিং এর জন্য শরের এলগরিদম, এবং অনির্মীত ডাটাবেজের জন্য গ্রোভারের এলগরিদম। শরের এলগরিদম সবচেয়ে ভাল সাধারণ এলগরিদম জেনারেল নাম্বার ফিল্ড সিয়েভ এর তুলনায় এক্সপোনেনশিয়ালি দ্রুত কাজ করে, আর গ্রোভারের এলগরিদম একইভাবে কোয়াড্র্যাটিক্যালি দ্রুত কাজ করে।
কোয়ান্টাম এলগরিদম সাধারণত কোয়ান্টাম সার্কিট (যা কিছু কিউবিট এর ইনপুটে কিছু পরিমাপ নিঃসরণ করে) এর মাধ্যমে সাধারনভাবে ব্যবহৃত কোয়ান্টাম কম্পিউটিং এর সার্কিট মডেল হিসেবে বর্ণিত হয়। কোয়ান্টাম সার্কিট কোয়ান্টাম গেট এর মাধ্যমে তৈরী হয় যা নির্দিষ্ট সংখ্যক কিউবিটের সমন্বয়ে গঠিত। কোয়ান্টাম এলগরিদম কোয়ান্টাম কম্পিউটিং এর আরো কিছু মডেল যেমন হ্যামিল্টনিয়ান ওরাকল মডেল-এ বিবৃত হতে পারে।
কোয়ান্টাম এলগরিদমকে এলগরিদমের ব্যবহৃত প্রয়োগকৌশল দ্বারা শ্রেণীকরণ করা যায়। কিছু ব্যবহৃত প্রয়োগকৌশল হল দশার ধাক্কা, দশা যাচাই, কোয়ান্টাম ফুরিয়ার ট্রান্সফর্ম, চূড়া বর্ধিতকরণ ও টপোলজিক্যাল কোয়ান্টাম ক্ষেত্র তত্ত্ব। এছাড়া সমস্যা সমাধানের দিক থেকেও বিভাগ করা যায়, যেমন বীজগাণিতীক সমস্যায় কোয়ান্টাম এলগরিদম এর জরিপ।
কোয়ান্টাম ফুরিয়ার ট্রান্সফর্ম বিচ্ছিন্ন ফুরিয়ার ট্রান্সফর্ম এর কোয়ান্টাম সদৃশ উদাহরণ। হ্যাডামার্ড ট্রান্সফর্ম একটি নির্দিষ্ট ক্ষেত্রে এন-মাত্রার ভেক্টর স্পেসের একটি উদাহরণ। কোয়ান্টাম ফুরিয়ার ট্রান্সফর্মকে কোয়ান্টাম কম্পিউটার দ্বারা সহজেই কোয়ান্টাম গেট এর পলিনোমিয়াল সংখ্যা ব্যবহার করে নিখুতভাবে বাস্তবায়ন করা যায়। 
ডয়চ-জসা এলগরিদম একটি ব্ল্যাক বক্স সমস্যা সমাধান করে যা যেকোন সাধারণ কম্পিউটারের সমাধান করতে এক্সপোনেনশিয়ালি বেশি সময় লাগবে, কিন্তু কোয়ান্টাম কম্পিউটার দিয়ে তা এক পলকে করে দিতে পারছে। যদি আমরা উভয় কোয়ান্টাম ও সাধারণ কম্পিউটারের এলগরিদমের ক্ষেত্রে বাউন্ডেড এর দেখি, তাহলে সাধারণ এলগরিদমের নির্দিষ্ট সংখ্যক কোয়েরি (যার ভুল হবার সম্ভাবনা অনেক কম) এর সমস্যার সমাধান করার ক্ষেত্রে তেমন কোন গতি নেই। এই এলগরিদমই বলে দেয় যে একটি ফাংশান নির্দিষ্ট (সব ইনপুট ০ অথবা) নাকি চলক (অর্ধেক ক্ষেত্রে ইনপুট ০ ও বাকী অর্ধেক ১)।
সায়মনের এলগরিদম একটি ব্ল্যাক বক্স সমস্যা সমাধান করে যা যেকোন সাধারণ এলগরিদমের সমাধান করতে ব্যাখ্যা মূলকভাবে বেশি সময় লাগবে, বাউন্ডেড এর এলগরিদমও। এই এলগরিদম (যা সকল সাধারণ এলগরিদমের চেয়ে এক্সপোনেনশিয়ালি দ্রুত) শরের ফ্যাক্টরিং এলগরিদমের জন্যে প্রেরণাস্বরুপ। 
কোয়ান্টাম দশা যাচাই এলগরিদম একটি ঐকিক গেটের আইগেনভেক্টরের আইগেনদশা হিসাব করতে ব্যবহৃত হয় যা দ্বারা আইগেনভেক্টরের সমানুপাতিক কোয়ান্তাম দশা পাওয়া যায় এবং পরিশেষে গেটে প্রবেশাধিকার দেয়। এই এলগরিদম অন্যান এলগরিদমের সাবরুটিন হিসেবে ব্যবহৃত হয়।
শরের এলগরিদম পলনোমিয়াল সময়ে বিচ্ছিন্ন এলগরিদম ও ইন্টিজার ফ্যাক্টরাইজেশন এর সমস্যার সমাধান দেয়, যেখানে সবচেয়ে ভাল সাধারণ এলগরিদম সুপার-পলনোমিয়াল সময় নিতে পারে। এটা সেসব কোয়ান্টাম এলগরিদমের একটি যা নন-ব্ল্যাকবক্স সমস্যা পলিনোমিয়াল সময়ে সমাধান করতে পারে।
এ্যাবেলিয়ান গুপ্ত উপশ্রেণী সমস্যা অনেকগুলো সমস্যার যোগফল যা কোয়ান্টাম কম্পিউটার দ্বারা করা যায়, যেমন সায়মন সমস্যা যা পেল’র সমীকরন এর সমাধান দেয় (যা রিং ও ফ্যাক্টরিং এর প্রধান আদর্শ পরীক্ষা করে)। কিছু এ্যাবেলিয়ান গুপ্ত উপশ্রেণী সমস্যা সমাধানের কার্যকর কোয়ান্টাম এলগরিদম রয়েছে।
কার্যকর কোয়ান্টাম এলগরিদমগুলোকে নন-এ্যাবেলিয়ান শ্রেণী বলা হয়। যাই হোক, প্রতিসম শ্রেণীর জন্যে কোন কার্যকর এলগরিদম নেই, যা ডাইহেড্রাল শ্রেণী (যা কিছু ল্যাটিস সমস্যার সমাধান দেয়) লেখ সমরূপরেখার জন্য কার্যকর এলগরিদম দেয়।
একটি পরীক্ষনীয় রূপরেখায় বোসন স্যাম্পলিং সমস্যা মনে করে মাঝারী সংখ্যার বোসন এর ইনপুটে ইউনিটারিটিতে বাধিত হয়ে বৃহৎ সংখ্যায় অনিয়মিতভাবে বিক্ষিপ্ত হয়। কিন্তু সমস্যা দাড়ায় যখন এটা থেকে সম্ভাব্যতা বিন্যাস বের করার চেষ্টা করা হয় যা ইউনিটারিটি ও বোসনের ইনপুটের বিন্যাসের উপর নির্ভর করে। এই সমস্যাকে সাধারণ কম্পিউটার এলগরিদম দিয়ে সমাধান করার জন্যে ইউনিটারি ট্রান্সফর্ম ম্যাট্রিক্স লাগবে, যা হয় অসম্ভব বা অনেক সময় লাগবে। ২০১৪ সালে বলা হয়েছিল যে বর্তমান প্রযুক্তি এবং একক ফোটন অবস্থা উদ্ভূতকারী সাধারণ পদ্ধতিকে উপযুক্ত কোয়ান্টাম পরিমাপযোগ্য রৈখিক দৃষ্টীয় নেটওয়ার্ক এর ইনপুট হিসেবে ব্যবহৃত হয় এবং প্রোব্যবিলিটি ডিস্ট্রিবিউশান এর আউটপুটের স্যাম্পলিং হয়ত নির্দেশকভাবে কোয়ান্টাম এলগরিদমের চেয়ে বড় হবে। ২০১৫ সালে তদন্ত অনুমান করে যে এই সমস্যার মতই জটিলতা রয়েছে স্যাম্পলিং সমস্যায়, যার ইনপুট ফোক অবস্থার ফোটন এর চেয়ে আলাদা এবং চিরায়ত সিমুলেশন থেকে পরিমাপযোগ্য জটিলতা এবং বোসন স্যাম্পলিং সমস্যার মধ্যে রূপান্তর হিসেবে পাওয়া যায়, যা সুসঙ্গত বিস্তারের ইনপুটের আকারের উপর নির্ভরশীল।
গাউস সংখ্যা এক ধরনের এক্সপোনেনশিয়াল সংখ্যা। এই সংখ্যা হিসাব করতে সাধারণ এলগরিদমের ব্যাখ্যা মূলকভাবে বেশি সময় লাগে। যদিও বিচ্ছিন্ন লগারিদম সমস্যা গাউস সংখ্যার হিসাবে কমে আসে, গাউস সংখ্যা হিসাব করার জন্যে একটি কার্যকর সাধারণ লগারিদম হয়ত বিচ্ছিন্ন লগারিদম পরিমাপের জন্যে একটি কার্যকর সাধারণ লগারিদম হত, যা অসম্ভাব্য মনে করা হয়। যাই হোক, কোয়ান্টাম কম্পিউটার গাউস সংখ্যা পলিনোমিয়াল সূক্ষতার সাথে পলিনোমিয়াল সময়ে হিসাব করতে পারে।.
একটি জ্ঞানগর্ভ সিদ্ধান্ত আছে যা n সংখ্যক অনিয়মিত বুলিয়ান নিয়ে গঠিত, যা n সংখ্যক বিট স্ট্রিংকে একতি বুলিয়ান মানে ম্যাপিং করতে পারে। আমাদের n সংখ্যক বিট খুজে বের করতে হবে (z1,z2,……..zn) যেমন হ্যাডামার্ড ফুরিয়ার ট্রান্সফর্,এর জন্য ৩/৪ স্ট্রিং দ্বারা পূরন কর যায়,
অথবা ১/৪ দ্বারা পূরন করা যায়,
এটা বিকিউপি দ্বারা করা যায়।
বিস্তার প্রসারণ এমন একতি ব্যবস্থা যার মাধ্যমে একটি নির্দিষ্ট কোয়ান্টাম স্টেটের একটি নির্দিষ্ট সাবস্পেসের বর্ধনের অনুমতি দেয়। এর ব্যবহার সাধারণ এলগরিদমের উপর দ্বিঘাত দ্রুততা আনে। একে গ্রোভারের এলগরিদমের সাধারনীকরন বলা যায়।
গ্রোভারের এলগরিদম সাধারণ এলগরিদমের Ω("N") কোয়েরির বদলে formula_3 কোয়েরি ব্যবহার করে N প্রবেশের মধে দাগান্বিত প্রবেশের জন্য অনির্মীত ডাটাবেজে খোজে। সাধারনভাবে বাউন্ডেড এরর সমস্যা মাথায় রাখলে Ω("N") কোয়েরিও ব্যবহার করতে হয়।
কোয়ান্টাম গনণা খোজার সমস্যাটিকে সাধারনীকরন করে। এটি অসজ্জিত তালিকা থেকে দাগান্বিত প্রবেশের সংখ্যা গনণার সমস্যার সমাধান করে। ঠিকভাবে বললে এটি N উপাদানের তালিকা থেকে দাগান্বিত প্রবেশের সংখ্যা গনণা করে, যার formula_4 ভুল formula_5 কোয়েরি, যেখানে k হল তালিকায় দাগান্বিত উপাদানের সংখ্যা। আরো ঠিকভাবে বললে এলগরিদম আউটপুটের হিসেবে k এর বদলে k’ ব্যবহার করে, যা নির্ভুলতা হলঃ formula_6
কোয়ান্টাম ওয়াক সাধারণ চিরায়ত ওয়াকের কোয়ান্টাম সদৃশ, যাকে কিছু অবস্থার উপর প্রোব্যবলিটি ডিস্ট্রিবিউশান দ্বারা ব্যাখ্যা করা যায়। কোয়ান্টাম ওয়াককে কিছু অবস্থার উপর কোয়ান্টাম সুপারপজিশন দিয়ে ব্যাখ্যা করা যায়। কোয়ান্টাম ওয়াক কিছু ব্ল্যাকবক্স সমস্যার ক্ষেত্রে এক্সপোনেনশিয়াল দ্রুততা আনে। এটা কিছু সমস্যার ক্ষেত্রে পলিনোমিয়াল দ্রুততাও আনে। কোয়ান্টাম ওয়াক এলগরিদমের তৈরীর একটি কাঠামো আছে যা অনেকটা বহুমুখী হয়।
উপাদানের বিচ্ছিন্নতা সমস্যা এমন একটা সমস্যা যা একটি তালিকার সকল উপাদান বিচ্ছিন্ন কিনা তা বের করার ব্যাপারে। সাধারনভাবে Ω("N") কোয়েরিগুলো N আকারের তালিকা তৈরী করার কাজে লাগে, যখন এই সমস্যা Ω("N") কোয়েরিওয়ালা খোজ সমস্যার চেয়েও কঠিন। যাইহোক, এটি কোয়ান্টাম কম্পিউটারে formula_7 কোয়েরি দিয়ে সমাধান করা যায়। সন্তোষজনক এলগরিদম হল এন্ড্রিস এম্ব্যানিস এর। ইয়ায়ুন শাই প্রথমবার প্রমাণ করেন যে সীমা সন্তোষজনকভাবে বড় হলে টানটান নিম্ন বন্ধন পাওয়া যায়। এম্ব্যানিস ও কুটিন স্বাধীনভাবে সকল ফাংশানের জন্য এই বন্ধন পাওয়ার চেষ্টা করেন। 
ত্রিকোন খোজার সমস্যা এমন একটি সমস্যা যা একটি লেখে ত্রিকোন আছে কিনা তা দেখে। কোয়ান্তাম লগারিদমের সবচেয়ে ভাল নিম্ন বন্ধনের হল Ω("N")। কিন্তু সবচেয়ে ভাল লগারিদমের O("N") কোয়েরি লাগে, আগের O("N") কোয়েরি এর চেয়ে উন্নত।
সূত্র একটি গাছ যার প্রত্যেকটা অন্তর্বর্তী গ্রন্থি একেকটা দ্বার এবং প্রত্যেকটা পাতার গ্রন্থি একেকটা ইনপুট। সমস্যা হল ঐ সূত্র মূল্যায়ন, যা ঐ গাছের শিকড় গ্রন্থি। 
একটি চর্চিত সূত্র ন্যান্ড গেট দ্বারা তৈরী বাইনারী গাছ মাত্র। এসব ধরনের সূত্রের অনিয়মিততা ব্যবহার করে Θ("N") কোয়েরী প্রয়োজন হয়, যেখানে formula_8। যাই হোক, কোয়ান্টাম এলগরিদম ব্যবহার করে একে Θ("N") কোয়েরি দিয়েই সমাধান করা যায়। এর জন্যে ভাল কোন কোয়ান্টাম এলগরিদম পাওয়া যায়নি যতদিন হ্যামিল্টনিয়ান সিদ্ধান্তের মডেল আসে। প্রমিত ব্যবস্থার জন্যেও একই অবস্থা দ্রুতই আবিষ্কৃত হয়।
আরো জটিল সূত্রের জন্য আরো কোয়ান্টাম এলগরিদম পাওয়া যায়।
এর সমস্যা হল k জেনারেটরের ব্ল্যাকবক্স শ্রেণী বিনিময় করে কিনা তা নির্ণয় করে। ব্ল্যাকবক্স শ্রেণী হল এমন একটি শ্রেণি যার সিদ্ধান্তের ফাংশান আছে, যা শ্রেণীর ক্রিয়াকলাপ করতে ব্যবহৃত হয়। আমরা কোয়েরি জটিলতার প্রতি আগ্রহী, যা সেই সিদ্ধান্তের সংখ্যা যা আমাদের সমস্যা সমাধানের জন্যে প্রয়োজন। এই নির্ণায়ক ও অনিয়মিত কোয়েরি জটিলতা হল যথাক্রমে formula_9 ও formula_10। একটি কোয়ান্টাম এলগরিদমের formula_11 কোয়ারি লাগে কিন্তু সবচেয়ে ভালটি হল কোয়েরি।
কিছু লিখা দেখিয়েছে যে জোনস পলিনোমিয়াল এর শর্তে কেম-সায়মন টপোলজিক্যাল কোয়ান্টাম ক্ষেত্র তত্ত্ব (TQFT) সমাধান করা যায়। কোয়ান্টাম কম্পিউটার TQFT তত্ত্ব স্টিমুলেট করতে পারে, এবং জোনাস পলিনোমিয়াল অনুমান করতে পারে, যা আমরা যতদূর জানি সাধারনভাবে বের করা যথেষ্ট কষ্টসাধ্য।
কোয়ান্টাম কম্পিউটার সাধারণ কম্পিউটারের চেয়ে শক্তিশালী হবে সে ধারণা পাওয়া যায় রিচার্ড ফাইনম্যানের পর্যবেক্ষণ থেকে যা বলে, কোয়ান্টাম কম্পিউটার বস্তুর কোয়ান্টাম ব্যবস্থা বর্নণা করতে এক্সপোনেনশিয়ালি বেশি সময় নিবে। এরপর থেকে কোয়ান্টাম কম্পিউটার কোয়ান্টাম ফিজিক্যাল ধারা সাধারণ কম্পিউটারের চেয়ে এক্সপোনেনশিয়ালি দ্রুত স্টিমুলেট করতে পারবে এ বিষয়টি ভাল করেই জানানো হয়। কার্যকর কোয়ান্টাম এলগরিদম বোসনিক ও ফার্মিওনিক উভয় ব্যবস্থাই স্টিমুলেট করতে সাহায্য করেছে এবং মাত্র কয়েক শত কিউবিট দিয়েই রাসায়নিক বিক্রিয়া স্টিমুলেট করা যায় যা সাধারণ সুপারকম্পিউটারের ধারণারও বাইরে। এটি দ্বারা TQFT ও স্টিমুলেট করা যায়। এর ফলে কোয়ান্টাম এলগরিদম কোয়ান্টাম টপোলজিক্যাল চলক এর হিসাব যেমন জোনস ও HOMFLY পলিনোমিয়াল, এবং তিন মাত্রার ম্যানিফোল্ডে টুরাভ ভিরু চলক ইত্যাদি হিসাবে সাহায্য করে।
হাইব্রিড কোয়ান্টাম/চিরায়ত এলগরিদম কোয়ান্টাম অবস্থা তৈরীর ও চিরায়ত নিখুঁততার সাহায্যে পরিমাপের সমন্বয়কারী। এই এলগরিদম সাধারণত ভূমি লেভেল হার্মিলশিয়ান চালক এর আইগেনভেক্টর ও আইগেন মান নির্ণয়ে সাহায্য করে।