⚛️ quantum physics

Faster algorithm for achieving minimal-size quantum decision diagrams

यह शोध पत्र QolDDer सिम्युलेटर में कार्यान्वित Pauli-LIMDDs के लिए एक नवीन $O(n^2)$ नॉर्मल-फॉर्म एल्गोरिदम प्रस्तुत करता है, जो मौजूदा उपकरणों की तुलना में क्रम-परिमाण (order-of-magnitude) की गति वृद्धि प्राप्त करके और इस डेटा संरचना के सैद्धांतिक रूप से सिद्ध घातांकीय लाभों को साकार करके क्वांटम सर्किट सिमुलेशन—विशेष रूप से क्लिफोर्ड (Clifford) सर्किट के लिए—को महत्वपूर्ण रूप से त्वरित करता है।

मूल लेखक: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

प्रकाशित 2026-06-24

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक बड़ी तस्वीर: एक अराजक पुस्तकालय को व्यवस्थित करना

कल्पना कीजिए कि आप एक क्वांटम कंप्यूटर का अनुकरण (simulate) करने की कोशिश कर रहे हैं। ऐसा करने के लिए, आपको कई सूक्ष्म कणों (qubits) की स्थिति को ट्रैक करना होगा। जैसे-जैसे आप अधिक कण जोड़ते हैं, आपको जितनी जानकारी स्टोर करने की आवश्यकता होती है, वह विस्फोट की तरह बढ़ती जाती है। यह एक ऐसी लाइब्रेरी में हर एक किताब को लिखने की कोशिश करने जैसा है जो हर बार एक नई शेल्फ जोड़ने पर दोगुनी हो जाती है। अंततः, लाइब्रेरी इतनी विशाल हो जाती है कि कोई भी कंप्यूटर उसे संभाल नहीं सकता।

इसे हल करने के लिए, वैज्ञानिक एक डेटा स्ट्रक्चर का उपयोग करते हैं जिसे डिसीजन डायग्राम (DD) कहा जाता है। एक DD को एक विशाल सूची के रूप में नहीं, बल्कि एक फ्लोचार्ट या एक पेड़ (tree) के रूप में सोचें। हर एक विवरण को लिखने के बजाय, फ्लोचार्ट शाखाओं में विभाजित होता है। यदि दो शाखाएं बिल्कुल एक ही परिणाम की ओर ले जाती हैं, तो आप उन्हें दो बार नहीं लिखते; आप बस एक ही शाखा खींचते हैं और दोनों जगहों से उसे एक ही बिंदु से जोड़ देते हैं। यह "विलय" (merging) स्थान की भारी बचत करता है।

समस्या: "अव्यवस्थित" फ्लोचार्ट

इन फ्लोचार्ट्स के विभिन्न प्रकार हैं। यह पेपर एक बहुत ही शक्तिशाली प्रकार पर ध्यान केंद्रित करता है जिसे LIMDD (लोकल इनवर्टिबल मैप डिसीजन डायग्राम) कहा जाता है।

मानक फ्लोचार्ट (QMDDs): ये एक सख्त लाइब्रेरियन की तरह हैं जो केवल तभी दो शाखाओं को मिलाते हैं जब वे बिल्कुल एक जैसी हों।
LIMDDs: ये एक प्रतिभाशाली लाइब्रेरियन की तरह हैं जो शाखाओं को तब भी मिला सकते हैं जब वे अलग दिखती हों, जब तक कि वे एक विशिष्ट गणितीय "अनुवाद" (जैसे कि पाउली गेट) द्वारा संबंधित हों। यह LIMDDs को मानक वाले की तुलना में बहुत छोटा और तेज़ बनाता है।

हालांकि, एक पेंच है। विलय का लाभ उठाने के लिए, फ्लोचार्ट को एक "कैनोनिकल फॉर्म" (canonical form) में होना चाहिए। इसका मतलब है कि लाइब्रेरियन को नियमों का एक सख्त सेट पालन करना होगा ताकि यह सुनिश्चित हो सके कि यदि दो चीजें मर्ज की जा सकती हैं, तो वे वास्तव में मर्ज की जाएं।

पेपर बताता है कि पिछले LIMDD सिम्युलेटर बनाने के प्रयास उन लाइब्रेरियन की तरह थे जो नियम तो जानते थे लेकिन उन्हें पूरी तरह से पालन करने के लिए बहुत धीमे या आलसी थे।

