⚛️ quantum physics

A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

यह शोध पत्र समान रूट जनरेशन (uniform route generation), वैधता मार्किंग (validity marking) और लागत चरण संचय (cost phase accumulation) के साथ एक टाइम-रजिस्टर प्रतिनिधित्व का उपयोग करते हुए ट्रैवलिंग सेल्सपर्सन समस्या के एक कॉम्पैक्ट क्वांटम एनकोडिंग का प्रस्ताव करता है, जो बहुपद क्वबिट और सर्किट डेप्थ आवश्यकताओं को प्राप्त करता है, जबकि यह स्वीकार करता है कि वैध दौरों की घातांकीय कमी (exponential scarcity) एम्प्लीट्यूड एम्प्लीफिकेशन के साथ भी इस पद्धति को समस्या की अंतर्निहित घातांकीय जटिलता को पार करने से रोकती है।

मूल लेखक: Alexander Johannes Stasik, Franz Georg Fuchs

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

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

CC BY 4.0

मूल लेखक: Alexander Johannes Stasik, Franz Georg Fuchs

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

कल्पना कीजिए कि आप एक ट्रैवल एजेंट हैं जो एक परम पहेली को हल करने की कोशिश कर रहे हैं: द ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP)। आपके पास $n$ शहरों का एक मानचित्र है, और आपको सबसे छोटा संभव मार्ग खोजना है जिसमें हर शहर की ठीक एक बार यात्रा की जाए और फिर वापस घर लौटा जाए।

समस्या यह है कि जैसे-जैसे आप शहरों की संख्या बढ़ाते हैं, संभावित मार्गों की संख्या विस्फोट की तरह बढ़ती जाती है। केवल 20 शहरों के लिए, संभावित मार्गों की संख्या ब्रह्मांड में मौजूद परमाणुओं की संख्या से भी अधिक है। एक सामान्य कंप्यूटर पर एक-एक करके उन्हें जांचने में ब्रह्मांड की आयु से भी अधिक समय लग जाएगा।

यह शोध पत्र एक तरीका प्रस्तावित करता है जिसका उपयोग करने के लिए एक क्वांटम कंप्यूटर की आवश्यकता है, न कि इसे जादुई रूप से तुरंत हल करने के लिए, बल्कि अव्यवस्था को बहुत चतुराई से व्यवस्थित करने के लिए। यहाँ सरल उपमाओं का उपयोग करके इसका विवरण दिया गया है।

1. सेटअप: "टाइम-ट्रैवलिंग" नोटबुक

शहरों के बीच रेखाएं खींचने के बजाय (जो अधिकांश कंप्यूटर प्रोग्राम करते हैं), लेखक एक अलग दृष्टिकोण का सुझाव देते हैं: एक टाइम-ट्रैवलिंग नोटबुक।

उपमा: कल्पना कीजिए कि आपके पास $n-1$ पृष्ठों वाली एक नोटबुक है। पृष्ठ 1 पर, आप पहले शहर को लिखते हैं जिसे आप देखते हैं। पृष्ठ 2 पर, दूसरा शहर, और इसी तरह।
क्वांटम ट्रिक: एक सामान्य कंप्यूटर नोटबुक में एक विशिष्ट मार्ग लिखता है (जैसे, "लंदन, पेरिस, बर्लिन...")। हालाँकि, एक क्वांटम कंप्यूटर एक ही समय में नोटबुक में शहरों के हर संभव संयोजन को लिख सकता है। यह एक "सुपरपोजिशन" बनाता है, जो एक जादुई बादल की तरह है जिसमें एक साथ हर संभावित यात्रा कार्यक्रम समाहित है।

2. तीन जादुई उपकरण (सामग्री)

इस संभावनाओं के बादल को उपयोगी बनाने के लिए, लेखकों ने इस क्वांटम अवस्था को नियंत्रित करने के लिए तीन विशिष्ट "उपकरण" (या सर्किट) बनाए हैं:

A. द यूनिफॉर्म जनरेटर (द "शफलर")

सबसे पहले, कंप्यूटर रैंडम तरीके से शहरों के नाम नोटबुक में भर देता है। उसे अभी इस बात की परवाह नहीं है कि मार्ग समझ में आने वाला है या नहीं; वह बस यह सुनिश्चित करता है कि शहरों का हर संभावित संयोजन क्वांटम क्लाउड में प्रतिनिधित्व किया गया है।

रूपक: यह ताश की गड्डी को रैंडम तरीके से फेंटने और उसे एक साथ हर संभावित खिलाड़ी को बांटने वाली मशीन की तरह है।

