কোয়ান্টাম অ্যালগরিদম একটি নতুন ধরনের সমস্যা জয় করে

1994 সালে, একজন গণিতবিদ আবিষ্কার করেছিলেন যে কীভাবে একটি কোয়ান্টাম কম্পিউটার এমন কিছু করা যায় যা কোনও সাধারণ ক্লাসিক্যাল কম্পিউটার পারে না। কাজটি প্রকাশ করেছে যে, নীতিগতভাবে, কোয়ান্টাম মেকানিক্সের নিয়মের উপর ভিত্তি করে একটি মেশিন দক্ষতার সাথে তার প্রধান কারণগুলির মধ্যে একটি বড় সংখ্যাকে বিভক্ত করতে পারে - একটি ক্লাসিক্যাল কম্পিউটারের জন্য একটি কাজ এত কঠিন যে এটি আজকের ইন্টারনেট নিরাপত্তার অনেকাংশের ভিত্তি তৈরি করে।

আশাবাদ একটি ঢেউ অনুসরণ. সম্ভবত, গবেষকরা ভেবেছিলেন, আমরা কোয়ান্টাম অ্যালগরিদম উদ্ভাবন করতে সক্ষম হব যা বিভিন্ন সমস্যার বিশাল পরিসরের সমাধান করতে পারে।

কিন্তু অগ্রগতি থমকে যায়। "এটি একটি bummer ট্র্যাজেক্টোরি একটি বিট হয়েছে," বলেন রায়ান ও'ডোনেল কার্নেগি মেলন বিশ্ববিদ্যালয়ের। "লোকেরা ছিল, 'এটি আশ্চর্যজনক, আমি নিশ্চিত যে আমরা অন্যান্য আশ্চর্যজনক অ্যালগরিদম সব ধরণের পেতে যাচ্ছি।' না।” বিজ্ঞানীরা একটি স্ট্যান্ডার্ড সেটের মধ্যে থেকে শুধুমাত্র একটি একক, সংকীর্ণ শ্রেণীর সমস্যার জন্য নাটকীয় গতির আবিষ্কার করেছেন এনপি বলা হয়, যার অর্থ তাদের দক্ষতার সাথে যাচাইযোগ্য সমাধান ছিল — যেমন ফ্যাক্টরিং।

প্রায় তিন দশক ধরে এটাই ছিল। এরপর এপ্রিলে গবেষক ড উদ্ভাবিত একটি মৌলিকভাবে নতুন ধরনের সমস্যা যা একটি কোয়ান্টাম কম্পিউটার একটি ক্লাসিক্যালের চেয়ে দ্রুতগতিতে সমাধান করতে সক্ষম হওয়া উচিত। এটি একটি জটিল গাণিতিক প্রক্রিয়ার ইনপুটগুলি গণনা করে, যা সম্পূর্ণরূপে এর জম্বল আউটপুটগুলির উপর ভিত্তি করে। সমস্যাটি একা দাঁড়িয়েছে নাকি অন্য অনেকের নতুন সীমান্তে প্রথম তা এখনও নির্ধারণ করা হয়নি।

"উত্তেজনার অনুভূতি আছে," বলেন বিনোদ বৈকুন্তনাথন, ম্যাসাচুসেটস ইনস্টিটিউট অফ টেকনোলজির একজন কম্পিউটার বিজ্ঞানী। "অনেক মানুষ সেখানে আর কী আছে তা নিয়ে ভাবছেন।"