वे धीमे थे: दो शाखाओं को मर्ज करने के लिए जांचने का एल्गोरिदम एक जटिल पहेली को सुलझाने की कोशिश करने जैसा था जब भी आप एक किताब जोड़ते थे। इसमें बहुत समय लगता था ( $O(n^3)$ )।
वे अव्यवस्थित थे: क्योंकि नियमों का पूरी तरह से पालन नहीं किया गया था, फ्लोचार्ट में डुप्लिकेट शाखाएं रह गईं जिन्हें मर्ज किया जाना चाहिए था। इसने सिमुलेशन को धीमा और फूला हुआ बना दिया, जिससे सैद्धांतिक गति का लाभ खो गया।

समाधान: एक तेज़ सॉर्टिंग एल्गोरिदम

इस पेपर के लेखकों, जूल सैंडर्स और उनकी टीम ने "अव्यवस्थित फ्लोचार्ट" की समस्या को ठीक करने के लिए एक नया, तेज़ एल्गोरिदम बनाया है।

उपमा (Analogy):
कल्पना कीजिए कि आपके पास मोजों का एक ढेर है। आप जोड़े (pairs) खोजना चाहते हैं।

पुराना तरीका: आप एक मोजा उठाते हैं, और यह देखने के लिए कि क्या वह दूसरे किसी मोजे से मेल खाता है, उसकी ढेर के हर एक मोजे से तुलना करते हैं। यदि आपके पास 1,000 मोजे हैं, तो इसमें अनंत काल लग जाएगा।
नया तरीका (यह पेपर): लेखकों ने एक चतुर ट्रिक खोजी। यदि आपके पास मोजों का एक ढेर है जहाँ अधिकांश पहले से ही क्रमबद्ध (sorted) हैं, तो आप विशिष्ट पैटर्न देखकर मिलान करने वाले जोड़े को बहुत तेज़ी से खोज सकते हैं। उन्होंने ज़ैसेनहास एल्गोरिदम (Zassenhaus algorithm) नामक एक गणितीय तकनीक को एक सुपर-एफिशिएंट मोजा-सॉर्टर के रूप में अपनाया।

उन्होंने क्या हासिल किया:

गति: कई सामान्य मामलों के लिए (जब एक नोड का केवल एक ही बच्चा होता है), उन्होंने सॉर्टिंग प्रक्रिया को एक धीमी, भारी कार्य से एक त्वरित, हल्के कार्य में बदल दिया (इसे $O(n^3)$ से $O(n^2)$ में सुधार कर दिया)।
पूर्णता: उन्होंने इसे एक नए सिम्युलेटर QolDDer में लागू किया। क्योंकि उन्होंने नियमों का पूरी तरह से पालन किया, उनके फ्लोचार्ट "रिड्यूस्ड" (न्यूनतम आकार के) हैं।

परिणाम: प्रमाण (Proof in the Pudding)

टीम ने अपने नए सिम्युलेटर का मौजूदा सिम्युलेटर्स के विरुद्ध परीक्षण किया:

मानक फ्लोचार्ट (QMDDs) के विरुद्ध: "क्लिफोर्ड सर्किट्स" (एक विशिष्ट प्रकार का क्वांटम सर्किट) पर, उनका नया LIMDD घातांकीय रूप से (exponentially) तेज़ था। यह एक साइकिल की तुलना में रॉकेट शिप की तुलना करने जैसा था। मानक फ्लोचार्ट डेटा की विशाल मात्रा में फंस गए, जबकि नया LIMDD चीजों को छोटा बनाए रखने में सफल रहा।
अन्य LIMDDs के विरुद्ध: उन्होंने अपने काम की तुलना दो अन्य LIMDD सिम्युलेटर्स (MQT-LIMDD और LimTDD) से की।
- उनमें से एक ने विलय के नियमों का कड़ाई से पालन नहीं किया, जिसके कारण उसका फ्लोचार्ट फूला हुआ रहा और वह बहुत धीमा था।
- दूसरा मानक वाले की तुलना में तेज़ था लेकिन फिर भी नए सिम्युलेटर की गति का मुकाबला नहीं कर सका क्योंकि उसमें वह "परफेक्ट सॉर्टिंग" (canonicity) की कमी थी जो लेखकों ने हासिल की थी।

