🔬 physics

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

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

मूल लेखक: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen

प्रकाशित 2026-08-10

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

CC0 1.0

मूल लेखक: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen

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

कल्पना कीजिए कि ब्रह्मांड एक विशाल, ब्रह्मांडीय पहेली है जहाँ हर टुकड़ा एक सूक्ष्म कण है, और जिस तरह से वे एक साथ फिट होते हैं, वही एक तारे के रंग से लेकर एक अणु की स्थिरता तक सब कुछ निर्धारित करता है। दशकों से, वैज्ञानिक इस पहेली के अंतिम संस्करण को हल करने की कोशिश कर रहे हैं: इन कणों की "ग्राउंड स्टेट" (ground state), या सबसे स्थिर, न्यूनतम-ऊर्जा वाली व्यवस्था को खोजना। यह केवल भौतिकविदों का खेल नहीं है; यह समझने की कुंजी है कि सामग्रियां बिजली का संचालन क्यों करती हैं, नई दवाएं वायरस पर कैसे हमला कर सकती हैं, और यहाँ तक कि कंप्यूटर की सीमाओं के बारे में भी।

इसे हल करने के लिए, कंप्यूटर वैज्ञानिक "कॉम्प्लेक्सिटी थ्योरी" (complexity theory) नामक एक विशेष प्रकार के तर्क का उपयोग करते हैं। इसे एक तरीके के रूप में सोचें जिससे यह मापा जाता है कि कोई समस्या कितनी कठिन है, न कि केवल इस आधार पर कि इसे हल करने में एक इंसान को कितना समय लगता है, बल्कि इस आधार पर कि जैसे-जैसे पहेली बड़ी होती जाती है, समय कैसे विस्फोट की तरह बढ़ता है। कुछ समस्याएं आसान होती हैं: यदि आप आकार को दोगुना करते हैं, तो इसे हल करने का समय भी दोगुना हो जाता है। अन्य "एक्सपोनेंशियल" (exponential) होती हैं, जिसका अर्थ है कि यदि आप केवल एक और टुकड़ा जोड़ते हैं, तो आवश्यक समय दोगुना हो सकता है, फिर फिर से दोगुना, फिर फिर से दोगुना, जब तक कि इसे हल करने में ब्रह्मांड की आयु से भी अधिक समय न लग जाए। इस क्षेत्र में दो प्रसिद्ध "नियम" (rules of the road), जिन्हें स्ट्रॉन्ग एक्सपोनेंशियल-टाइम हाइपोथीसिस (SETH) और इसके क्वांटम समकक्ष (QSETH) के रूप में जाना जाता है, सुझाव देते हैं कि कुछ प्रकार की पहेलियों के लिए, कोई जादुई शॉर्टकट नहीं है। वे दावा करते हैं कि उन्हें हल करने का एकमात्र तरीका हर एक संभावना की एक-एक करके जांच करना है, चाहे आपका कंप्यूटर कितना भी चतुर क्यों न हो।

यह शोध पत्र इन नियमों के केंद्र में गहराई से उतरता है, विशेष रूप से "लोकल हैमिल्टोनियन" (Local Hamiltonian) नामक एक समस्या पर ध्यान केंद्रित करता है। कल्पना कीजिए कि आपके पास ऊन का एक विशाल, उलझा हुआ गोला (एक क्वांटम सिस्टम) है और आप उस एक सटीक गांठ को खोजना चाहते हैं जो कम से कम तनाव के साथ इसे सब कुछ थामे हुए है। यह शोध पत्र एक सरल लेकिन भयानक प्रश्न पूछता है: क्या उस सटीक गांठ को खोजने का कोई तरीका है जो ब्रह्मांड की हर एक संभावित गांठ की जांच करने से तेज़ हो? लेखक, क्वांटम मैकेनिक्स और उन्नत गणित के मिश्रण का उपयोग करते हुए, कहते हैं "नहीं।" वे सिद्ध करते हैं कि SETH और QSETH के नियमों के तहत, वर्तमान सर्वोत्तम विधियां ही संभवतः सर्वोत्तम हैं जो हम कभी उम्मीद कर सकते हैं। वे यह भी दिखाते हैं कि इस उलझे हुए ऊन की "तापमान" (एक मान जिसे पार्टिशन फंक्शन कहा जाता है) की गणना करना भी उतना ही कठिन है, और उन्होंने इसे करने का एक नया, तेज़ तरीका भी बनाया है जो सैद्धांतिक गति सीमा को छूता है।

