Quantum Approximation Complexity of Classical Optimization Problems

शीर्षक: शास्त्रीय अनुकूलन समस्याओं की क्वांटम सन्निकटन जटिलता (Quantum Approximation Complexity of Classical Optimization Problems)
लेखक: स्टुअर्ट हैडफील्ड (Stuart Hadfield)

समस्या विवरण

यह शोध पत्र क्वांटम अनुकूलन एल्गोरिदम के लिए कठोर 'वर्स्ट-केस' (worst-case) प्रदर्शन गारंटी के अभाव को संबोधित करता है। जबकि कई क्वांटम विधियाँ (जैसे QAOA, DQI) विशिष्ट उदाहरणों पर उच्च स्कोर प्रदर्शित करती हैं या अपेक्षित मानों (decoded means) पर सीमाएँ प्रदान करती हैं, उनमें अक्सर ऐसे समान (uniform) एल्गोरिदम का अभाव होता है जो प्रत्येक इनपुट के लिए एक निश्चित सन्निकटन अनुपात (approximation ratio) और सीमित त्रुटि (bounded error) की गारंटी दे सकें। यह कार्य क्वांटम गणना के माध्यम से शास्त्रीय सन्निकटन जटिलता वर्गों (APX, PTAS, FPTAS) के क्वांटम समकक्षों को औपचारिक रूप से परिभाषित करने और यह निर्धारित करने का प्रयास करता है कि क्या क्वांटम गणना, गारंटीकृत समाधान की गुणवत्ता या वांछित सटीकता प्राप्त करने के लिए आवश्यक समय के संदर्भ में रैंडमाइज्ड (randomized) शास्त्रीय एल्गोरिदम से सख्ती से बेहतर हो सकती है।

कार्यप्रणाली (Methodology)

लेखक बाउंडेड-एरर (bounded-error) क्वांटम एल्गोरिदम को शामिल करने के लिए NP ऑप्टिमाइज़ेशन (NPO) समस्याओं के ढांचे का विस्तार करता है।

1. क्वांटम वर्गों की परिभाषा: शोध पत्र BQ-APX, BQ-PTAS, और BQ-FPTAS को परिभाषित करता है। इन वर्गों की सदस्यता के लिए एक समान (uniform) क्वांटम एल्गोरिदम की आवश्यकता होती है जो, प्रत्येक इनपुट पर, कम से कम $2/3$ की प्रायिकता के साथ दावा किया गया सन्निकटन अनुपात प्राप्त करने वाला एक व्यवहार्य शास्त्रीय समाधान लौटाता है। महत्वपूर्ण रूप से, रनिंग टाइम में सभी चरण शामिल हैं: पैरामीटर चयन, स्टेट तैयारी, मापन (measurement), डिकोडिंग और पुनरावृत्ति (repetition)। समाधान का स्कोर शास्त्रीय रूप से कुशलतापूर्वक गणनीय होना चाहिए।
2. डिकोडेड-मीन से आउटपुट स्थानांतरण: लेम्मा 6 और कोरोलरी 7 एक प्रमुख तकनीकी उपकरण के रूप में कार्य करते हैं, जो डिकोड किए गए समाधान के अपेक्षित स्कोर और एक बाउंडेड-एरर शास्त्रीय आउटपुट गारंटी के बीच संबंध स्थापित करते हैं। यह अपेक्षा-आधारित विश्लेषणों (जो क्वांटम साहित्य में सामान्य हैं) को उन सख्त आउटपुट गारंटियों में अनुवादित करने की अनुमति देता है जो क्लास सदस्यता के लिए आवश्यक हैं।
3. सशर्त पृथक्करण (Conditional Separations): पेपर विशिष्ट समस्याओं का निर्माण करता है ताकि मानक जटिलता धारणाओं (जैसे $NP \not\subseteq BQP$ और $Factor \notin FBPP$) के तहत क्वांटम और शास्त्रीय वर्गों के बीच सख्त समावेशन को प्रदर्शित किया जा सके। ये निर्माण "सर्च पैडिंग" (search padding) और क्रिप्टोग्राफिक हार्डनेस पर आधारित हैं।

प्रमुख योगदान और परिणाम