B. द वैलिडिटी ऑरेकल (द "स्ट्रिक्ट लाइब्रेरियन")

यह सबसे महत्वपूर्ण फिल्टर है। हमारी रैंडम नोटबुक में, कई मार्ग निरर्थक हैं (जैसे, "पेरिस" को तीन बार देखना और "बर्लिन" को पूरी तरह से छोड़ देना)।

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

C. द कॉस्ट ऑरेकल (द "प्राइस टैगर")

एक बार जब किसी मार्ग पर "वैलिड" स्टैम्प लग जाता है, तो कंप्यूटर को यह जानने की आवश्यकता होती है कि यात्रा कितनी लंबी है।

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

3. परिणाम: मार्गों का एक सिम्फनी

इन उपकरणों को चलाने के बाद, क्वांटम कंप्यूटर एक विशाल, जटिल तरंग धारण करता है।

"इनवैलिड" मार्गों को कचरा चिह्नित किया जाता है।
"वैलिड" मार्गों को अच्छा चिह्नित किया जाता है।
अच्छे मार्गों के बीच, छोटी यात्राओं की "पिच" लंबी यात्राओं की तुलना में अलग होती है।

अब कंप्यूटर के पास एक कोहेरेंट सुपरपोजिशन है: एक एकल क्वांटम अवस्था जिसमें सभी वैध दौरे शामिल हैं, और उनकी लागत उनके तरंग पैटर्न में एनकोड की गई है।

4. रियलिटी चेक: यह एक जादुई समाधान क्यों नहीं है

शोध पत्र अपनी सीमाओं के बारे में ईमानदार है। हालांकि यह समस्या को क्वांटम मेमोरी में व्यवस्थित करने का एक सुंदर और संक्षिप्त तरीका है, यह "एक्सपोनेंशियल वॉल" (घातीय दीवार) को हल नहीं करता है।

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

सारांश

यह शोध पत्र एक ब्लूप्रिंट प्रस्तुत करता है कि कैसे एक क्वांटम कंप्यूटर पर ट्रैवलिंग सेल्सपर्सन प्रॉब्लम को व्यवस्थित किया जाए।

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

निष्कर्ष: यह समस्या को क्वांटम मेमोरी में स्टोर करने का एक बहुत ही कुशल तरीका है, लेकिन यह इसे तुरंत हल करने के लिए अभी तक कोई शॉर्टकट प्रदान नहीं करता है। यह भविष्य के शोधकर्ताओं के लिए एक ठोस आधार है जिस पर वे निर्माण कर सकें, शायद अंततः कोड को तोड़ने के लिए अन्य उन्नत क्वांटम तकनीकों के साथ इसे जोड़कर।

यहाँ स्टैसिक और फुच्स के शोध पत्र "A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation Oracle" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP) को संबोधित करता है, जो एक क्लासिक NP-hard कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्या है। इसका लक्ष्य $n$ शहरों के एक भारित (weighted) ग्राफ में एक न्यूनतम-लागत वाले हैमिल्टोनियन चक्र (Hamiltonian cycle) को खोजना है, जो प्रत्येक शहर की ठीक एक बार यात्रा करता है और वापस प्रस्थान बिंदु पर लौट आता है।

चुनौती: वैध दौरों (tours) की संख्या फैक्टोरियलली ( $(n-1)!$ ) बढ़ती है, जबकि संभावित शहर अनुक्रमों का कुल खोज स्थान (search space) एक्सपोनेंशियल रूप से ( $(n-1)^{n-1}$ ) बढ़ता है।
संदर्भ: जबकि क्वांटम एल्गोरिदम (जैसे ग्रोवर एल्गोरिदम, QSVT) सुपरपोजीशन-आधारित खोज प्रदान करते हैं, मानक एज-आधारित एनकोडिंग (जो QUBO/Ising मॉडल में उपयोग किए जाते हैं) अक्सर बाधाओं (constraints) को लागू करने में संघर्ष करते हैं। यह शोध पत्र समस्या की क्रमचय संरचना (permutation structure) को स्पष्ट रूप से संभालने के लिए एक रूट-आधारित एनकोडिंग (route-based encoding) प्रस्तावित करता है।

2. कार्यप्रणाली: क्वांटम एनकोडिंग निर्माण (Methodology: Quantum Encoding Construction)