द ग्रेट पज़ल हंट: हम शॉर्टकट क्यों नहीं ले सकते

कहानी एक ऐसी समस्या से शुरू होती है जो एक भौतिकी के दुःस्वप्न जैसी लगती है लेकिन वास्तव में एक कंप्यूटर विज्ञान की पहेली है। "लोकल हैमिल्टोनियन" समस्या क्लासिक लॉजिक पहेली का क्वांटम संस्करण है। शास्त्रीय दुनिया में, आपके पास ऐसे नियम हो सकते हैं जैसे "यदि लाइट चालू है, तो दरवाजा बंद होना चाहिए।" आप उन सभी लाइटों और दरवाजों के लिए एक सेटिंग खोजना चाहते हैं जो हर नियम को संतुष्ट करती हो। क्वांटम दुनिया में, "लाइट्स" और "दरवाजे" क्यूबिट्स (qubits) हैं जो एक साथ कई अवस्थाओं में हो सकते हैं, और नियम उनके बीच की अंतःक्रियाएं हैं। लक्ष्य "ग्राउंड स्टेट" खोजना है, वह विन्यास जहाँ सिस्टम सबसे अधिक विश्राम की स्थिति में होता है और उसकी ऊर्जा सबसे कम होती है।

लंबे समय से, वैज्ञानिक जानते हैं कि इस ग्राउंड स्टेट को खोजना अविश्वसनीय रूप से कठिन है। वास्तव में, यह इतना कठिन है कि इसे "QMA-complete" माना जाता है, जो "NP-complete" का क्वांटम समकक्ष है। इसका अर्थ है कि यदि आप इस समस्या को कुशलतापूर्वक हल कर सकते हैं, तो आप ब्रह्मांड की लगभग किसी भी अन्य कठिन समस्या को कुशलतापूर्वक हल कर सकते हैं। लेकिन कितना कठिन है? क्या यह केवल "बहुत कठिन" है, या यह "ब्रूट फोर्स विधि को हराने में असंभव" है?

इस शोध पत्र के लेखकों ने सीमाओं का परीक्षण करने का निर्णय लिया। वे जानना चाहते थे कि क्या कोई छिपा हुआ शॉर्टकट है जो हमें इन क्वांटम पहेलियों को वर्तमान सर्वोत्तम विधियों की तुलना में काफी तेज़ी से हल करने की अनुमति देता है। वर्तमान सर्वोत्तम विधियों में बहुत समय लगता है: $n$ क्यूबिट्स के सिस्टम के लिए, क्लासिकल कंप्यूटर लगभग $2^n$ स्टेप्स लेते हैं, और क्वांटम कंप्यूटर लगभग $2^{n/2}$ स्टेप्स लेते हैं। ये संख्याएँ इतनी तेज़ी से बढ़ती हैं कि केवल कुछ सौ क्यूबिट्स वाले सिस्टम के लिए, आवश्यक समय ब्रह्मांड के जीवनकाल से भी अधिक हो जाता है। शोध पत्र पूछता है: क्या हम इससे बेहतर कर सकते हैं? क्या हम उस समय में थोड़ी कटौती कर सकते हैं, शायद इसे $2^n$ के बजाय $2^{0.9n}$ बना सकते हैं?

द मैजिक ट्रिक: क्लॉक को कंप्रेस करना

इसका उत्तर देने के लिए, लेखकों को दो अलग-अलग दुनियाओं के बीच एक पुल बनाना था: लॉजिक पहेलियों (जैसे SAT समस्याएं) की दुनिया और क्वांटम भौतिकी (लोकल हैमिल्टोनियन) की दुनिया। इस पुल को बनाने का मानक तरीका "सर्किट-टू-हैमिल्टोनियन कंस्ट्रक्शन" कहलाता है। इसे एक फिल्म की स्क्रिप्ट (लॉजिक पहेली) को एक भौतिक सेट (क्वांटम सिस्टम) में अनुवाद करने जैसा समझें।