मुख्य निष्कर्ष (The Takeaway)

पेपर का दावा है कि LIMDD कुछ विशेष क्वांटम सर्किट्स के अनुकरण के लिए सैद्धांतिक रूप से सबसे अच्छा उपकरण है, लेकिन केवल तभी जब आप इसे सही ढंग से बना सकें।

पहले: लोग जानते थे कि LIMDD सिद्धांत में बहुत अच्छे हैं, लेकिन उन्हें बनाने के उपकरण बहुत धीमे या अपूर्ण थे, इसलिए वे व्यवहार में अच्छी तरह से काम नहीं कर पाते थे।
अब: लेखकों ने एक "परफेक्ट" टूल (QolDDer) बनाया है जिसमें एक तेज़ सॉर्टिंग एल्गोरिदम है। उन्होंने साबित किया कि जब आप इस टूल का उपयोग करते हैं, तो LIMDD वास्तव में अपने वादे को पूरा करते हैं, और विशिष्ट कार्यों पर पुराने तरीकों की तुलना में कई गुना तेज़ चलते हैं।

संक्षेप में: उन्होंने एक नया क्वांटम कंप्यूटर नहीं बनाया, बल्कि उन्होंने क्वांटम कंप्यूटर की स्थिति के "मैप" को व्यवस्थित करने का एक बहुत बेहतर तरीका बनाया, जिससे सिमुलेशन काफी तेज़ और अधिक कुशल हो गया।

तकनीकी सारांश: न्यूनतम-आकार के क्वांटम डिसीजन डायग्राम प्राप्त करने के लिए तेज़ एल्गोरिदम

समस्या विवरण
डिसीजन डायग्राम (DDs), क्वांटम अवस्थाओं और ऑपरेशन्स को दर्शाने के लिए एक संक्षिप्त डेटा संरचना हैं, जो समकक्ष उप-फंक्शंस (sub-functions) को एक कैनोनिकल रूप में मर्ज करके संक्षिप्तता (succinctness) प्राप्त करते हैं। जबकि लोकल इनवर्टिबल मैप डिसीजन डायग्राम्स (LIMDDs), विशिष्ट सर्किट वर्गों (जैसे, क्लिफोर्ड सर्किट्स) के लिए अन्य संरचनाओं जैसे कि क्वांटम मल्टीपल-वैल्यूड डिसीजन डायग्राम्स (QMDDs) की तुलना में सैद्धांतिक रूप से घातांकीय (exponential) लाभ प्रदान करते हैं, ये लाभ मौजूदा कार्यान्वयनों में पूरी तरह से प्रकट नहीं हुए हैं।

प्राथमिक बाधा नॉर्मल-फॉर्म प्रक्रिया है, विशेष रूप से हाई डिटर्मिनिज्म नियम जिसे कैनोनिसिटी (canonicity) सुनिश्चित करने के लिए आवश्यक है। यह नियम उन स्वतंत्रता के स्तरों (degrees of freedom) को हल करता है जहाँ दो नोड्स एक स्थानीय इनवर्टिबल मैप (LIM) तक एक ही क्वांटम अवस्था का प्रतिनिधित्व करते हैं। इस नियम के लिए मौजूदा एल्गोरिदम, जो समूह-सिद्धांत (group-theoretic) कार्यों पर आधारित है, एक $n$ -क्यूबिट नोड के लिए $O(n^3)$ की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी रखता है। इसके अलावा, मौजूदा ओपन-सोर्स कार्यान्वयन (MQT-LIMDD और LimTDD) या तो सभी मामलों में न्यूनतम आकार प्राप्त करने में विफल रहते हैं या कार्यान्वयन जटिलता से बचने के लिए कैनोनिसिटी गुण को जानबूझकर छोड़ देते हैं, जिससे नोड संख्या में संभावित घातांकीय वृद्धि (exponential blow-ups) हो सकती है।

कार्यप्रणाली
लेखक सेमी-रिड्यूस्ड पॉली-LIMDD नोड्स को पूर्णतः रिड्यूस्ड (कैनोनिकल) रूपों में बदलने के लिए एक नया एल्गोरिदम प्रस्तावित करते हैं, जो विशेष रूप से हाई डिटर्मिनिज्म नियम को अनुकूलित करता है।