1. क्वांटम सन्निकटन वर्गों का औपचारिक पदानुक्रम (Formal Hierarchy)
शोध पत्र $NP \not\subseteq BQP$ की धारणा के तहत क्वांटम सन्निकटन वर्गों के लिए एक सख्त पदानुक्रम स्थापित करता है:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
यह पदानुक्रम शास्त्रीय समस्याओं द्वारा प्रमाणित है:

• Max-E3SAT: एक नियतात्मक (deterministic) कॉन्स्टेंट-रेशियो सन्निकटन (APX में) रखता है लेकिन कोई क्वांटम PTAS नहीं रखता।
• Planar Vertex Cover: एक नियतात्मक PTAS रखता है लेकिन कोई क्वांटम FPTAS नहीं रखता।
  ये परिणाम दिखाते हैं कि क्वांटम वर्ग एक-दूसरे से भिन्न हैं, हालांकि वे अभी भी इन विशिष्ट समस्याओं के लिए क्वांटम को रैंडमाइज्ड शास्त्रीय वर्गों से अलग नहीं करते हैं।

2. सर्टिफाइड मैक्सिमम ऑर्डर (CMO): एक मजबूत क्वांटम-शास्त्रीय पृथक्करण
पेपर सर्टिफाइड मैक्सिमम ऑर्डर (CMO) समस्या को पेश करता है, जहाँ लक्ष्य $N$ के मॉड्यूल में किसी तत्व के मल्टीप्लिकेटिव ऑर्डर को खोजना है, जो ऑर्डर के अभाज्य गुणनखंड (prime factorization) द्वारा प्रमाणित हो।

• क्वांटम परिणाम: एक बाउंडेड-एरर क्वांटम एल्गोरिदम फैक्टरिंग और पीरियड फाइंडिंग का उपयोग करके पॉलीनोमियल समय में सटीक ऑप्टिमम (Carmichael function $\lambda(N)$) पा सकता है। अतः, $CMO \in BQ\text{-}FPTAS$ है।
• शास्त्रीय बाधा: कोई भी रैंडमाइज्ड पॉलीनोमियल-टाइम एल्गोरिदम जो CMO के लिए कम से कम पॉलीनोमियल-फैक्टर सन्निकटन की गारंटी देता है, वह रैंडमाइज्ड पॉलीनोमियल-टाइम फैक्टरिंग एल्गोरिदम को सिद्ध कर देगा।
• निष्कर्ष: $Factor \notin FBPP$ की धारणा के तहत, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$ है। यह एक सशर्त पृथक्करण स्थापित करता है जहाँ क्वांटम एल्गोरिदम सटीक समाधान प्रदान करते हैं जबकि रैंडमाइज्ड शास्त्रीय एल्गोरिदम पॉलीनोमियल-फैक्टर सन्निकटन तक भी प्राप्त नहीं कर सकते।

3. डिस्क्रीट-लॉगारिदम फिटिंग (DLog-Fit): एक थ्रेशोल्ड पृथक्करण
पेपर DLog-Fit को परिभाषित करता है, जो डिस्क्रीट लॉगरिदम के आधार पर एक सैंपल पर लेबल की भविष्यवाणी करने वाली एक समस्या है।

• शास्त्रीय बेसलाइन: एक नियतात्मक एल्गोरिदम $1/2$-सन्निकटन प्राप्त करता है (बहुमत लेबल की भविष्यवाणी करना)।
• क्वांटम लाभ: एक क्वांटम एल्गोरिदम एक परफेक्ट फिट (सटीक ऑप्टिमम) पा सकता है।
• शास्त्रीय बाधा: $1/2$ अनुपात में रैंडमाइज्ड शास्त्रीय एल्गोरिदम द्वारा किया गया कोई भी निश्चित सुधार से सेफ-प्राइम सबग्रुप में डिस्क्रीट लॉगरिदम समस्या हल हो जाएगी।
• निष्कर्ष: इस धारणा के तहत कि सेफ-प्राइम डिस्क्रीट लॉगरिदम $FBPP$ में नहीं है, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$ है। यह $1/2$ सन्निकटन थ्रेशोल्ड पर एक अंतर को प्रदर्शित करता है।

