शोर का अल्गोरिद्म

मुक्त ज्ञानकोश विकिपीडिया से
नेविगेशन पर जाएँ खोज पर जाएँ

शोर का अल्गोरिद्म पूर्णांकों के गुणनखण्ड के लिए एक क्वांटम अल्गोरिद्म (क्वांटम कंप्यूटर पर चलने वाला अल्गोरिद्म) है जो पोलीनोमिअल टाइम में उत्तर दे देता है[१][२] (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम में उत्तर देने वाले अल्गोरिद्मों को तेज माना जाता है[३][४][५])। इसके विपरीत, गैर-क्वांटम कंप्यूटर पर पोलीनोमिअल टाइम में पूर्णांकों का गुणनखण्ड करने के लिए कोई भी अल्गोरिद्म ज्ञात नहीं है।[२]

महत्त्व

स्ट्रोंग चर्च ट्यूरिंग थीसिस (Strong Church Turing thesis) एक दार्शनिक तर्क है जो कहता है कि - अगर किसी कम्प्यूटेशनल प्रॉब्लम के लिए किसी कम्प्यूटर (आज के या भविष्य के) पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म बन सकता है, तो उस प्रॉब्लम के लिए एक क्लासिकल कम्प्यूटर (अर्थात गैर-क्वांटम कम्प्यूटर) पर भी पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म जरूर होगा; और अगर किसी प्रॉब्लम के लिए एक क्लासिकल कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म नहीं बन सकता है, तो उस प्रॉब्लम के लिए किसी भी कम्प्यूटर (आज के या भविष्य के) पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म भी नहीं बन सकता है।[६] चूंकि पूर्णांकों के गुणनखण्ड के लिए क्वांटम कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म ज्ञात है, तो स्ट्रोंग चर्च ट्यूरिंग थीसिस के अनुसार पूर्णांकों के गुणनखण्ड के लिए एक गैर-क्वांटम कम्प्यूटर पर भी पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म जरूर होगा। पर, अगर कोई ये साबित कर देता है कि पूर्णांकों के गुणनखण्ड के लिए एक गैर-क्वांटम कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म नहीं बन सकता है, तो इसका अर्थ होगा कि स्ट्रोंग चर्च ट्यूरिंग थीसिस गलत है।[७]

आगे पढ़ें

सन्दर्भ

  1. साँचा:harvtxt
  2. साँचा:harvtxt
  3. साँचा:harvtxt
  4. स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
  5. स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
  6. साँचा:harvtxt
  7. साँचा:harvtxt


ग्रन्थ सूची

साँचा:refbegin

  • स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।