पुराने अनुवाद पद्धति के साथ समस्या यह थी कि यह अविश्वसनीय रूप से अपव्ययकारी थी। फिल्म स्क्रिप्ट (घटनाओं के क्रम) में "समय" को दर्शाने के लिए, पुरानी पद्धति ने एक "यूनरी क्लॉक" (unary clock) का उपयोग किया। कल्पना कीजिए कि आपके पास 1,000 दृश्यों वाली एक फिल्म है। यूनरी क्लॉक 1,000 अलग-अलग स्विचों का उपयोग करेगी, जहाँ एक समय में केवल एक स्विच "ऑन" होगा ताकि यह दिखाया जा सके कि आप किस दृश्य में हैं। यदि फिल्म लंबी होती है, तो आपको अधिक स्विचों की आवश्यकता होगी। इसका मतलब था कि एक जटिल पहेली के लिए, क्वांटम सिस्टम को मूल पहेली के वेरिएबल्स की तुलना में बहुत अधिक क्यूबिट्स (स्विचों) की आवश्यकता थी। इस अतिरिक्त आकार ने इसे साबित करना असंभव बना दिया कि समस्या वास्तव में मूल पहेली जितनी ही कठिन थी, क्योंकि "अनुवाद" ने स्वयं समस्या को फुला दिया था।

लेखकों की सफलता एक नए प्रकार के क्लॉक का आविष्कार करने में थी। उन्होंने इसे "साइज-प्रिजर्विंग कंस्ट्रक्शन" (size-preserving construction) कहा। 1,000 दृश्यों के लिए 1,000 स्विचों का उपयोग करने के बजाय, उन्होंने कुछ ही स्विचों की एक चतुर व्यवस्था का उपयोग किया जो अभी भी सभी 1,000 दृश्यों का प्रतिनिधित्व कर सकते थे। उन्होंने समय की जानकारी को बहुत अधिक सघनता से पैक करने के लिए "जॉनसन ग्राफ" (Johnson graph) नामक एक गणितीय संरचना का उपयोग किया (कल्पना कीजिए कि यह कनेक्शनों का एक विशाल जाल है)। यह एक लंबी लाइन में हाथ पकड़े लोगों के बजाय एक जटिल नृत्य फॉर्मेशन की तरह है जहाँ हर कोई एक विशिष्ट स्थान पर है, लेकिन पूरा समूह बहुत कम जगह घेरता है।

इस नए क्लॉक ने उन्हें $n$ वेरिएबल्स वाली लॉजिक पहेली को केवल $n$ प्लस थोड़े से अतिरिक्त स्पेस वाले क्वांटम सिस्टम में अनुवाद करने की अनुमति दी, न कि $n$ प्लस बहुत अधिक स्पेस में। यही मुख्य कुंजी थी। क्योंकि अनुवाद ने अतिरिक्त भार नहीं डाला, वे अंततः यह सिद्ध कर सके कि क्वांटम समस्या मूल लॉजिक पहेली जितनी ही कठिन थी, बिना किसी अतिरिक्त वेरिएबल्स को जोड़कर "शॉर्टकट" लिए।

द वर्डिक्ट: कोई शॉर्टकट मान्य नहीं

अपने नए, कुशल अनुवाद उपकरण के साथ, लेखकों ने अंतिम परीक्षण किया। उन्होंने माना कि "स्ट्रॉन्ग एक्सपोनेंशियल-टाइम हाइपोथीसिस" (SETH) और इसके क्वांटम संस्करण (QSETH) सत्य हैं। ये हाइपोथीसिस कंप्यूटर विज्ञान के लिए "भौतिकी के नियमों" की तरह हैं, जो कहते हैं कि कुछ लॉजिक पहेलियों के लिए, आप हर एक संभावना की जांच करने से बेहतर कुछ नहीं कर सकते।

उन्होंने सिद्ध किया कि यदि ये नियम सत्य हैं, तो लोकल हैमिल्टोनियन समस्या को भी वर्तमान सीमाओं से तेज़ी से हल करना असंभव है। विशेष रूप से:

