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

शोर का अल्गोरिद्म पूर्णांकों के गुणनखण्ड के लिए एक क्वांटम अल्गोरिद्म (क्वांटम कंप्यूटर पर चलने वाला अल्गोरिद्म) है जो पोलीनोमिअल टाइम में उत्तर दे देता हैArora Barak 2009 p. 201, "As we will see in Section 10.6, there is a polynomial-time algorithm for quantum computers to factor integers"Arora Barak 2009 p. 221-222, "Theorem 10.15 Shor’s algorithm: Factoring in BQP. There is a quantum algorithm that given a number N, runs in time poly(log(N)) and outputs the prime factorization of N." (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम में उत्तर देने वाले अल्गोरिद्मों को तेज माना जाता हैArora Barak 2009 p. 25, "Now we try to make the notion of “efficient computation” precise. We equate this with polynomial running time, which means it is at most n^c for some constant c > 0."Papadimitriou Christos H. Computational complexity https://archive.org/details/computationalcom00papa 1994 Addison-Wesley Reading, Mass. [u.a.] 0-201-53082-1 6 Reprinted with corr., [Nachdr.] अंग्रेज़ी In the course of this book we shall regard such polynomial rates of growth as acceptable time requirements, as a sign that the problem has been solved satisfactorily.Cormen Thomas H. Leiserson Charles E. Rivest Ronald L. Stein Clifford Introduction to algorithms https://archive.org/details/introductiontoal00corm_805 Polynomial time 2009 MIT Press Cambridge, Massachusetts 978-0-262-03384-8 1053-1054 3rd ed. अंग्रेज़ी)। इसके विपरीत, गैर-क्वांटम कंप्यूटर पर पोलीनोमिअल टाइम में पूर्णांकों का गुणनखण्ड करने के लिए कोई भी अल्गोरिद्म ज्ञात नहीं है। महत्त्व स्ट्रोंग चर्च ट्यूरिंग थीसिस (Strong Church Turing thesis) एक दार्शनिक तर्क है जो कहता है कि - अगर किसी कम्प्यूटेशनल प्रॉब्लम के लिए किसी कम्प्यूटर (आज के या भविष्य के) पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म बन सकता है, तो उस प्रॉब्लम के लिए एक क्लासिकल कम्प्यूटर (अर्थात गैर-क्वांटम कम्प्यूटर) पर भी पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म जरूर होगा; और अगर किसी प्रॉब्लम के लिए एक क्लासिकल कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म नहीं बन सकता है, तो उस प्रॉब्लम के लिए किसी भी कम्प्यूटर (आज के या भविष्य के) पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म भी नहीं बन सकता है।Arora Barak 2009 p. 26, "The strong form of the CT thesis says that every physically realizable computation model can be simulated by a TM with polynomial overhead (in other words, t steps on the model can be simulated in t^c steps on the TM, where c is a constant that depends upon the model). If true, it implies that the class P defined by the aliens will be the same as ours." चूंकि पूर्णांकों के गुणनखण्ड के लिए क्वांटम कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म ज्ञात है, तो स्ट्रोंग चर्च ट्यूरिंग थीसिस के अनुसार पूर्णांकों के गुणनखण्ड के लिए एक गैर-क्वांटम कम्प्यूटर पर भी पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म जरूर होगा। पर, अगर कोई ये साबित कर देता है कि पूर्णांकों के गुणनखण्ड के लिए एक गैर-क्वांटम कम्प्यूटर पर पोलीनोमिअल टाइम में चलने वाला अल्गोरिद्म नहीं बन सकता है, तो इसका अर्थ होगा कि स्ट्रोंग चर्च ट्यूरिंग थीसिस गलत है।Arora Barak 2009 p. 201, "As we will see in Section 10.6, there is a polynomial-time algorithm for quantum computers to factor integers, whereas despite much effort, no such algorithm is known for deterministic or probabilistic Turing machines. If in fact there is no efficient classical algorithm to factor integers (and indeed society currently relies on this conjecture since it underlies the presumed security of cryptographic schemes such as RSA) and if quantum computers are physically realizable, then the strong Church-Turing thesis is wrong." आगे पढ़ें शोर के अल्गोरिद्म का सरल शब्दों में स्पष्टीकरण – स्कॉट आरोनसन के ब्लॉग पर ग्रन्थ सूची Sanjeev Arora Barak Boaz Computational Complexity A Modern Approach https://archive.org/details/computationalcom00aror 2009 Cambridge University Press Leiden 978-0-511-53381-5 221-222 अंग्रेज़ी श्रेणी:अल्गोरिद्म श्रेणी:कम्प्यूटर विज्ञान