एल्गोरिदम में सुधार:
- लेखक ज़ैसेनहास प्रक्रिया (Zassenhaus procedure) को अनुकूलित करते हैं, जो वेक्टर स्पेस के इंटरसेक्शन और यूनियन की गणना करने की एक विधि है, ताकि हाई डिटर्मिनिज्म के लिए आवश्यक मिनिमाइजेशन समस्या को हल किया जा सके।
- स्टेबलाइजर ग्रुप इंटरसेक्शन और कोसेट (cosets) को अलग-अलग गणना करने के बजाय, वे तीन रजिस्टरों के साथ एक "ज़ैसेनहास मैट्रिक्स" का निर्माण करते हैं: पॉली वर्ड्स (Pauli words) का प्रतिनिधित्व करने वाले बाइनरी वेक्टर्स, मिडिल स्टेबलाइजर्स, और राइट स्टेबलाइजर्स।
- पॉली-LIM मल्टीप्लिकेशन नियमों का उपयोग करके इस मैट्रिक्स पर गॉसियन एलिमिनेशन (Gaussian elimination) करके, वे न्यूनतम पॉली वर्ड और संबंधित स्टेबलाइजर जनरेटरों को एक साथ खोज लेते हैं।
- जटिलता में कमी:
  - दो अलग-अलग बच्चों (children) वाले नोड्स के लिए, एल्गोरिदम $O(n^3)$ की वर्स्ट-केस कॉम्प्लेक्सिटी बनाए रखता है लेकिन कम ओवरहेड के साथ।
  - एकल बच्चे (single child) वाले नोड्स के लिए (एक सामान्य मामला जहाँ DDs संक्षिप्तता प्राप्त करते हैं), समस्या एक सिंगल स्टेबलाइजर ग्रुप के विरुद्ध एक वेक्टर को मिनिमाइज करने में सरल हो जाती है। यह जटिलता को $O(n^3)$ से घटाकर $O(n^2)$ कर देता है।
रिकर्सिव स्टेबलाइजर फाइंडिंग:
- लेखक ज़ैसेनहास परिणामों का उपयोग करके एक रिड्यूस्ड नोड के लिए स्टेबलाइजर जनरेटिंग सेट की गणना करने के लिए एक रिकर्सिव एल्गोरिदम प्रस्तुत करते हैं। यह रेडंडेंट (redundant) ग्रुप इंटरसेक्शन गणनाओं से बचता है, जिससे सिंगल-चाइल्ड नोड्स के लिए $O(n^2)$ मामले को और अधिक अनुकूलित करता है।
कार्यान्वयन (QolDDer):
- इस एल्गोरिदम को C/C++ में लिखे गए एक नए, स्क्रैच से बने पॉली-LIMDD सिम्युलेटर, QolDDer में लागू किया गया है।
- QolDDer में कोर नॉर्मलाइजेशन लॉजिक के लिए एक अलग लाइब्रेरी, PauliLim शामिल है।
- कार्यान्वयन फ्लोटिंग-पॉइंट स्कैलर्स को एक कॉन्फ़िगर करने योग्य थ्रेशोल्ड ( $\delta = 10^{-13}$ ) के साथ मानकर और इक्विवेलेंस चेकिंग के लिए सर्च ट्रीज़ का उपयोग करके संख्यात्मक सटीकता (numerical precision) को संभालता है, जबकि कैनोनिसिटी को बनाए रखता है।

प्रमुख परिणाम
लेखकों ने RandCliff (रैंडम क्लिफोर्ड) और MQT-Bench डेटासेट्स का उपयोग करके QolDDer का मूल्यांकन दो मौजूदा LIMDD कार्यान्वयनों (MQT-LIMDD, LimTDD) और QMDD सिम्युलेटर (MQT-DDSIM) के विरुद्ध किया।