কম্পিউটার বিজ্ঞানীরা তাদের প্রতিনিধিত্বকারী গাণিতিক মডেলগুলি অধ্যয়ন করে কোয়ান্টাম কম্পিউটারগুলি কী ভাল করে তা বোঝার চেষ্টা করেন। প্রায়শই, তারা একটি কোয়ান্টাম বা ক্লাসিক্যাল কম্পিউটারের একটি মডেল কল্পনা করে যা একটি ওরাকল নামক একটি আদর্শ গণনাকারী মেশিনের সাথে যুক্ত। ওরাকল হল সাধারণ গাণিতিক ফাংশন বা কম্পিউটার প্রোগ্রামের মতো, একটি ইনপুট গ্রহণ করে এবং একটি পূর্বনির্ধারিত আউটপুট বের করে দেয়। তাদের একটি এলোমেলো আচরণ থাকতে পারে, যদি ইনপুট একটি নির্দিষ্ট র্যান্ডম সীমার মধ্যে পড়ে তবে "হ্যাঁ" আউটপুট করে (বলুন, 12 থেকে 67) এবং যদি না হয় তবে "না"। অথবা সেগুলি পর্যায়ক্রমিক হতে পারে, যাতে 1 থেকে 10 এর মধ্যে একটি ইনপুট "হ্যাঁ", 11 থেকে 20 "না" প্রদান করে, 21 থেকে 30 আবার "হ্যাঁ" উৎপন্ন করে, ইত্যাদি।

ধরা যাক আপনার এই পর্যায়ক্রমিক ওরাকলগুলির মধ্যে একটি আছে এবং আপনি পিরিয়ড জানেন না। আপনি যা করতে পারেন তা হল এটির সংখ্যাগুলি খাওয়ানো এবং দেখুন এটি কী আউটপুট করে। এই সীমাবদ্ধতার সাথে, একটি কম্পিউটার কত দ্রুত পিরিয়ড খুঁজে পেতে পারে? 1993 সালে, ড্যানিয়েল সাইমন, তখন মন্ট্রিল ইউনিভার্সিটিতে, আবিষ্কার করেছিলেন যে একটি কোয়ান্টাম অ্যালগরিদম যে কোনও ক্লাসিক্যাল অ্যালগরিদমের চেয়ে দ্রুতগতিতে ঘনিষ্ঠভাবে সম্পর্কিত সমস্যার উত্তর গণনা করতে পারে।

ফলাফলটি সাইমনকে প্রথম ইঙ্গিতগুলির মধ্যে একটি নির্ধারণ করতে সক্ষম করেছিল যেখানে কোয়ান্টাম কম্পিউটারগুলির জন্য নাটকীয় শ্রেষ্ঠত্ব আশা করা যেতে পারে। কিন্তু যখন তিনি একটি শীর্ষস্থানীয় সম্মেলনে তার কাগজ জমা দেন, তখন তা প্রত্যাখ্যান করা হয়। কাগজটি অবশ্য সম্মেলনের প্রোগ্রাম কমিটির একজন জুনিয়র সদস্যকে আগ্রহী করেছিল — পিটার শোর, যিনি সেই সময়ে নিউ জার্সির বেল ল্যাবরেটরিজে ছিলেন। শোর দেখতে গিয়েছিলেন যে তিনি সাইমনের অ্যালগরিদমকে একটি ওরাকলের সময়কাল গণনা করার জন্য মানিয়ে নিতে পারেন, যদি এটি থাকে। তারপর তিনি বুঝতে পারলেন যে তিনি পর্যায়ক্রমিক ওরাকলের অনুরূপ আচরণ করে এমন একটি সমীকরণ সমাধান করতে আবার অ্যালগরিদমকে মানিয়ে নিতে পারেন: যে সমীকরণটি ফ্যাক্টরিংকে বর্ণনা করে, যা পর্যায়ক্রমিক।

শোর ফলাফল ছিল ঐতিহাসিক। তিনি যে কোয়ান্টাম অ্যালগরিদম আবিষ্কার করেছিলেন তা দ্রুত বিশাল সংখ্যাগুলিকে তাদের উপাদান প্রধান উপাদানগুলিতে হ্রাস করতে পারে, এমন কিছু যা কোনও পরিচিত শাস্ত্রীয় অ্যালগরিদম করতে পারে না। পরবর্তী বছরগুলিতে, গবেষকরা অন্যান্য দক্ষ কোয়ান্টাম অ্যালগরিদম আবিষ্কার করেছিলেন। তাদের মধ্যে কিছু, যেমন Shor এর অ্যালগরিদম, এমনকি সূচকীয় সুবিধা প্রদান করেছে, কিন্তু কেউ পর্যায়ক্রমিক নয় এমন কোনো NP সমস্যায় একটি নাটকীয় কোয়ান্টাম সুবিধা প্রমাণ করতে পারেনি।