क्लासिकल कंप्यूटरों के लिए: आप 3-लोकल हैमिल्टोनियन को किसी भी $\epsilon > 0$ के लिए $O(2^{(1-\epsilon)n})$ समय में हल नहीं कर सकते। सरल शब्दों में, आप एक्सपोनेंशियल समय के एक छोटे से हिस्से की भी कटौती नहीं कर सकते। वर्तमान सर्वोत्तम एल्गोरिदम ही संभवतः सर्वोत्तम हैं जो हमारे पास होंगे।
क्वांटम कंप्यूटरों के लिए: आप इसे $O(2^{(1-\epsilon)n/2})$ समय में हल नहीं कर सकते। क्वांटम मैकेनिक्स की शक्ति के साथ भी, आप ग्रोवर के सर्च एल्गोरिदम द्वारा प्रदान किए गए स्क्वायर-रूट स्पीडअप को नहीं हरा सकते।

शोध पत्र स्पष्ट रूप से इस विचार को खारिज करता है कि कोई चतुर, छिपा हुआ एल्गोरिदम खोजा जाना बाकी है जो इन समस्याओं को काफी तेज़ी से हल करेगा। यदि ऐसा एल्गोरिदम मौजूद होता, तो वह उन मौलिक धारणाओं (SETH/QSETH) को तोड़ देता जिन पर संपूर्ण फाइन-ग्रेन्ड कॉम्प्लेक्सिटी का क्षेत्र निर्मित है। लेखक केवल यह नहीं कह रहे हैं कि "हमने इसे अभी तक नहीं पाया है"; वे कह रहे हैं कि "यदि आप इसे पा लेते हैं, तो आप खेल के नियम तोड़ देंगे।"

द पार्टिशन फंक्शन: अदृश्य को गिनना

शोध पत्र केवल ग्राउंड स्टेट खोजने पर नहीं रुका। उन्होंने "क्वांटम पार्टिशन फंक्शन" (QPF) को भी देखा। यदि ग्राउंड स्टेट सबसे स्थिर गांठ है, तो पार्टिशन फंक्शन यह गिनने जैसा है कि ऊन के उलझने के कितने संभावित तरीके हैं, जिन्हें उनकी स्थिरता के आधार पर भारित किया गया है। यह समझने के लिए महत्वपूर्ण है कि विभिन्न तापमानों पर सामग्रियां कैसे व्यवहार करती हैं।

इसकी गणना करना ग्राउंड स्टेट खोजने से भी अधिक कठिन है क्योंकि आपको केवल सबसे निचली ऊर्जा के बजाय प्रत्येक संभावित ऊर्जा स्तर के बारे में जानकारी चाहिए। लेखकों ने दिखाया कि यह समस्या भी "SETH-hard" और "QSESETH-hard" है। इसका अर्थ है कि एक स्थिर त्रुटि (constant error) के साथ पार्टिशन फंक्शन का अनुमान लगाना उतना ही कठिन है जितना कि लॉजिक पहेलियों को हल करना।

हालाँकि, उन्होंने केवल यह नहीं कहा कि "यह कठिन है।" उन्होंने इसे संभालने के लिए एक नया क्वांटम एल्गोरिदम भी बनाया। पिछले एल्गोरिदम कम तापमान पर धीमे थे (जो कि वह समय है जब भौतिकी सबसे दिलचस्प होती है)। लेखकों का नया एल्गोरिदम $O(2^{n/2})$ समय में चलता है, जो उस सैद्धांतिक निचले स्तर (lower bound) से मेल खाता है जिसे उन्होंने अभी सिद्ध किया है। यह ऐसा है जैसे उन्होंने दौड़ के लिए सबसे तेज़ कार ढूंढ ली हो, और फिर सिद्ध कर दिया हो कि कोई भी कार उस ट्रैक पर उससे तेज़ नहीं चल सकती।

यह क्यों महत्वपूर्ण है

यह शोध पत्र एक मील का पत्थर है क्योंकि यह एक स्पष्ट रेखा खींचता है। वर्षों से, शोधकर्ता इस उम्मीद में थे कि क्वांटम कंप्यूटर अंततः इन विशाल भौतिकी पहेलियों को हमारी सोच से कहीं अधिक तेज़ी से हल करने का तरीका खोज लेंगे। यह शोध पत्र कहता है, "जादुई समाधान की उम्मीद छोड़ दें।" हमारे कंप्यूटरों के काम करने के सबसे तर्कसंगत अनुमानों के तहत, वर्तमान विधियां ही उच्चतम सीमा हैं।

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