क्लिफोर्ड सर्किट्स पर घातांकीय गति (Exponential Speedup): रैंडम क्लिफोर्ड सर्किट्स (RandCliff) पर, QolDDer QMDDs (MQT-DDSIM) की तुलना में घातांकीय गति प्रदर्शित करता है। यह LIMDDs के सैद्धांतिक लाभ की पुष्टि करता है, जो क्लिफोर्ड सर्किट्स को दर्शा सकते हैं, जबकि QMDDs अत्यधिक एंटैंगल्ड (entangled) अवस्थाओं को संक्षिप्त रूप में नहीं दर्शा सकते।
कैनोनिसिटी का प्रभाव:
- QolDDer में पूर्ण कैनोनिसिटी (हाई डिटर्मिनिज्म) को सक्षम करने से क्लिफोर्ड सर्किट्स पर सेमी-रिड्यूस्ड (गैर-कैनोनिकल) संस्करणों की तुलना में काफी तेज़ रन टाइम और बहुत कम नोड्स प्राप्त होते हैं।
- QolDDer कई इंस्टेंस पर मौजूदा MQT-LIMDD कार्यान्वयन से एक ऑर्डर ऑफ मैग्नीट्यूड बेहतर प्रदर्शन करता है, जिसका श्रेय MQT-LIMDD के कैनोनिसिटी के आंशिक कार्यान्वयन को जाता है।
- QolDDer, कैनोनिकल मर्जिंग के माध्यम से प्राप्त नोड संख्या में कमी के कारण, क्लिफोर्ड सर्किट्स पर LimTDD (जिसमें कैनोनिसिटी गारंटी का अभाव है) की तुलना में लगातार 25 या उससे अधिक के कारक से तेज़ है।
सामान्य बेंचमार्क पर सीमाएँ: व्यापक MQT-Bench डेटासेट पर, कैनोनिसिटी का प्रदर्शन लाभ सार्वभौमिक नहीं है। कुछ सर्किट प्रकारों (जैसे, क्वांटम न्यूरल नेटवर्क, ग्रोवर एल्गोरिदम) के लिए, LIMs, QMDDs की तुलना में अधिक मर्जिंग प्रदान नहीं करते हैं, और कैनोनिसिटी बनाए रखने का ओवरहेड QolDDer को MQT-DDSIM की तुलना में थोड़ा धीमा (एक स्थिरांक कारक द्वारा) बना देता है। हालांकि, स्केलिंग रैखिक बनी रहती है।

महत्व और दावे
पेपर का दावा है कि LIMDDs की सैद्धांतिक शक्ति को साकार करने में प्राथमिक बाधा एक कुशल, पूर्णतः कैनोनिकल कार्यान्वयन की कमी रही है। एक $O(n^2)$ एल्गोरिदम प्रदान करके और एक मजबूत, ओपन-सोर्स कार्यान्वयन (QolDDer) के माध्यम से, लेखक प्रदर्शित करते हैं कि:

LIMDDs वास्तव में विशिष्ट, महत्वपूर्ण सर्किट वर्गों (क्लिफोर्ड सर्किट्स) के लिए QMDDs पर घातांकीय लाभ प्राप्त कर सकते हैं।
कैनोनिसिटी अनिवार्य है; इसके बिना, नोड संख्या बढ़ सकती है, जो डेटा स्ट्रक्चर के लाभों को निष्प्रभावी कर देती है।
यह कार्य क्वांटम डिज़ाइन कार्यों और सामान्य लीनियर-अल्जेब्रा-आधारित सिस्टम विश्लेषण दोनों के लिए LIMDD वेरिएंट के विकास को सक्षम बनाता है।

लेखक सामान्य बेंचमार्क के संबंध में विनम्र बने हुए हैं, यह नोट करते हुए कि उन सर्किट्स के लिए जहाँ LIMs, QMDDs की तुलना में कोई अतिरिक्त मर्जिंग नहीं देते हैं, कैनोनिकल ओवरहेड उचित नहीं हो सकता है। भविष्य के कार्य के रूप में इन एल्गोरिदम को व्यापक XP ग्रुप तक विस्तारित करना और सर्किट इक्विवेलेंस चेकिंग और क्लासिकल लीनियर अल्जेब्रा समस्याओं जैसे कार्यों के लिए LIMDDs को लागू करना विजन किया गया है।

एक बड़ी तस्वीर: एक अराजक पुस्तकालय को व्यवस्थित करना

समस्या: "अव्यवस्थित" फ्लोचार्ट

समाधान: एक तेज़ सॉर्टिंग एल्गोरिदम

परिणाम: प्रमाण (Proof in the Pudding)

मुख्य निष्कर्ष (The Takeaway)

इसी तरह के और पेपर