ত্রিশ বছর পরে, কোয়ান্টাম ফ্যাক্টরিংয়ের জন্য একটি গতি বৃদ্ধি | কোয়ান্টা ম্যাগাজিন

পিটার শোর ইন্টারনেট ভাঙার জন্য সেট আউট না. কিন্তু 1990-এর দশকের মাঝামাঝি সময়ে তিনি যে অ্যালগরিদম তৈরি করেছিলেন তা ঠিক সেটাই করার হুমকি দিয়েছিল। ক ল্যান্ডমার্ক পেপার, শোর দেখিয়েছেন যে কীভাবে একটি অনুমানমূলক কম্পিউটার যেটি কোয়ান্টাম পদার্থবিজ্ঞানের ছদ্মবেশগুলিকে কাজে লাগিয়েছে তা যেকোন সাধারণ ক্লাসিক্যাল মেশিনের চেয়ে অনেক বেশি দ্রুত তাদের প্রধান উপাদানগুলিতে বিভক্ত করতে পারে।

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

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

"এটি সত্যিই অসাধারণ যে কেউ দৃশ্যত এই ফলাফলের জটিলতা অনেক, অনেক বছর পরে উন্নত করতে সক্ষম হয়েছে," বলেন অ্যাশলে মন্টানারো, ব্রিস্টল বিশ্ববিদ্যালয়ের কোয়ান্টাম কম্পিউটিং গবেষক। "এটি সত্যিই উত্তেজনাপূর্ণ।"

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

রেগেভ উচ্চ-মাত্রিক জ্যামিতির সাথে সম্পর্কিত ক্রিপ্টোগ্রাফির একটি শাখার কৌশলগুলির সাথে শোর অ্যালগরিদমকে বাড়িয়ে তার নতুন অ্যালগরিদম তৈরি করেছিলেন।

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

ফাইন্ডিং ফ্যাক্টর

কোয়ান্টাম কম্পিউটারগুলি তথ্য প্রক্রিয়া করার অদ্ভুত উপায় থেকে তাদের শক্তি অর্জন করে। ধ্রুপদী কম্পিউটারগুলি বিট ব্যবহার করে, যার প্রতিটিকে সর্বদা 0 এবং 1 লেবেলযুক্ত দুটি অবস্থার একটিতে থাকতে হবে। কোয়ান্টাম বিট, বা "কুবিটস" অতিরিক্তভাবে তাদের 0 এবং 1 অবস্থার সংমিশ্রণে হতে পারে - সুপারপজিশন নামক একটি ঘটনা। একাধিক কিউবিটকে একটি সমষ্টিগত সুপারপজিশনে ঢোকানোও সম্ভব: একটি দুই-কুবিট সুপারপজিশনে চারটি উপাদান থাকে যা একই সাথে বিভিন্ন গণনা করতে পারে এবং কিউবিটের সংখ্যা বাড়ার সাথে সাথে এই জাতীয় উপাদানগুলির সংখ্যা দ্রুতগতিতে বৃদ্ধি পায়। এটি কোয়ান্টাম কম্পিউটারগুলিকে সমান্তরালভাবে দ্রুতগতিতে অনেকগুলি গণনা কার্যকরভাবে সম্পাদন করতে দেয়।

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

এরপর ১৯৯৪ সালে শোর পড়েন একটি কাগজ কম্পিউটার বিজ্ঞানী ড্যানিয়েল সাইমন দেখিয়েছেন কিভাবে একটি কল্পিত সমস্যা সমাধানের জন্য কোয়ান্টাম সুপারপজিশনকে কাজে লাগাতে হয়। শোর খুঁজে বের করেছেন কিভাবে সাইমনের ফলাফলকে আরও সাধারণ এবং ব্যবহারিক সমস্যায় প্রসারিত করা যায় যার নাম পিরিয়ড ফাইন্ডিং। একটি গাণিতিক ফাংশনকে পর্যায়ক্রমিক বলা হয় যখন ইনপুট বৃদ্ধির সাথে সাথে একই মানগুলির মাধ্যমে তার আউটপুট চক্র বারবার চলে; একটি একক চক্রের দৈর্ঘ্য ফাংশনের সময়কাল হিসাবে পরিচিত।

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

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

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