अंत में, शोध पत्र सीमाओं की कहानी बताता है। यह सुझाव देता है कि ब्रह्मांड जटिल है और हमारे शॉर्टकट लेने के प्रयासों का विरोध करता है। चाहे आप क्लासिकल कंप्यूटर हों या क्वांटम, कुछ पहेलियाँ बस कठिन तरीके से, एक-एक कदम करके हल होने के लिए बनी होती हैं। और यह ठीक है, क्योंकि यह समझना कि हम शॉर्टकट क्यों नहीं ले सकते, उत्तर खोजने जितना ही महत्वपूर्ण है।

तकनीकी सारांश: आकार-संरक्षण करने वाले सर्किट-टू-हैमिल्टनियन निर्माणों से क्वांटम समस्याओं के लिए सूक्ष्म-स्तरीय जटिलता (Fine-Grained Complexity)

1. समस्या विवरण (Problem Statement)

यह शोध पत्र क्वांटम जटिलता सिद्धांत की दो मौलिक समस्याओं के सूक्ष्म-स्तरीय जटिलता (fine-grained complexity) की जांच करता है: लोकल हैमिल्टनियन (LH) समस्या और क्वांटम पार्टिशन फंक्शन (QPF) समस्या।

लोकल हैमिल्टनियन (LH): $n$ क्विबिट्स पर कार्य करने वाले $k$ -लोकल हैमिल्टनियन $H$ को देखते हुए, इसके ग्राउंड-स्टेट ऊर्जा $\lambda(H)$ का एक स्थिर योगात्मक त्रुटि (constant additive error) के भीतर अनुमान लगाना। यह एक कैनोनिकल QMA-पूर्ण समस्या है।
क्वांटम पार्टिशन फंक्शन (QPF): एक हैमिल्टनियन $H$ और एक इनवर्स टेम्परेचर $\beta$ को देखते हुए, पार्टिशन फंक्शन $Z = \text{tr}[e^{-\beta H}]$ का एक स्थिर सापेक्ष त्रुटि (constant relative error) तक अनुमान लगाना। यह समस्या एक QMA वेरीफायर द्वारा स्वीकार किए गए विटनेस (witnesses) की संख्या को लगभग गिनने के समतुल्य है।

मुख्य प्रश्न: क्या ऐसे शास्त्रीय या क्वांटम एल्गोरिदम मौजूद हैं जो वर्तमान सर्वोत्तम ज्ञात सीमाओं से काफी बेहतर प्रदर्शन कर सकते हैं?

LH के लिए शास्त्रीय एल्गोरिदम $O^*(2^n)$ समय में चलते हैं।
LH के लिए क्वांटम एल्गोरिदम $O^*(2^{n/2})$ समय में चलते हैं (ग्रोवर सर्च के माध्यम से)।
QPF के लिए, मौजूदा क्वांटम एल्गोरिदम $O^*(\frac{1}{\delta}\sqrt{2^n/Z})$ समय में चलते हैं, जो लो-टेम्परेचर रिजीम (बड़ा $\beta$ ) में $O^*(2^{n/2})$ से भी अधिक हो सकता है जहाँ $Z$ घातांकीय रूप से छोटा (exponentially small) होता है।

लेखक स्ट्रॉन्ग एक्सपोनेंशियल-टाइम हाइपोथीसिस (SETH) और इसके क्वांटम एनालॉग, क्वांटम स्ट्रॉन्ग एक्सपोनेंशियल-टाइम हाइपोथीसिस (QSETH) के आधार पर सशर्त निचली सीमाओं (conditional lower bounds) को स्थापित करने का लक्ष्य रखते हैं, ताकि यह निर्धारित किया जा सके कि क्या ये रनिंग टाइम्स इष्टतम (optimal) हैं।

2. कार्यप्रणाली और प्रमुख तकनीकें (Methodology and Key Techniques)

2.1 आकार-संरक्षण करने वाला सर्किट-टू-हैमिल्टनियन निर्माण (Size-Preserving Circuit-to-Hamiltonian Construction)

फिक्स्ड-लोकैलिटी हैमिल्टोनियन्स (जैसे, 3-लोकल) के लिए फाइन-ग्रेंड लोअर बाउंड्स स्थापित करने में प्राथमिक तकनीकी बाधा मानक रिडक्शन में "साइज ओवरहेड" है।

