क्वांटम कंप्यूटर अभी तक 21 का अभाज्य गुणनखंडन क्यों नहीं कर पाए हैं

 (algassert.com)
1 पॉइंट द्वारा GN⁺ 2025-09-01 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 2001 में क्वांटम कंप्यूटर से 15 का अभाज्य गुणनखंडन करने के बाद भी प्रगति न होने जैसी दिखने वाली स्थिति की व्याख्या
  • 21 का अभाज्य गुणनखंडन करने वाले सर्किट को 15 के गुणनखंडन की तुलना में 100 गुना अधिक entangling gates की आवश्यकता होती है
  • यह अंतर conditional modular multiplication की जटिलता और 15 पर ही लागू होने वाले विशेष optimization की वजह से है
  • quantum error correction और हार्डवेयर सीमाएँ भी 21 के गुणनखंडन तक पहुँचने की बाधा को और ऊँचा करती हैं
  • अब तक रिपोर्ट किए गए 21 के गुणनखंडन के अधिकांश मामलों में वास्तविक multiplication किए बिना ट्रिक का इस्तेमाल किया गया है

क्वांटम कंप्यूटर अभी तक 21 का अभाज्य गुणनखंडन क्यों नहीं कर पाए हैं

15 के गुणनखंडन के बाद 21 का गुणनखंडन सामने क्यों नहीं आया

  • 2001 में क्वांटम कंप्यूटर से 15 का अभाज्य गुणनखंडन करने का एक प्रयोग हुआ था
  • 2025 आ चुका है, लेकिन अभी तक 21 के गुणनखंडन का कोई सफल उदाहरण नहीं है
  • इसी आधार पर यह धारणा फैल गई है कि क्वांटम कंप्यूटर में कोई प्रगति ही नहीं हुई
  • लेकिन वास्तव में 15 और 21 के गुणनखंडन सर्किट की तुलना करने पर इससे भी अधिक चौंकाने वाली वजह सामने आती है

15 के गुणनखंडन सर्किट और 21 के गुणनखंडन सर्किट के संरचनात्मक अंतर

  • 15 के गुणनखंडन वाला सर्किट केवल 21 quantum gates (21 entangling gates) से लागू हो जाता है
    • 6 two-qubit entangling gates (CNOT और CPHASE gates) और
    • 2 Toffoli gates (जिनमें से हर एक 6 entangling gates में विभाजित होता है), कुल 21 entangling gates
  • 21 के गुणनखंडन वाले सर्किट के लिए 191 CNOT, 369 Toffoli, कुल 2405 entangling gates चाहिए
    • 15 के गुणनखंडन की तुलना में 115 गुना अधिक entangling gate भार उत्पन्न होता है
    • सर्किट का आकार केवल 25% या 2 गुना नहीं बढ़ता, बल्कि 100 गुना से भी अधिक महँगा हो जाता है
  • सर्किट optimization के स्तर को ध्यान में रखें तो 500 गुना का अंतर भी व्यवहारिक रूप से संभव लगता है