শোর অ্যালগরিদম ছিল কয়েকটি মূল প্রাথমিক ফলাফলের মধ্যে একটি যা কোয়ান্টাম কম্পিউটিংকে তাত্ত্বিক কম্পিউটার বিজ্ঞানের একটি অস্পষ্ট সাবফিল্ড থেকে আজকের জুগারনটে রূপান্তরিত করেছিল। কিন্তু অ্যালগরিদম অনুশীলন করা একটি কঠিন কাজ, কারণ কোয়ান্টাম কম্পিউটারগুলি ভুলের জন্য কুখ্যাতভাবে সংবেদনশীল: তাদের গণনা সম্পাদনের জন্য প্রয়োজনীয় কিউবিটগুলি ছাড়াও, তাদের আরও অনেককে করতে হবে অতিরিক্ত কাজ তাদের ব্যর্থ হওয়া থেকে রক্ষা করার জন্য। ক সাম্প্রতিক কাগজ Ekerå এবং Google গবেষক দ্বারা ক্রেগ গডনি অনুমান করে যে Shor-এর অ্যালগরিদম ব্যবহার করে একটি নিরাপত্তা-মান 2,048-বিট নম্বর (প্রায় 600 ডিজিট দীর্ঘ) ফ্যাক্টর করার জন্য 20 মিলিয়ন কিউবিট সহ একটি কোয়ান্টাম কম্পিউটারের প্রয়োজন হবে। আজকের অত্যাধুনিক মেশিনের সংখ্যা অন্তত কয়েকশ।

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

যদি তাই হয়, রেগেভ বলেছিলেন, "আমাদের যত তাড়াতাড়ি সম্ভব জানা উচিত, খুব দেরি হওয়ার আগে।"

গাছে হারিয়ে গেছে

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

"যদি এটি একটি শত-মাত্রিক বন হয়, তবে এটি দ্বিমাত্রিক বনের চেয়ে অনেক বেশি জটিল," বলেন গ্রেগ কুপারবার্গ, ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের একজন গণিতবিদ, ডেভিস।

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

কুপারবার্গ বলেন, "ওডেড জালির সাথে একেবারে উজ্জ্বল।"

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

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

অতিরিক্ত মাত্রা

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

সাদৃশ্যপূর্ণ দ্বি-মাত্রিক ফাংশন পরিবর্তে এক জোড়া সংখ্যা ব্যবহার করে, g₁ এবং g₂. এটা গুন জড়িত g₁ নিজের সাথে অনেকবার এবং তারপর বারবার দ্বারা গুণ করা g₂. এই ফাংশনের সময়কালও দ্বি-মাত্রিক — এটি সংখ্যা দ্বারা সংজ্ঞায়িত করা হয় g₁ গুণ এবং g₂ যে গুণগুলি একসাথে ফাংশনের আউটপুট পুনরাবৃত্তি করা শুরু করে। এর অনেকগুলি বিভিন্ন সমন্বয় রয়েছে g₁ এবং g₂ কৌশল করতে হবে যে multiplications.

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

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

"এটি বিশ্বের সমস্ত পার্থক্য তৈরি করে," বলেছেন বিনোদ বৈকুন্তনাথন, MIT-এর একজন ক্রিপ্টোগ্রাফার।

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

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

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

বালিতে লেখা