मानक रिडक्शन: यूनरी क्लॉक निर्माण (किटाएव, केम्पे, रेगेव [KKR06]) $T$ गेट्स के सर्किट को 2-लोकल हैमिल्टनियन में बदल देता है लेकिन इसके लिए $O(T)$ एंसिलर क्विबिट्स की आवश्यकता होती है। चूंकि $T$ , $n$ के बहुपद (polynomial) में हो सकता है, इसलिए परिणामी हैमिल्टनियन $n + O(n)$ क्विबिट्स पर कार्य करता है, जो फाइन-ग्रेंड $O(2^n)$ बनाम $O(2^{n(1-\epsilon)})$ के अंतर को नष्ट कर देता है।
बाइनरी क्लॉक: क्विबिट संख्या को $O(\log T)$ तक कम करता है लेकिन लोकैलिटी को $O(\log T)$ तक बढ़ा देता है, जो फिक्स्ड-लोकैलिटी की आवश्यकता को पूरा करने में विफल रहता है।
लेखकों का नवाचार: यह शोध पत्र पहला आकार-संरक्षण करने वाला सर्किट-टू-हैमिल्टनियन निर्माण प्रस्तुत करता है।
- तंत्र: वे जॉनसन ग्राफ (Johnson graphs) से आधारित एक $(n, d)$ -क्लॉक स्टेट ([CCH+23] से) को एक यूनरी क्लॉक के साथ जोड़ते हैं।
- निर्माण: क्लॉक रजिस्टर दो सब-रजिस्टर्स का उपयोग करता है: एक जॉनसन ग्राफ पाथ के माध्यम से समय को एनकोड करने के लिए (जो $T$ स्टेप्स के लिए $O(T^{1/d})$ क्विबिट्स की अनुमति देता है) और एक यूनरी क्लॉक जो जॉनसन ग्राफ पाथ के आवधिक भ्रमण (periodic traversal) को प्रबंधित करती है।
- परिणाम: $N$ क्विबिट्स पर $T$ गेट्स वाले एक वेरिफिकेशन सर्किट को $N + O(T^{1/d})$ क्विबिट्स पर कार्य करने वाले एक $(d+1)$ -लोकल हैमिल्टनियन में मैप किया जाता है। $d$ को उपयुक्त रूप से चुनकर, ओवरहेड $o(n)$ हो जाता है, जो फाइन-ग्राइंड विश्लेषण के लिए इनपुट साइज को सुरक्षित रखता है।

2.2 SAT के लिए कुशल वेरिफिकेशन सर्किट

SETH/QSETH को लागू करने के लिए, लेखक एक क्वांटम वेरिफिकेशन सर्किट का निर्माण करते हैं जो $o(n)$ एंसिलर क्विबिट्स का उपयोग करता है।

क्लॉज को व्यक्तिगत रूप से बड़े ओवरहेड के साथ चेक करने के बजाय, वे संतुष्ट क्लॉज की संख्या को ट्रैक करने के लिए एक काउंटर का उपयोग करते हैं।
काउंटर के लिए केवल $O(\log m) = O(\log n)$ एंसिलर क्विबिट्स की आवश्यकता होती है।
यह सुनिश्चित करता है कि परिणामी हैमिल्टनियन में कुल क्विबिट्स की संख्या $n + o(n)$ है, जो फाइन-ग्राइंड रिडक्शन की सख्त आवश्यकताओं को पूरा करती है।

2.3 फाइन-ग्राइंड रिडक्शन (Fine-Grained Reductions)

LH से SAT: आकार-संरक्षण निर्माण का उपयोग करते हुए, लेखक $k$ -SAT इंस्टेंस को 3-लोकल हैमिल्टनियन में रिड्यूस करते हैं। SETH (या QSETH) के तहत, $k$ -SAT को हल करने के लिए $2^{(1-\epsilon)n}$ (या $2^{(1-\epsilon)n/2}$ ) समय की आवश्यकता होती है। चूंकि रिडक्शन केवल $o(n)$ क्विबिट्स जोड़ता है, इसलिए 3-LH को $O^*(2^{(1-\epsilon)n})$ (या $O^*(2^{(1-\epsilon)n/2})$ ) में हल करना SETH (या QSETH) को गलत सिद्ध कर देगा।
LH से QPF: लेखक दिखाते हैं कि पर्याप्त बड़े $\beta$ के लिए $E_{yes}$ और $E_{no}$ के बीच अंतर करने के लिए QPF का एक स्थिर सापेक्ष त्रुटि के साथ अनुमान लगाना संभव है। विशेष रूप से, यदि $E_{no} - E_{yes} = \Omega(1)$ है, तो पार्टिशन फंक्शन $Z$ , $e^{\beta(E_{no}-E_{yes})}$ के कारक से भिन्न होता है, जो बड़े $\beta$ के लिए $2^n$ डिजेनरेसी फैक्टर पर हावी हो जाता है। यह LH से QPF तक एक फाइन-ग्राइंड रिडक्शन स्थापित करता है।

