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

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

महत्त्व

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

आगे पढ़ें

• शोर के अल्गोरिद्म का सरल शब्दों में स्पष्टीकरण – स्कॉट आरोनसन के ब्लॉग पर