क्वाण्टम कम्प्यूटर

प्रमात्रा संगणक (quantum computer) ऐसा संगणक है जो अपने कार्य के लिये अध्यारोपण एवं प्रमात्रा उलझाव (entanglement) जैसी प्रमात्रा यांत्रिक परिघटनाओं (quantum mechanical phenomena) का सीधे उपयोग करता है। प्रमात्रा अभिकलन (quantum computation) का मूल आधार यह है कि प्रमात्रा गुणों का उपयोग आंकड़ों के निरूपण एवं उन पर संक्रियाएँ करने के लिये किया जा सकता है।

प्रमात्रा संगणक ट्रांसिस्टर पर आधारित परंपरागत संगणकों से भिन्न होते हैं। इसका सैद्धान्तिक प्रादर्श है- प्रमात्रा टूरिंग मशीन, जिसे सार्वत्रिक प्रमात्रा संगणक भी कहा जाता है। प्रमात्रा संगणकों की सैद्धान्तिक समानता, नॉन-डिटर्मिनिस्टिक तथा प्रायिकता आधारित ऑटोमैटन के साथ है। ऐसी समानता का उदाहरण है- एक से ज्यादा अवस्थाओं में एक साथ रह पाने की क्षमता।

यद्यपि प्रमात्रा अभिकलन अभी अपनी शैशवावस्था में ही है, परन्तु ऐसे प्रयोग किये जा चुके हैं, जिनमें बहुत मामूली संख्या में क्युबिटों (प्रमात्रा बिटों) पर प्रमात्रा अभिकलन की संक्रियाएँ संपन्न की गयी हैं। प्रायोगिक तथा सैद्धान्तिक दोनों प्रकार के अनुसंधान जारी हैं। बहुत सी राष्ट्रीय सरकारें तथा सैन्य वित्तपोषक एजेन्सियाँ भी प्रमात्रा अभिकलन पर अनुसंधान को संबल देती हैं, ताकि नागरिक तथा राष्ट्रीय सुरक्षा उद्देश्यों से (जैसे- कूटविश्लेषण (क्रिप्टैनालिसिस्)) प्रमात्रा संगणक का विकास किया जा सके।^[1]

सैद्धांतिक कम्प्यूटर विज्ञान में महत्त्व

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

सन्दर्भ

↑ Quantum Information Science and Technology Roadmap Archived 2011-08-10 at the वेबैक मशीन for a sense of where the research is heading.
↑ ^अ ^आ 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.")
↑ 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. 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.")
↑ 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.")

बाहरी कड़ियाँ

क्वांटम कम्प्यूटर (जागरण जोश)
Quantum computer simulates molecular reality
दर्शनशास्त्र का स्टैनफोर्ड ज्ञानकोष: "Quantum Computing" by Amit Hagar.
Quantiki - Wiki and portal with free-content related to quantum information science.
jQuantum: Java quantum circuit simulator
QCAD: Quantum circuit emulator
C++ Quantum Library
Haskell Library for Quantum computations
Video Lectures by David Deutsch
Lectures at the Institut Henri Poincaré (slides and videos)

[1] Quantum Information Science and Technology Roadmap Archived 2011-08-10 at the वेबैक मशीन for a sense of where the research is heading.

[arora_barak_shor_poly_intro-2] अ ^आ 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.")

[arora_barak_shor-3] 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-4] 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-5] 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.

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]