2.4 QPF के लिए क्वांटम एल्गोरिदम

लोअर बाउंड्स से मेल खाने के लिए, लेखक QPF के लिए एक नया क्वांटम एल्गोरिदम प्रस्तावित करते हैं:

दृष्टिकोण: ऊर्जा स्पेक्ट्रम को कई बहुपद (polynomially many) अंतरालों (intervals) में विभाजित करें। क्वांटम काउंटिंग (एम्प्लीट्यूड एस्टीमेशन) का उपयोग करके प्रत्येक अंतराल में आइजनस्टेट्स की संख्या $M_j$ का अनुमान लगाएं, जिसे एक EPR स्टेट (जो आइजनबेसिस पर एक समान सुपरपोजिशन के रूप में कार्य करता है) पर लागू किया जाता है।
त्रुटि हैंडलिंग: $1/\text{poly}(n)$ सापेक्ष त्रुटि प्राप्त करने के लिए (मानक फेज एस्टीमेशन की कांस्टेंट एरर से निपटने के लिए), एल्गोरिदम अलग-अलग सीमाओं वाले कई विभाजनों पर चलता है। एक एवरेजिंग तर्क यह सुनिश्चित करता है कि सीमाओं के पास आइजनस्टेट्स की "डबल-काउंटिंग" न्यूनतम हो।
जटिलता: एल्गोरिदम $O^*(2^{n/2})$ समय में चलता है, जो पार्टिशन फंक्शन के मान $Z$ से स्वतंत्र है। यह विशेष रूप से लो-टेम्परेचर रिजीम को संबोधित करता है जहाँ पिछले एल्गोरिदम $Z$ के घातांकीय रूप से छोटे होने के कारण $O^*(2^{n/2})$ की अपेक्षित क्वाड्रेटिक स्पीडअप प्राप्त करने में विफल रहे थे।

3. मुख्य परिणाम (Key Results)

3.1 लोकल हैमिल्टनियन के लिए लोअर बाउंड्स

थ्योरम 1.2 (अनौपचारिक): यह मानते हुए कि SETH (या QSETH), $n$ क्विबिट्स पर एक 3-लोकल हैमिल्टनियन के ग्राउंड-स्टेट ऊर्जा का निरंतर योगात्मक त्रुटि के साथ अनुमान लगाना निम्न में हल नहीं किया जा सकता है:

शास्त्रीय रूप से $O^*(2^{(1-\epsilon)n})$ समय में, किसी भी $\epsilon > 0$ के लिए।
क्वांटम रूप से $O^*(2^{(1-\epsilon)n/2})$ समय में, किसी भी $\epsilon > 0$ के लिए।

ये बाउंड्स सर्वोत्तम ज्ञात शास्त्रीय ( $O^*(2^n)$ ) और क्वांटम ( $O^*(2^{n/2})$ ) एल्गोरिदम के प्रदर्शन से मेल खाते हैं, जो सुझाव देते हैं कि ये SETH/QSETH के तहत इष्टतम हैं।

3.2 क्वांटम पार्टिशन फंक्शन के लिए लोअर बाउंड्स

थ्योरम 1.3 (अनौपचारिक): यह मानते हुए कि SETH (या QSETH), निरंतर सापेक्ष त्रुटि के साथ 3-लोकल हैमिल्टनियन्स के लिए QPF का अनुमान लगाना निम्न में हल नहीं किया जा सकता है:

शास्त्रीय रूप से $O^*(2^{(1-\epsilon)n})$ समय में।
क्वांटम रूप से $O^*(2^{(1-\epsilon)n/2})$ समय में।