इतना बड़ा अंतर क्यों पैदा होता है

  • क्वांटम गुणनखंडन सर्किट (Shor's algorithm) में सबसे प्रमुख लागत conditional modular multiplication की होती है
    • n-bit संख्या N के लिए accumulator पर कई बार conditionally modular multiplication करना पड़ता है
    • यहाँ 15 के मामले में 8 conditional multiplications में से 6 को 1 से multiplication (यानी कोई काम नहीं) के रूप में संभाला जा सकता है
      • पहला multiplication इसलिए लगभग मुफ़्त है क्योंकि input 1 होता है
      • दूसरा (बाकी बचा एक) भी दो CSWAP से सस्ते में किया जा सकता है
      • नतीजतन वास्तव में केवल 2 के लिए ही लागत चुकानी पड़ती है
      • यह संरचना केवल 15 के लिए लागू होने वाला एक विशेष गुण है, जहाँ 1 के करीब multiplication कई बार आते हैं, इसलिए भार बहुत कम हो जाता है
  • लेकिन 21 के मामले में कोई भी multiplication 1 नहीं है और मान अलग-अलग हैं, इसलिए हर multiplication की लागत लगती है
    • 8 के 8 multiplication महँगे पड़ते हैं; बढ़ोतरी केवल 4~5 गुना नहीं बल्कि 20~100 गुना तक जाती है
    • 4 या 16 से multiplication जैसी क्रियाएँ CSWAP (conditional swap) से लागू नहीं की जा सकतीं
    • हर multiplication की जटिलता अलग होती है और optimization आसान नहीं है

हार्डवेयर और error correction की वास्तविक सीमाएँ

  • पहले (2001) 15 का गुणनखंडन NMR quantum computer पर लागू किया गया था, जिसकी scaling में कई सीमाएँ थीं
  • इससे आगे बढ़ने पर quantum error correction की ज़रूरत भी बढ़ती है
    • यदि gate की संख्या 100 गुना बढ़े तो error rate 100 गुना कम होना चाहिए
    • व्यवहार में qubit की संख्या भी 100 गुना बढ़ानी पड़ सकती है, इसलिए कुल लागत 10,000 गुना तक जा सकती है

गुणनखंडन के प्रयासों पर विवाद और गलत नतीजे

  • हाल की कुछ papers में क्वांटम कंप्यूटर से 21 का गुणनखंडन करने का दावा किया गया है, लेकिन
    • वास्तव में उनमें algorithm के multiplication चरण को छोड़ दिया गया, या परिणाम पहले से जानकर सर्किट को सरल बनाया गया
    • जब तक असली multiplication operation न किया जाए, उसे गुणनखंडन नहीं कहा जा सकता
    • यह "period finding" और गुणनखंडन के मूलभूत अंतर को नज़रअंदाज़ करने वाला भ्रामक परिणाम है
  • कुछ papers में खुले तौर पर ट्रिक का इस्तेमाल किया गया, और उन पर व्यंग्य papers भी आए
    • गुणनखंडन champion record की नकल वाले प्रयोगों सहित कई व्यंग्य papers मौजूद हैं
    • Variational factoring जैसे benchmark बार-बार सामने आते हैं, जिनके पास scale-up का कोई ठोस आधार नहीं है

क्वांटम कंप्यूटर की सही प्रगति का संकेतक क्या है

  • इस समय गुणनखंडन क्वांटम कंप्यूटर प्रगति का मुख्य benchmark नहीं है
    • 15 से आगे लागत विस्फोटक रूप से बढ़ती है, इसलिए व्यवहारिक सत्यापन कठिन हो जाता है
  • इसके बजाय quantum error correction का अपनाया जाना (जैसे surface code में सुधार) या
    • scaling समस्या हल करने वाली hardware architecture में बदलाव (जैसे neutral atoms का निरंतर प्रतिस्थापन)
    • वास्तविक प्रगति दिखाने के अधिक महत्वपूर्ण संकेतक हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-09-01
Hacker News राय

  • इसकी वजह यह है कि अब तक इससे छोटे numbers को भी वास्तव में factor नहीं किया गया था। अगर प्रोग्राम की compilation process ऐसी हो कि उसे चलने के लिए जवाब पहले से पता होना चाहिए, तो वह असली factorization नहीं है, बल्कि सिर्फ़ "3 को print करना" है

  • यह जानने की जिज्ञासा है कि cryptographically meaningful number को वास्तव में factor करने के लिए कितने quantum gate चाहिए होंगे। यह भी जानना है कि क्या इस सदी के भीतर काम का quantum computer आने की कोई व्यावहारिक राह है

    • 2048-bit RSA factorization के लिए लगभग 7 billion Toffoli gate की ज़रूरत पड़ती है, इसका उदाहरण paper के Table 5 के estimate से लिया जा सकता है(paper link). दसियों अरब operations तक पहुँचने का तरीका quantum error correction है, और paper के अनुसार distance 25 surface code काफ़ी है। इस स्थिति में 1,400 logical qubit से बढ़ाकर लगभग 1 million वास्तविक noisy qubit तक जाना पड़ता है। PQCrypto में Samuel Jacques की talk भी देखने लायक है(YouTube). मैं इस blog और संबंधित paper का author हूँ
    • इस सवाल के कठिन होने की दो वजह हैं। पहली, 'cryptographically meaningful' की कोई साफ़ सीमा नहीं खींची जा सकती। दूसरी, जो QC वास्तव में यह computation कर सके, उसकी architecture अभी स्पष्ट रूप से ज्ञात नहीं है। यह कुछ वैसा है जैसे 1985 में neural network बनाने के लिए कितने पारंपरिक logic gate चाहिए होंगे, इसका अनुमान लगाना। फिर भी यह लगभग तय लगता है कि लाखों से अधिक gate चाहिए होंगे। तीसरी बात, quantum error correction में lower raw qubit error rate और भरोसेमंद error-corrected virtual qubit बनाने के लिए आवश्यक gate count के बीच trade-off होता है। आगे raw qubit की error rate कहाँ तक नीचे जा सकेगी, यह अभी पता नहीं। अगर quantum computer में भी पिछले 75 साल के computer development जैसी प्रगति हुई, तो अनुमान है कि 2100 के आसपास मौजूदा cryptography पूरी तरह बेअसर हो सकती है। transistor जैसी किसी एक बड़ी innovation के आने तक भविष्यवाणी करना मुश्किल है। तकनीकी प्रगति हमेशा असंभव लगती है, लेकिन जब कोई पहली बार तरीका खोज लेता है, तो तस्वीर बदल जाती है। (UNIVAC I description)
    • इस विषय पर एक हालिया tweet भी है(tweet link). आम नज़रिए से देखें तो यह राह कई बड़े materials science breakthroughs के पीछे छिपी हुई लगती है
    • RSA 4096 के लिए मोटे तौर पर 10^7 qubit और 10^-4 error rate चाहिए। पहले से ही लगभग 100 qubit के साथ उपयोगी quantum chemistry calculations संभव हैं, और post-quantum algorithms के फैलने के साथ cryptanalysis के लिए quantum computer बनाने की motivation कम हो रही है। मुझे लगता है quantum computing cryptography से असंबंधित दिशाओं में ज़्यादा तेज़ी से आगे बढ़ेगी
    • ताज़ा आंकड़ा यह है कि 1e-4 error rate पर लगभग 1 million qubit चाहिए(paper link). gate count code level पर वास्तविक computation के अनुसार अलग-अलग मापा जाता है, और 1MHz "clock" (code cycle time) के आधार पर पूरा computation लगभग एक हफ़्ता लेता है। qubit count की तुलना में computation time हासिल करना ज़्यादा कठिन metric है। quantum error correction के जादुई असर (जैसे-जैसे error rate घटती है, qubit count बहुत कम हो जाती है) की वजह से qubit quality में एक स्तर की बेहतरी से आवश्यक qubit की संख्या तेज़ी से गिरती है। दूसरी ओर, अगर computation को कई systems में बाँटना पड़े, तो स्थिति बहुत ख़राब हो जाती है

  • 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' paper काफ़ी दिलचस्प है(paper पढ़ें)

  • RSA1024 जैसे cryptographically meaningful number के factorization circuit size और उसकी feasibility में रुचि है

    • RSA1024 की cost estimate छोटे numbers (जैसे 4-bit) से simple scaling करके नहीं निकाली गई, बल्कि वास्तविक scale के अनुरूप circuit design के आधार पर निकाली गई है। यानी इस लेख में उठाई गई discontinuity वाली समस्या को पहले से ही अप्रत्यक्ष रूप से शामिल किया गया है। इसलिए इस posting का मौजूदा cost estimates पर कोई असर नहीं पड़ता
    • (संदर्भ के लिए: 21 factorization circuit का optimization बड़े numbers को factor करते समय लागू करना कठिन होगा। 15 factorization circuit की तुलना में 500x cost ज़्यादा यथार्थवादी हो सकती है। बेशक, 100x overhead भी तर्क समझाने के लिए काफ़ी है। उस circuit optimization के लिए Noah Shutty द्वारा महंगी computer search चलाने पर विशेष धन्यवाद)
    • यह विषय से थोड़ा हटकर है, लेकिन जिज्ञासा है कि क्या cryptographers को इस बात पर भरोसा है कि हाल के बहुत बड़े datacenter भी RSA1024 को factor करना व्यावहारिक रूप से असंभव मानते हैं। अभी की सबसे तेज़ algorithms भी यथार्थ समय में इसे factor नहीं कर सकतीं। लेकिन क्या इस बात पर सहमति है कि निकट भविष्य में इन algorithms में कोई क्रांतिकारी सुधार नहीं होगा, यह जानना दिलचस्प होगा

  • यह जिज्ञासा है कि क्या कभी quantum computer post-quantum RSA को target कर पाएगा(related paper). एक मत यह भी है कि सामान्य RSA operations (key generation, encryption, decryption) Shor algorithm के संदर्भ में asymmetrically advantageous हैं, इसलिए बस काफ़ी बड़ी key इस्तेमाल करनी चाहिए। इसका असर कुछ हद तक Merkle puzzle जैसा है, और एक अतिरिक्त शर्त यह है कि attacker को हमला quantum computer से ही करना होगा। मैंने पहले gigabit RSA public key भी बनाई थी(key file). format यह है: 4-byte little-endian key byte count, उसके बाद key, और key inverse (256^bytes mod में). public exponent 3 है

    • Post-Quantum RSA, djb का एक मज़ाक है, जो "क्या सिर्फ़ बड़ी key इस्तेमाल करने से काम नहीं चल जाएगा?" जैसे सवाल के जवाब में बनाया गया था। इसे इस तरह design किया गया है कि 1TB key पर एक बार encryption करने में 100 घंटे लगें। quantum computer से भी इसे तोड़ा नहीं जा सकता

  • "error corection" typo देखकर काफ़ी मज़ा आया

  • "factorization-15 की तुलना में 500x circuit cost" वाला हिस्सा समझना मुश्किल है। author ने पहले ही 115x का मामला दिया है, तो यह समझना कठिन है कि अतिरिक्त optimization कैसे और बदतर नतीजे दे सकती है

    • इसका मतलब यह है कि छोटे numbers के factorization circuit बनाने में जितना भारी optimization effort लगाया गया, वह बड़े numbers पर व्यावहारिक नहीं है। यानी सामान्यतः intuition यह है कि factor किए जाने वाले number के बड़े होने पर लगभग 500x gate वृद्धि चाहिए होगी (115x जितनी कम नहीं)
    • वास्तव में बड़े scale पर optimization का असर घट जाता है, और N=21 circuit जैसा फ़ायदा नहीं मिलेगा
    • minimal implementation अस्थिर होती है और reliability की गारंटी देना मुश्किल होता है। practical circuit development के लिए stable qubit सुनिश्चित करने पर बहुत research चाहिए, और "decoherence time" जैसे concepts भी सामने आते हैं। इसलिए qubit count का बहुत तेज़ी से बढ़ना लगभग तय है
    • 115x, (अव्यावहारिक) भारी optimization का परिणाम है

  • इस post की बात का सार क्या यह संकेत देता है कि Shor's factorization के लिए Big-O circuit requirement super-polynomial है, यह स्पष्ट नहीं है

    • लेख के अनुसार gate cost मुख्य रूप से O(n) modular multiplication operations से आती है, और हर operation को O(n^2) gate में implement किया जा सकता है। कुल मिलाकर worst case में भी यह लगभग cubic complexity लगती है

  • PQ (post-quantum) cryptography को अपनाने की वजह यह नहीं कि सबको यक़ीन है कि QC बहुत जल्द आ जाएगा। QC कब आएगा, यह तकनीकी प्रगति की रफ़्तार पर निर्भर है और अनिश्चित है। cryptography का लक्ष्य ऐसे तरीक़े खोजना है जिन्हें सैद्धांतिक रूप से भी लगभग तोड़ा न जा सके, और अगर कोई theoretical attack path मौजूद है, तो भौतिक रूप से भी संभावना मानी जाती है, इसलिए पहले से तैयारी की जाती है। ECC और RSA के लिए ऐसा theoretical path ज्ञात है, इसलिए वास्तविक hardware न होने पर भी उन्हें attackable माना जाता है। इस वजह से QC आने से पहले तैयारी करना पूरी तरह तर्कसंगत है। दूसरी ओर SHA2, AES, ChaCha आदि के लिए कोई व्यावहारिक attack path नज़र नहीं आता, इसलिए अभी तत्काल replacement plan नहीं है। encryption, QC का एकमात्र या सबसे महत्वपूर्ण application नहीं है। उम्मीद है कि physical systems, protein folding, machine learning आदि जैसे क्षेत्रों में अभी अज्ञात innovations निकल सकती हैं

    • जिज्ञासा है कि protein folding जैसे क्षेत्रों में आगे और प्रगति संभव है या नहीं (AlphaFold के बाद भी)। (संदर्भ लेख)

    • symmetric-key cryptography (AES, ChaCha, SHA-2) के मामले में quantum attack का प्रभाव लगभग key length के आधा रह जाने जैसा होता है (जैसे 3DES और 2DES के उदाहरण में)। व्यवहार में वास्तविक quantum computer की performance बराबर या समान नहीं होगी, इसलिए इसे बिल्कुल आधा मान लेना सही नहीं, लेकिन AES-256 पर जाना संभव है इसलिए समस्या नहीं है। असल फ़ोकस Key Exchange पर होना चाहिए। वजह यह है कि Key Exchange का इस्तेमाल दोनों पक्षों द्वारा secret key सीधे बताए बिना उस पर सहमति बनाने के लिए किया जाता है। अगर Quantum Computer मौजूद हो, तो पहले रिकॉर्ड की गई पुरानी conversations भी पढ़ी जा सकती हैं। signing algorithm टूट जाने पर कोई अतीत में जाकर signatures नहीं बना सकता, लेकिन Key Exchange एक बार टूट जाए तो पुरानी बातचीत भी पूरी तरह उजागर हो सकती है, इसलिए इसका सुरक्षित replacement सबसे ज़्यादा ज़रूरी है