উন্নতি গভীর ছিল. রেগেভের অ্যালগরিদমের কোয়ান্টাম অংশে প্রাথমিক যৌক্তিক ধাপের সংখ্যা সমানুপাতিক n^1.5 যখন একটি ফ্যাক্টরিং n-বিট সংখ্যা, পরিবর্তে n² Shor এর অ্যালগরিদম হিসাবে. অ্যালগরিদম সেই কোয়ান্টাম অংশটিকে কয়েক ডজন বার পুনরাবৃত্তি করে এবং ফলাফলগুলিকে একত্রিত করে একটি উচ্চ-মাত্রিক জালি তৈরি করতে, যেখান থেকে এটি সময়কাল নির্ণয় করতে পারে এবং সংখ্যাটিকে ফ্যাক্টর করতে পারে। তাই সামগ্রিকভাবে অ্যালগরিদম দ্রুত নাও চলতে পারে, কিন্তু প্রয়োজনীয় ধাপের সংখ্যা কমিয়ে কোয়ান্টাম অংশের গতি বাড়ানোর ফলে এটিকে অনুশীলনে রাখা সহজ হতে পারে।

অবশ্যই, একটি কোয়ান্টাম অ্যালগরিদম চালাতে যে সময় লাগে তা বেশ কয়েকটি বিবেচনার মধ্যে একটি। সমানভাবে গুরুত্বপূর্ণ হল প্রয়োজনীয় qubits সংখ্যা, যা একটি সাধারণ ক্লাসিক্যাল গণনার সময় মধ্যবর্তী মান সঞ্চয় করার জন্য প্রয়োজনীয় মেমরির সাথে সাদৃশ্যপূর্ণ। Shor-এর অ্যালগরিদম একটি ফ্যাক্টর করার জন্য প্রয়োজনীয় qubits সংখ্যা n-বিট সংখ্যা সমানুপাতিক n, যদিও রেগেভের অ্যালগরিদম এর আসল আকারে এর সমানুপাতিক সংখ্যক কিউবিট প্রয়োজন n^1.5 - 2,048-বিট সংখ্যার জন্য একটি বড় পার্থক্য।

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

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

কিন্তু রেগেভের কাগজ গল্পের শেষ নয়। দুই সপ্তাহ আগে, বৈকুন্তনাথন এবং তার স্নাতক ছাত্র সিয়ুন রাগভান অ্যালগরিদমের মেমরি ব্যবহার কমানোর একটি উপায় খুঁজে পান। তাদের বৈকল্পিক রেগেভের অ্যালগরিদম, শোর আসল অ্যালগরিদমের মতো, আনুপাতিক সংখ্যক কিউবিট প্রয়োজন n বরং n^1.5. Ekerå একটি ইমেলে লিখেছেন যে কাজটি "আমাদেরকে একটি বাস্তবায়নের অনেক কাছাকাছি নিয়ে আসে যা অনুশীলনে আরও দক্ষ হবে।"

রেগেভের নতুন অ্যালগরিদমের বিস্তৃত পাঠ, ফ্যাক্টরিংয়ের প্রভাবের বাইরে, কোয়ান্টাম কম্পিউটিং গবেষকদের সর্বদা বিস্ময়ের জন্য উন্মুক্ত থাকা উচিত, এমনকি কয়েক দশক ধরে অধ্যয়ন করা সমস্যাগুলিতেও।

"আমার অ্যালগরিদমের এই রূপটি 30 বছর ধরে অনাবিষ্কৃত ছিল এবং নীল থেকে বেরিয়ে এসেছিল," শোর বলেছিলেন। "এখনও সম্ভবত অন্যান্য অনেক কোয়ান্টাম অ্যালগরিদম পাওয়া যাবে।"

সম্পাদকের দ্রষ্টব্য: Oded Regev থেকে তহবিল পায় সিমন্স ফাউন্ডেশন, যা এই সম্পাদকীয় স্বাধীন পত্রিকাকে অর্থায়ন করে। সিমন্স ফাউন্ডেশন ফান্ডিং সিদ্ধান্ত আমাদের কভারেজের উপর কোন প্রভাব ফেলে না। আরো বিস্তারিত হল এখানে পাওয়া.

কোয়ান্টা আমাদের শ্রোতাদের আরও ভালভাবে পরিবেশন করার জন্য সমীক্ষার একটি সিরিজ পরিচালনা করছে। আমাদের নিন কম্পিউটার বিজ্ঞান পাঠক জরিপ এবং আপনি বিনামূল্যে জিততে প্রবেশ করা হবে কোয়ান্টা বণিক।