यह लो-टेम्परेचर रिजीम में भी मान्य है जहाँ $Z$ घातांकीय रूप से छोटा होता है।

3.3 क्वांटम पार्टिशन फंक्शन के लिए अपर बाउंड

थ्योरम 1.4 (अनौपचारिक): एक ऐसा क्वांटम एल्गोरिदम मौजूद है जो कांस्टेंट-लोकल हैमिल्टोनियन्स के लिए $1/\text{poly}(n)$ सापेक्ष त्रुटि के साथ $O^*(2^{n/2})$ समय में QPF का अनुमान लगा सकता है।

यह पिछले एल्गोरिदम (जैसे, Bravyi et al. [BCGW22]) की तुलना में सुधार करता है जिनका रनटाइम $1/\sqrt{Z}$ पर निर्भर था, जो विशेष रूप से लो-टेम्परेचर रिजीम (बड़ा $\beta$ ) में सुपर-पॉलिनोमियलियल हो सकता है।
नया एल्गोरिदम सभी इनवर्स टेम्परेचर $\beta = \text{poly}(n)$ के लिए यूनिफॉर्म है, यह सुनिश्चित करता है कि $O^*(2^{n/2})$ का बाउंड तब भी बना रहे जब $Z$ घातांकीय रूप से छोटा हो।

4. महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि यह पहला आकार-संरक्षण करने वाला सर्किट-टू-हैमिल्टनियन निर्माण प्रदान करता है जो एक साथ निम्नलिखित प्राप्त करता है:

आकार-संरक्षण (Size Preservation): परिणामी हैमिल्टनियन $N + o(T)$ क्विबिट्स पर कार्य करता है (विशेष रूप से $N + O(T^{1/d})$ )।
स्थिर लोकैलिटी (Constant Locality): लोकैलिटी $d+1$ है, जो सर्किट साइज $T$ से स्वतंत्र है।

निहितार्थ:

वर्तमान एल्गोरिदम की इष्टतमता: परिणाम इस बात का पुख्ता प्रमाण देते हैं कि LH और QPF के लिए $O^*(2^n)$ और $O^*(2^{n/2})$ की बाधाएं मौलिक हैं और SETH/QSETH को गलत सिद्ध किए बिना इन्हें तोड़ा नहीं जा सकता है।
लो-टेम्परेचर QPF का समाधान: यह पेपर लो-टेम्परेचर रिजीम में QPF की जटिलता को हल करता है, यह दिखाते हुए कि एक क्वाड्रेटिक स्पीडअप ( $2^{n/2}$ ) प्राप्त किया जा सकता है और यह इष्टतम भी है, भले ही $Z$ घातांकीय रूप से छोटा हो। यह पिछले समझ को सुधारता है कि लो-टेम्परेचर के लिए सुपर-ग्रोवर समय की आवश्यकता हो सकती है।
पद्धतिगत प्रगति: जॉनसन ग्राफ और यूनरी क्लॉक का उपयोग करके कंप्रेस्ड क्लॉक स्टेट का निर्माण, क्वांटम जटिलता रिडक्शन में ओवरहेड को कम करने के लिए एक नया उपकरण प्रदान करता है, जिसे अन्य QMA-हार्ड समस्याओं पर भी लागू किया जा सकता है।

लेखक स्पष्ट रूप से कहते हैं कि उनके लोअर बाउंड्स SETH और QSETH पर सशर्त हैं, जिन्हें व्यापक रूप से प्रशंसनीय लेकिन अपुष्ट अनुमान माना जाता है। वे यह दावा नहीं कर रहे हैं कि उन्होंने इन हाइपोथीसिस को सिद्ध कर दिया है, बल्कि यह स्थापित किया है कि SETH/QSETH को मानते हुए LH और QPF की कठिनाई क्या है। शोध पत्र यह भी नोट करता है कि जबकि 2-लोकल हैमिल्टोनियन्स QMA-हार्ड हैं, इन विशिष्ट फाइन-ग्राइंड लोअर बाउंड्स को 2-लोकल मामले में विस्तारित करना एक खुला प्रश्न बना हुआ है क्योंकि लोकैलिटी को और कम करते समय आकार-संरक्षण बनाए रखना कठिन है।