4. सामान्य सर्च पैडिंग (Theorem 8)
पेपर एक जेनेरिक निर्माण प्रदान करता है जो दिखाता है कि किसी भी सर्च समस्या को, जिसके पास कुशलतापूर्वक सत्यापन योग्य साक्ष्य (witnesses) हैं, उसे एक NPO समस्या में बदला जा सकता है जिसमें $1/2$ सन्निकटन थ्रेशोल्ड हो। यदि कोई क्वांटम सॉल्वर सर्च के लिए मौजूद है लेकिन रैंडमाइज्ड शास्त्रीय सॉल्वर नहीं है, तो परिणामी अनुकूलन समस्या $BQ\text{-}FPTAS$ में होगी लेकिन $R\text{-}PTAS$ से बाहर होगी।

5. मौजूदा क्वांटम विधियों का विश्लेषण
पेपर मौजूदा एल्गोरिदम पर इन परिभाषाओं को लागू करता है:

• QAOA: 3-रेगुलर MaxCut के लिए फिक्स्ड-डेप्थ QAOA के लिए, पेपर डिकोडेड-मीन ट्रांसफर का उपयोग करके यह दिखाने के लिए कि पुनरावृत्ति एक बाउंडेड-एरर आउटपुट गारंटी (जैसे, ऑप्टिमम के $2/3$ से अधिक) दे सकती है, इस विशिष्ट ग्राफ परिवार को $BQ\text{-}APX$ में रखता है।
• डिस्कोडेड क्वांटम इंटरफेरोमेट्री (DQI): पेपर नोट करता है कि जबकि DQI विशिष्ट परिवारों (जैसे फोल्डेड OPI) पर बेहतर अपेक्षित स्कोर दिखाता है, स्पष्ट-इनपुट समय मॉडल में पृथक्करण स्थापित करने के लिए यह सिद्ध करना आवश्यक है कि रैंडमाइज्ड शास्त्रीय एल्गोरिदम समान अनुपात प्राप्त नहीं कर सकते, जो कि अनियंत्रित समस्याओं के लिए एक खुला प्रश्न बना हुआ है।

महत्व और दावे

पेपर का दावा है कि यह बाउंडेड-एरर क्वांटम सन्निकटन वर्गों के लिए पहले कठोर परिभाषाएँ प्रदान करता है और यह सिद्ध करता है कि, स्पष्ट जटिलता धारणाओं के तहत, क्वांटम गणना रैंडमाइज्ड शास्त्रीय गणना की तुलना में वर्स्ट-केस सन्निकटन गारंटी में सख्ती से सुधार कर सकती है।

• सीमित दायरा: लेखक स्पष्ट रूप से कहता है कि MaxCut या MaxSAT जैसी सामान्य, अनियंत्रित समस्याओं के लिए, वर्स्ट-केस आउटपुट रेश्यो में क्वांटम-शास्त्रीय अंतर अभी भी खुला (open) है। स्थापित पृथक्करण विशिष्ट, अक्सर क्रिप्टोग्राफिक, समस्या निर्माण (CMO, DLog-Fit) या प्रतिबंधित ग्राफ परिवारों पर निर्भर करते हैं।
• सैद्धांतिक ढांचा: यह कार्य ह्यूरिस्टिक क्वांटम प्रदर्शन (जो अक्सर एक्सपेक्टेशन वैल्यू द्वारा मापा जाता है) और कठोर जटिलता सिद्धांत (बाउंडेड-एरर आउटपुट गारंटियाँ) के बीच के अंतर को पाटता है। यह स्पष्ट करता है कि केवल उच्च बेंचमार्क स्कोर, यूनिफॉर्मिटी और रनटाइम बाउंड्स के बिना, सन्निकटन क्लास सदस्यता स्थापित नहीं करते हैं।
• भविष्य की दिशा: पेपर पहचान करता है कि एक समान क्वांटम एल्गोरिदम की खोज जो मानक समस्याओं (जैसे अनरिस्ट्रिक्टेड MaxCut) के लिए शास्त्रीय हार्डनेस थ्रेशोल्ड से बेहतर अनुपात की गारंटी देता है, क्षेत्र में केंद्रीय खुला प्रश्न है।