लेखक एक संक्षिप्त क्वांटम सर्किट प्रस्तावित करते हैं जो उम्मीदवार दौरों को शहरों के लेबल के समय-क्रमबद्ध अनुक्रमों (time-ordered sequences) के रूप में एनकोड करता है। यह निर्माण तीन प्राथमिक घटकों से बना है:

A. अवस्था प्रतिनिधित्व (State Representation - Route Register)

एनकोडिंग योजना: किनारों (edges) को एनकोड करने के बजाय, एल्गोरिदम एक टाइम-रजिस्टर प्रतिनिधित्व का उपयोग करता है।
- एक शहर (जैसे, शहर $n-1$ ) को स्टार्ट/एंड पॉइंट के रूप में स्थिर किया जाता है।
- शेष $n-1$ शहरों को एक अनुक्रम $x_1, x_2, \dots, x_T$ के रूप में एनकोड किया जाता है जहाँ $T = n-1$ है।
- प्रत्येक शहर लेबल के लिए $b = \lceil \log_2(n-1) \rceil$ क्यूबिट्स की आवश्यकता होती है।
क्यूबिट गणना: कुल रूट रजिस्टर का आकार $T \times b \approx n \log_2(n)$ क्यूबिट्स है।
प्रारंभिक अवस्था: हैडामार्ड गेट्स का उपयोग करके सभी संभावित $2^{bT}$ बाइनरी स्ट्रिंग्स पर एक समान सुपरपोजीशन $|\psi_{unif}\rangle$ बनाया जाता है। यह शहरों के सभी संभावित अनुक्रमों का प्रतिनिधित्व करता है, जिसमें अमान्य क्रमचय (जहाँ शहर दोहराए गए हैं या छोड़ दिए गए हैं) भी शामिल हैं।

B. वैधता ऑरेकल ( $O_{valid}$ )

वैध दौरों (permutations) को अमान्य असाइनमेंट से अलग करने के लिए एक रिवर्सिबल ऑरेकल का निर्माण किया गया है:

तर्क: एक दौर तभी वैध होता है जब प्रत्येक गैर-स्टार्ट शहर का लेबल अनुक्रम में ठीक एक बार दिखाई देता है।
कार्यान्वयन:
1. पैरिटी एकत्रीकरण (Parity Accumulation): प्रत्येक शहर लेबल $i \in \{0, \dots, n-2\}$ के लिए, एक एंसिला (ancilla) क्यूबिट सभी टाइम स्टेप्स में इसके होने की पैरिटी (parity) को ट्रैक करता है। यह प्रत्येक स्टेप पर $|x_t\rangle$ की तुलना $i$ के बाइनरी एनकोडिंग से करके और संगत एंसिला को फ्लिप करके किया जाता है।
2. फ्लैग जनरेशन: एक अंतिम फ्लैग क्यूबिट को $|1\rangle$ पर सेट किया जाता है यदि और केवल यदि सभी पैरिटी एंसिला विषम गणना (विशेष रूप से, ठीक एक उपस्थिति) दर्शाते हैं। यह एक मल्टी-कंट्रोल्ड X (MCX) गेट के माध्यम से प्राप्त किया जाता है।
जटिलता: इसके लिए $(n-1)^2$ तुलना गेट्स और एक अंतिम MCX गेट की आवश्यकता होती है।

C. लागत ऑरेकल ( $O_{cost}$ )

यह ऑरेकल कुल दौरे की लंबाई को क्वांटम अवस्था के फेज (phase) में एनकोड करता है:

लागत फलन (Cost Function): $L(x) = C_{0,x_1} + \sum_{t=1}^{T-1} C_{x_t, x_{t+1}} + C_{x_T, 0}$ ।
कार्यान्वयन: एज वेट्स के आधार पर कंट्रोल्ड फेज रोटेशन लागू किए जाते हैं।
- स्टार्ट/एंड एडजेस: पहले और अंतिम शहर लेबल द्वारा नियंत्रित।
- मध्यवर्ती एडजेस: आस-पास के जोड़ीदार लेबल $(x_t, x_{t+1})$ द्वारा नियंत्रित।
फेज: अवस्था रूपांतरित होती है: $|x\rangle \to e^{i L(x)/\Lambda}|x\rangle$ , जहाँ $\Lambda$ एक स्केलिंग फैक्टर है (दौरे की लंबाई की ऊपरी सीमा)।

3. मुख्य योगदान (Key Contributions)

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

4. परिणाम और जटिलता विश्लेषण (Results and Complexity Analysis)

शोध पत्र प्रस्तावित एनकोडिंग के लिए संसाधन आवश्यकताओं को मापता है:

