1994 में, एक गणितज्ञ ने यह पता लगाया कि क्वांटम कंप्यूटर को कुछ ऐसा कैसे बनाया जाए जो कोई साधारण शास्त्रीय कंप्यूटर नहीं कर सकता। काम से पता चला कि, सिद्धांत रूप में, क्वांटम यांत्रिकी के नियमों पर आधारित एक मशीन बड़ी संख्या को अपने प्रमुख कारकों में कुशलता से तोड़ सकती है - एक शास्त्रीय कंप्यूटर के लिए एक कार्य इतना कठिन है कि यह आज की अधिकांश इंटरनेट सुरक्षा के लिए आधार बनाता है।
इसके बाद आशावाद की लहर दौड़ गई। शायद, शोधकर्ताओं ने सोचा, हम क्वांटम एल्गोरिदम का आविष्कार करने में सक्षम होंगे जो विभिन्न समस्याओं की एक विशाल श्रृंखला को हल कर सकते हैं।
लेकिन प्रगति ठप हो गई। "यह एक बमर प्रक्षेपवक्र का एक सा रहा है," ने कहा रयान ओ'डोनेल कार्नेगी मेलन विश्वविद्यालय के। "लोग इस तरह थे, 'यह आश्चर्यजनक है, मुझे यकीन है कि हम सभी प्रकार के अन्य अद्भुत एल्गोरिदम प्राप्त करने जा रहे हैं।" नहीं।" वैज्ञानिकों ने एक मानक सेट के भीतर से केवल एकल, संकीर्ण वर्ग की समस्याओं के लिए नाटकीय गति की खोज की एनपी . कहा जाता है, जिसका अर्थ है कि उनके पास कुशलता से सत्यापन योग्य समाधान थे - जैसे कि फैक्टरिंग।
करीब तीन दशक तक ऐसा ही रहा। फिर अप्रैल में, शोधकर्ताओं आविष्कार एक मौलिक रूप से नई तरह की समस्या है कि एक क्वांटम कंप्यूटर शास्त्रीय की तुलना में तेजी से तेजी से हल करने में सक्षम होना चाहिए। इसमें एक जटिल गणितीय प्रक्रिया के लिए इनपुट की गणना करना शामिल है, जो पूरी तरह से इसके अव्यवस्थित आउटपुट पर आधारित है। समस्या अकेले खड़ी है या कई अन्य लोगों की एक नई सीमा में पहली है यह अभी तक निर्धारित नहीं किया गया है।
"उत्साह की भावना है," ने कहा विनोद वैकुंठनाथनमैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में कंप्यूटर वैज्ञानिक। "बहुत से लोग सोच रहे हैं कि वहां और क्या है।"
कंप्यूटर वैज्ञानिक यह समझने की कोशिश करते हैं कि क्वांटम कंप्यूटर उनका प्रतिनिधित्व करने वाले गणितीय मॉडल का अध्ययन करके क्या बेहतर करते हैं। अक्सर, वे एक क्वांटम या शास्त्रीय कंप्यूटर के एक मॉडल की कल्पना करते हैं जिसे एक आदर्श गणना मशीन के साथ जोड़ा जाता है जिसे ऑरैकल कहा जाता है। ओरेकल सरल गणितीय कार्यों या कंप्यूटर प्रोग्राम की तरह हैं, एक इनपुट लेते हैं और एक पूर्व निर्धारित आउटपुट को थूकते हैं। उनके पास एक यादृच्छिक व्यवहार हो सकता है, यदि इनपुट एक निश्चित यादृच्छिक सीमा (कहते हैं, 12 से 67) के भीतर आता है, तो "हां" का उत्पादन होता है और यदि ऐसा नहीं होता है तो "नहीं"। या वे आवधिक हो सकते हैं, ताकि 1 से 10 के बीच का इनपुट "हां," 11 से 20 के बीच "नहीं", 21 से 30 के बीच फिर से "हां" हो, और इसी तरह।
मान लीजिए कि आपके पास इनमें से एक आवधिक दैवज्ञ है और आप अवधि नहीं जानते हैं। आप बस इतना कर सकते हैं कि इसे नंबर फीड करें और देखें कि यह क्या आउटपुट करता है। उन बाधाओं के साथ, कंप्यूटर कितनी तेजी से अवधि का पता लगा सकता है? 1993 में, मॉन्ट्रियल विश्वविद्यालय में डैनियल साइमन ने पाया कि एक क्वांटम एल्गोरिथ्म किसी भी शास्त्रीय एल्गोरिथ्म की तुलना में तेजी से संबंधित समस्या के उत्तर की गणना कर सकता है।
परिणाम ने साइमन को पहले संकेतों में से एक को निर्धारित करने में सक्षम बनाया जहां क्वांटम कंप्यूटरों के लिए नाटकीय श्रेष्ठता की उम्मीद की जा सकती है। लेकिन जब उन्होंने एक प्रमुख सम्मेलन में अपना पेपर प्रस्तुत किया, तो इसे अस्वीकार कर दिया गया। हालाँकि, अखबार ने सम्मेलन की कार्यक्रम समिति के एक कनिष्ठ सदस्य को दिलचस्पी दी - पीटर शोर, जो उस समय न्यू जर्सी में बेल लेबोरेटरीज में थे। शोर ने पाया कि यदि वह एक दैवज्ञ की अवधि की गणना करने के लिए साइमन के एल्गोरिथ्म को अनुकूलित कर सकता है। तब उन्होंने महसूस किया कि वह एक बार फिर से एल्गोरिदम को अनुकूलित कर सकते हैं, एक समीकरण को हल करने के लिए जो एक आवधिक ओरेकल के समान व्यवहार करता है: वह समीकरण जो फैक्टरिंग का वर्णन करता है, जो आवधिक है।
शोर का परिणाम ऐतिहासिक था। उन्होंने जो क्वांटम एल्गोरिथम खोजा, वह उनके घटक प्रमुख कारकों में विशाल संख्याओं को तेजी से कम कर सकता है, कुछ ऐसा जो कोई ज्ञात शास्त्रीय एल्गोरिथ्म नहीं कर सकता। इसके बाद के वर्षों में, शोधकर्ताओं ने अन्य कुशल क्वांटम एल्गोरिदम की खोज की। उनमें से कुछ, जैसे शोर का एल्गोरिदम, ने भी घातीय लाभ प्रदान किया, लेकिन कोई भी किसी भी एनपी समस्या पर नाटकीय क्वांटम लाभ साबित नहीं कर सका जो आवधिक नहीं था।
प्रगति की इस कमी ने दो कंप्यूटर वैज्ञानिकों का नेतृत्व किया, स्कॉट आरोनसन टेक्सास विश्वविद्यालय, ऑस्टिन, और एंड्रीस अम्बैनिस लातविया विश्वविद्यालय, एक अवलोकन करने के लिए। क्वांटम लाभ के प्रमाण हमेशा उन ओरेकलों पर निर्भर लगते थे जिनकी किसी प्रकार की गैर-यादृच्छिक संरचना थी, जैसे कि आवधिकता। 2009 में, वे अनुमान लगाया कि यादृच्छिक, या असंरचित एनपी समस्याओं पर नाटकीय गति नहीं हो सकती। अपवाद किसी को नहीं मिला।
उनके अनुमानों ने क्वांटम कंप्यूटरों की शक्तियों को सीमित कर दिया। लेकिन इसने केवल इतना कहा कि एक विशिष्ट प्रकार की असंरचित एनपी समस्या के लिए कोई नाटकीय गति नहीं थी - जिनके पास हां या ना में उत्तर हैं। यदि किसी समस्या में अधिक विशिष्ट, मात्रात्मक उत्तरों का पता लगाना शामिल है, जिसे खोज समस्या के रूप में जाना जाता है, तो अनुमान लागू नहीं होता।
इसे ध्यान में रखते हुए, शोधकर्ताओं ताकाशी यामाकावा एनटीटी सामाजिक सूचना विज्ञान प्रयोगशालाओं और मार्क झंड्री एनटीटी रिसर्च और प्रिंसटन यूनिवर्सिटी ने एक विशिष्ट खोज समस्या के साथ प्रयोग करने का फैसला किया, जिसे 2005 में शुरू किया गया था उबेद रेगेव.
वेदर वेन्स के एक सेट की कल्पना करें जो सभी एक ही दिशा में इशारा कर रहे हैं। उनमें से प्रत्येक को एक मापा झटका दें, फिर एक तेज़ हवा को उनकी दिशा को प्रभावित करने दें। रेगेव अपने अंतिम निर्देशों के आधार पर निर्धारित करना चाहते थे, जहां वे सभी शुरू में इंगित करते थे। इस तरह की समस्याओं को "त्रुटियों के साथ सीखना" कहा जाने लगा, क्योंकि शॉव और विंड मूल दिशा में यादृच्छिक त्रुटि के स्रोत की तरह काम करते हैं। इस बात के प्रमाण हैं कि शास्त्रीय और क्वांटम एल्गोरिदम दोनों के लिए इसे हल करना कठिन है।
यामाकावा और ज़ांद्री ने सेटअप में बदलाव किया। उन्होंने उन शुरुआती झटके की ताकत को संशोधित किया, जिससे उन्हें और अधिक अनुमान लगाया जा सके। उन्होंने हवा को एक यादृच्छिक दैवज्ञ द्वारा निर्धारित किया ताकि यह कुछ मामलों में और भी अधिक यादृच्छिक हो लेकिन दूसरों में पूरी तरह से निष्क्रिय हो।
इन संशोधनों के साथ, शोधकर्ताओं ने पाया कि क्वांटम एल्गोरिथम कुशलतापूर्वक प्रारंभिक दिशा का पता लगा सकता है। उन्होंने यह भी साबित किया कि किसी भी शास्त्रीय एल्गोरिथ्म को एक घातीय कारक से धीमा होना चाहिए। शोर की तरह, उन्होंने तब समस्या के वास्तविक-विश्व संस्करण को हल करने के लिए अपने एल्गोरिथ्म को अनुकूलित किया, जो कि वास्तविक गणितीय समीकरण के साथ ऑरेकल को बदल देता है।
कंप्यूटर वैज्ञानिक अभी भी समस्या को समझने और उस पर निर्माण करने के लिए काम कर रहे हैं। वैकुंठनाथन इसकी तुलना एक अलग से करता है जो डेटा संपीड़न करते समय उत्पन्न होता है: जब जानकारी को निचोड़ा जा रहा है, तो दो बिट्स गलती से एक ही स्थान पर निचोड़ा जा सकता है, उन्हें अधिलेखित कर सकता है। उन टकरावों की पहले से भविष्यवाणी करने की समस्या, ताकि आप उनसे बच सकें, कुछ समानता है। "यह समस्याओं का एक वर्ग है जो मूल रूप से इस तरह दिखता है," उन्होंने कहा। "शायद इन समस्याओं को क्वांटम रूप से हल किया जा सकता है।"
ऐसी उम्मीदें थीं कि नई जैसी असंरचित समस्या क्वांटम कंप्यूटरों के आज के नवोदित संस्करणों पर भी हल हो सकती है, जिससे उनका परीक्षण करने का एक साधन उपलब्ध हो सके। सोच यह थी कि असंरचित समस्याएं कार्यक्रम के लिए कम संसाधन ले सकती हैं, या शोर के प्रति कम संवेदनशील हो सकती हैं, क्योंकि वे पहले से ही यादृच्छिक हैं। लेकिन अभी तक, मौजूदा क्वांटम कंप्यूटरों को हल करने के लिए नई समस्या अभी भी बहुत उन्नत है। "यह एक अजीब समस्या है। मैंने इसे परिभाषित करने के बारे में नहीं सोचा था," आरोनसन ने कहा। "लेकिन पूर्वव्यापी में, इसमें कुछ बहुत अच्छी विशेषताएं हैं।"
परिणाम एक असंरचित एनपी समस्या पर नाटकीय क्वांटम लाभ का पहला उदाहरण प्रदान करता है। क्या कई अन्य समस्याएं हो सकती हैं जो क्वांटम दुनिया को व्यावहारिक रूप से अघुलनशील से हल करने योग्य में बदल देती हैं? ऐसा सोचने का अब और कारण है।
"यह कुछ हद तक हमारे विश्वासों को उलट देता है कि क्वांटम कंप्यूटर किस प्रकार की समस्याओं में अच्छे हो सकते हैं," ओ'डॉनेल ने कहा।
