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

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

महत्त्व

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

आगे पढ़ें

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

सन्दर्भ

↑ 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. (1994). Computational complexity (अंग्रेज़ी में) (Reprinted with corr., [Nachdr.] संस्करण). Reading, Mass. [u.a.]: Addison-Wesley. पपृ॰ 6. आई॰ऍस॰बी॰ऍन॰ 0-201-53082-1. 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 (2009). "Polynomial time". Introduction to algorithms (अंग्रेज़ी में) (3rd ed. संस्करण). Cambridge, Massachusetts: MIT Press. पपृ॰ 1053-1054. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.सीएस1 रखरखाव: फालतू पाठ (link)
↑ 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 (2009). Computational Complexity A Modern Approach (अंग्रेज़ी में). Leiden: Cambridge University Press. पपृ॰ 221-222. आई॰ऍस॰बी॰ऍन॰ 978-0-511-53381-5.

[arora_barak_shor_poly_intro-1] 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_shor-2] अ ^आ 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_polynomial-3] 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-4] Papadimitriou, Christos H. (1994). Computational complexity (अंग्रेज़ी में) (Reprinted with corr., [Nachdr.] संस्करण). Reading, Mass. [u.a.]: Addison-Wesley. पपृ॰ 6. आई॰ऍस॰बी॰ऍन॰ 0-201-53082-1. 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.

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "Polynomial time". Introduction to algorithms (अंग्रेज़ी में) (3rd ed. संस्करण). Cambridge, Massachusetts: MIT Press. पपृ॰ 1053-1054. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.सीएस1 रखरखाव: फालतू पाठ (link)

[arora_barak_church_turing-6] 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_church_turing_violate-7] 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.")

[1]

[2]

[3]

[4]

[5]

[6]

[7]