অগ্রগতির এই অভাব দুই কম্পিউটার বিজ্ঞানীর নেতৃত্বে, স্কট অ্যারনসন টেক্সাস বিশ্ববিদ্যালয়ের, অস্টিন, এবং আন্দ্রিস আম্বাইনিস লাটভিয়া বিশ্ববিদ্যালয়ের, একটি পর্যবেক্ষণ করতে. কোয়ান্টাম সুবিধার প্রমাণগুলি সর্বদা ওরাকলের উপর নির্ভরশীল বলে মনে হয় যেগুলির মধ্যে একধরনের ননর্যান্ডম কাঠামো ছিল, যেমন পর্যায়ক্রমিকতা। 2009 সালে, তারা অনুমান করা যে এনপি সমস্যার নাটকীয় গতি হতে পারে না যা এলোমেলো, বা অসংগঠিত ছিল। কেউ এর ব্যতিক্রম খুঁজে পায়নি।

তাদের অনুমান কোয়ান্টাম কম্পিউটারের ক্ষমতার উপর একটি সীমাবদ্ধ রাখে। তবে এটি কেবল বলেছিল যে নির্দিষ্ট ধরণের অসংগঠিত এনপি সমস্যার জন্য কোনও নাটকীয় গতি নেই - যাদের হ্যাঁ বা না উত্তর রয়েছে। যদি একটি সমস্যা আরো নির্দিষ্ট, পরিমাণগত উত্তর খুঁজে বের করতে জড়িত থাকে, যা একটি অনুসন্ধান সমস্যা হিসাবে পরিচিত, অনুমানটি প্রযোজ্য নয়।

সেই কথা মাথায় রেখেই গবেষকরা তাকাশি ইয়ামাকাওয়া এনটিটি সোশ্যাল ইনফরমেটিক্স ল্যাবরেটরিজ এবং মার্ক জান্ড্রি এনটিটি রিসার্চ এবং প্রিন্সটন ইউনিভার্সিটি 2005 সালে প্রবর্তিত একটি নির্দিষ্ট অনুসন্ধান সমস্যা নিয়ে পরীক্ষা করার সিদ্ধান্ত নিয়েছে ওডেড রেগেভ.

আবহাওয়া ভ্যানের একটি সেট কল্পনা করুন যেগুলি একই দিকে নির্দেশ করছে। তাদের প্রত্যেককে একটি পরিমাপ করা ধাক্কা দিন, তারপর একটি দমকা হাওয়া তাদের দিককে প্রভাবিত করতে দিন। রেগেভ তাদের চূড়ান্ত দিকনির্দেশের ভিত্তিতে নির্ধারণ করতে চেয়েছিল, যেখানে তারা সবাই প্রাথমিকভাবে নির্দেশ করেছিল। এই ধরনের সমস্যাগুলিকে "ত্রুটির সাথে শেখা" বলা হয়, কারণ ঝাঁকুনি এবং বাতাস মূল দিকের এলোমেলো ত্রুটির উত্সের মতো কাজ করে। প্রমাণ আছে যে ক্লাসিক্যাল এবং কোয়ান্টাম অ্যালগরিদম উভয়ের জন্যই সমাধান করা কঠিন।

ইয়ামাকাওয়া এবং জান্ড্রি সেটআপটি টুইট করেছেন। তারা সেই স্টার্টিং শোভগুলির শক্তি পরিবর্তন করেছে, সেগুলিকে আরও অনুমানযোগ্য করে তুলেছে। তারা বাতাসকে একটি এলোমেলো ওরাকল দ্বারা নির্ধারিত করে যাতে এটি নির্দিষ্ট কিছু ক্ষেত্রে আরও বেশি এলোমেলো কিন্তু অন্যদের ক্ষেত্রে সম্পূর্ণরূপে সুপ্ত ছিল।