मीट्रिक	जटिलता (Complexity)	नोट्स
क्यूबिट्स (Qubits)	$O(n \log_2 n)$	रूट रजिस्टर + पैरिटी और फ्लैग के लिए एंसिला।
CX गेट्स (संख्या)	$O(n^3 \log_2 n)$	कॉस्ट ऑरेकल के मल्टी-कंट्रोल्ड फेज गेट्स द्वारा प्रभावी।
T गेट्स (संख्या)	$O(n^3 (\log_2 n + \log_2(1/\epsilon)))$	फेज रोटेशन के लिए परिशुद्धता $\epsilon$ पर निर्भर करता है।
सर्किट डेप्थ	$O(n^2 \log_2 n)$	विलगित (disjoint) टाइम स्टेप्स पर ऑपरेशन्स को समानांतर (parallelize) करके प्राप्त किया गया।

एम्प्लीफिकेशन सीमाएँ (Amplification Limitations):
लेखक इष्टतम दौर खोजने के लिए एम्प्लीट्यूड एम्प्लीफिकेशन (ग्रोवर एल्गोरिदम) के उपयोग की व्यवहार्यता का विश्लेषण करते हैं:

सफलता की संभावना: सुपरपोजीशन में वैध दौरों का अंश $\frac{(n-1)!}{(n-1)^{n-1}}$ है। स्टर्लिंग के सन्निकटन (Stirling's approximation) द्वारा, यह $\sim e^{-(n-1)}$ के रूप में स्केल करता है।
जटिलता का परिणाम: वैध सबस्पेस को एम्प्लीफाई करने के लिए आवश्यक पुनरावृत्तियों (iterations) की संख्या $O(1/\sqrt{p}) \approx O(e^{(n-1)/2})$ के रूप में स्केल करती है।
निष्कर्ष: क्वांटम स्पीडअप के साथ भी, वैध अवस्थाओं का एक्सपोनेंशियल रूप से छोटा अंश होने के कारण, समग्र जटिलता $n$ के लिए एक्सपोनेंशियल बनी रहती है। यह विधि TSP के लिए बहुपद-समय (polynomial-time) क्वांटम एल्गोरिदम प्रदान नहीं करती है।

5. महत्व और भविष्य की दिशाएं (Significance and Future Directions)

सिमुलेशन के लिए बेसलाइन: इस कार्य का प्राथमिक मूल्य एक स्पष्ट, पुनरुत्पादनीय (reproducible) बेसलाइन एनकोडिंग प्रदान करना है जो छोटे पैमाने के क्वांटम सिमुलेशन और स्पेक्ट्रल फिल्टरिंग तकनीकों (जैसे QSVT) के परीक्षण के लिए उपयुक्त है।
हाइब्रिड रणनीतियाँ: शोध पत्र सुझाव देता है कि हालांकि शुद्ध एम्प्लीट्यूड एम्प्लीफिकेशन अक्षम है, यह एनकोडिंग स्पेक्ट्रल फिल्टरिंग या पॉलीनोमियल फिल्टरिंग विधियों के अनुकूल है, जो अवस्था को सख्ती से वैध सबस्पेस को आइसोलेट करने के बजाय कम-लागत वाले दौरों की ओर झुका सकती है।
भविष्य का कार्य: लेखक निम्नलिखित की आवश्यकता की पहचान करते हैं:
- $O(n^3)$ गेट काउंट को कम करने के लिए अधिक कुशल ऑरेकल निर्माण (जैसे, रिवर्सिबल अरिथमेटिक या ब्लॉक-एनकोडिंग का उपयोग करना)।
- वैकल्पिक एनकोडिंग जो हिल्बर्ट स्पेस में वैध अवस्थाओं के घनत्व को बढ़ाती है।
- लागत फलन और व्यवहार्यता बाधाओं को एक साथ संभालने के लिए स्पेक्ट्रल विधियों (QSCT) का अन्वेषण करना।

संक्षेप में, शोध पत्र TSP के लिए एक सैद्धांतिक रूप से सुदृढ़ लेकिन कम्प्यूटेशनल रूप से महंगी क्वांटम सर्किट प्रस्तुत करता है। यह यह समझने के लिए एक आधारभूत निर्माण खंड (foundational building block) के रूप में कार्य करता है कि कैसे क्वांटम स्पेक्ट्रल विधियाँ अंततः उन कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं से निपट सकती हैं जहाँ समाधान स्थान बहुत विरल (sparse) होता है।