এই পরিবর্তনগুলির সাথে, গবেষকরা আবিষ্কার করেছেন যে একটি কোয়ান্টাম অ্যালগরিদম দক্ষতার সাথে প্রাথমিক দিকটি খুঁজে পেতে পারে। তারা এটাও প্রমাণ করেছে যে যেকোন ক্লাসিক্যাল অ্যালগরিদম অবশ্যই সূচকীয় ফ্যাক্টর দ্বারা ধীর হতে হবে। শোরের মতো, তারা তখন সমস্যার একটি বাস্তব-বিশ্ব সংস্করণ সমাধানের জন্য তাদের অ্যালগরিদমকে অভিযোজিত করেছিল, যা একটি প্রকৃত গাণিতিক সমীকরণের সাথে ওরাকলকে প্রতিস্থাপন করে।

কম্পিউটার বিজ্ঞানীরা এখনও সমস্যাটি বুঝতে এবং তৈরি করার জন্য কাজ করছেন। বৈকুন্তনাথন ডেটা কম্প্রেশন করার সময় উত্থাপিত একটি ভিন্নটির সাথে এটির তুলনা করেছেন: যখন তথ্য চাপা দেওয়া হচ্ছে, তখন দুটি বিট দুর্ঘটনাক্রমে একই জায়গায় চাপা দেওয়া যেতে পারে, তাদের ওভাররাইট করে। সেই সংঘর্ষগুলি আগে থেকেই ভবিষ্যদ্বাণী করার সমস্যা, যাতে আপনি সেগুলি এড়াতে পারেন, কিছু সাদৃশ্য বহন করে। "এটি একটি শ্রেণীর সমস্যা যা মূলত এইরকম দেখায়," তিনি বলেছিলেন। "সম্ভবত এই সমস্যাগুলি পরিমাণগতভাবে সমাধান করা যেতে পারে।"

আশা ছিল যে নতুনের মতো একটি অসংগঠিত সমস্যা এমনকি কোয়ান্টাম কম্পিউটারের আজকের নতুন সংস্করণেও সমাধানযোগ্য হতে পারে, যার ফলে তাদের পরীক্ষা করার একটি উপায় প্রদান করা হয়। চিন্তাভাবনা ছিল যে অসংগঠিত সমস্যাগুলি প্রোগ্রামে কম সংস্থান নিতে পারে, বা শব্দের প্রতি কম সংবেদনশীল হতে পারে, যেহেতু তারা ইতিমধ্যে এলোমেলো। কিন্তু এখনও অবধি, নতুন সমস্যাটি এখনও বিদ্যমান কোয়ান্টাম কম্পিউটারগুলির সমাধানের জন্য খুব উন্নত বলে মনে হচ্ছে। “এটা একটা অদ্ভুত সমস্যা। আমি এটি সংজ্ঞায়িত করার কথা ভাবিনি, "অ্যারনসন বলেছিলেন। "কিন্তু পূর্ববর্তী সময়ে, এর কিছু খুব সুন্দর বৈশিষ্ট্য রয়েছে।"

ফলাফল একটি অসংগঠিত NP সমস্যার নাটকীয় কোয়ান্টাম সুবিধার প্রথম উদাহরণ প্রদান করে। কোয়ান্টাম জগত কার্যত অমীমাংসিত থেকে সমাধানযোগ্য হতে পরিবর্তিত হয় এমন আরও অনেক সমস্যা হতে পারে? এখন এমনটা ভাবার আরও কারণ আছে।

"কোয়ান্টাম কম্পিউটারগুলি কী ধরণের সমস্যায় ভাল হতে পারে সে সম্পর্কে এটি আমাদের বিশ্বাসকে কিছুটা উল্টে দিয়েছে," ও'ডোনেল বলেছেন।