2025-11-28T20:49:18.679046

Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations

Odake, Yoshida, Murao

Recent developments have revealed deterministic and exact protocols for performing complex conjugation, inversion, and transposition of a general $d$-dimensional unknown unitary operation using a finite number of queries to a black-box unitary operation. In this work, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation, which hold even if the input unitary is an unknown logarithmic-depth unitary. Specifically, our lower bound of $d^2$ for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with $O(d^2)$ queries. We introduce a novel framework utilizing differentiation to derive these lower bounds on query complexity for general differentiable functions $f: \mathrm{SU}(d)\to \mathrm{SU}(d)$. As a corollary, we prove that a catalytic protocol -- a new concept recently noted in the study of exact unitary inversion -- is impossible for unitary complex conjugation. Furthermore, we extend our framework to the partially known setting, where the input unitary operation is promised to be within a subgroup of $\mathrm{SU}(d)$ and the probabilistic setting, where transformations succeed probabilistically.

academic

अज्ञात यूनिटरी ऑपरेशन्स के ट्रांसफॉर्मेशन के लिए क्वेरी कॉम्प्लेक्सिटी पर विश्लेषणात्मक निचली सीमा

मूल जानकारी

पेपर ID: 2405.07625
शीर्षक: अज्ञात यूनिटरी ऑपरेशन्स के ट्रांसफॉर्मेशन के लिए क्वेरी कॉम्प्लेक्सिटी पर विश्लेषणात्मक निचली सीमा
लेखक: तात्सुकी ओडाके, सातोशी योशिडा, मियो मुराओ (टोक्यो विश्वविद्यालय)
वर्गीकरण: quant-ph (क्वांटम भौतिकी)
प्रकाशन समय: 27 नवंबर 2025 (संस्करण 4)
पेपर लिंक: https://arxiv.org/abs/2405.07625

सारांश

यह पेपर अज्ञात यूनिटरी ऑपरेशन्स के ट्रांसफॉर्मेशन के लिए क्वेरी कॉम्प्लेक्सिटी की विश्लेषणात्मक निचली सीमा स्थापित करता है। अनुसंधान से पता चलता है कि d-आयामी यूनिटरी ऑपरेशन्स के व्युत्क्रम, ट्रांसपोज़ और जटिल संयुग्म ट्रांसफॉर्मेशन के लिए, भले ही इनपुट यूनिटरी ऑपरेशन लॉगरिदमिक गहराई का क्वांटम सर्किट हो, निश्चित निचली सीमाएं मौजूद हैं। विशेष रूप से, लेखकों ने साबित किया कि यूनिटरी व्युत्क्रम को कम से कम $d^2$ क्वेरीज़ की आवश्यकता है, जो दर्शाता है कि मौजूदा $O(d^2)$ क्वेरी एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम है। पेपर सामान्य अवकलनीय फलन $f: \mathrm{SU}(d)\to \mathrm{SU}(d)$ के लिए क्वेरी कॉम्प्लेक्सिटी निचली सीमा प्राप्त करने के लिए अवकलन-आधारित एक नवीन ढांचा प्रस्तुत करता है, और साबित करता है कि उत्प्रेरक प्रोटोकॉल (catalytic protocol) यूनिटरी जटिल संयुग्म के लिए असंभव है। इसके अतिरिक्त, यह ढांचा आंशिक रूप से ज्ञात और संभाव्य सेटिंग्स तक विस्तारित होता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समाधान की जाने वाली मूल समस्या

यह पेपर अज्ञात यूनिटरी ऑपरेशन्स के ट्रांसफॉर्मेशन की क्वेरी कॉम्प्लेक्सिटी समस्या का अध्ययन करता है: एक ब्लैक-बॉक्स यूनिटरी ऑपरेशन $U \in SU(d)$ दिया गया है, किसी ट्रांसफॉर्मेशन $f(U)$ (जैसे $U^{-1}$ , $U^T$ या $U^*$ ) को लागू करने के लिए $U$ पर कितनी क्वेरीज़ की आवश्यकता है?

समस्या की महत्ता

क्वांटम कंप्यूटिंग मौलिक सिद्धांत: यह क्वांटम सूचना प्रसंस्करण में एक मौलिक समस्या है, जो क्वांटम क्रिप्टोग्राफी में क्वांटम no-cloning प्रमेय की भूमिका के समान है
व्यावहारिक अनुप्रयोग मूल्य:
- दूरस्थ क्वांटम कंप्यूटिंग: विशिष्ट यूनिटरी ऑपरेशन विवरण जाने बिना ट्रांसफॉर्मेशन लागू करना
- क्वांटम नियंत्रण: अवांछित हैमिल्टनियन गतिविज्ञान को समाप्त करने के लिए $U^{-1}$ लागू करना
- क्वांटम सीखना: आउट-ऑफ-टाइम-ऑर्डर सहसंबंध फलन को मापना
- क्वांटम विलक्षण मान परिवर्तन: क्वांटम एल्गोरिदम का मूल घटक

मौजूदा विधियों की सीमाएं

विश्लेषणात्मक निचली सीमा की कमी: यूनिटरी जटिल संयुग्म (निचली सीमा $d-1$ ) और कुछ अरैखिक ट्रांसफॉर्मेशन को छोड़कर, अधिकांश ट्रांसफॉर्मेशन की विश्लेषणात्मक निचली सीमाएं अज्ञात हैं
संख्यात्मक विधियों की सीमा: यूनिटरी व्युत्क्रम और ट्रांसपोज़ के लिए, केवल $d=2$ पर संख्यात्मक निचली सीमाएं (4 के बराबर) उपलब्ध हैं, जो सामान्य आयाम तक विस्तारित करना कठिन है
समानांतर कार्यान्वयन की no-go प्रमेय: मौजूदा no-go प्रमेय केवल समानांतर कार्यान्वयन पर लागू होते हैं, अनुक्रमिक कार्यान्वयन की निचली सीमा अभी भी एक खुली समस्या है
उत्प्रेरक प्रोटोकॉल शर्तें अज्ञात: यह स्पष्ट नहीं है कि कौन से ट्रांसफॉर्मेशन उत्प्रेरक प्रोटोकॉल की अनुमति देते हैं (अर्थात्, पहले चलाने के बाद अधिक कुशलता से दोहराया जा सकता है)

अनुसंधान प्रेरणा

सैद्धांतिक अंतराल भरना: क्वेरी कॉम्प्लेक्सिटी निचली सीमा साबित करने के लिए एक सामान्य विश्लेषणात्मक ढांचा स्थापित करना
एल्गोरिदम इष्टतमता सत्यापित करना: मूल्यांकन करना कि क्या मौजूदा एल्गोरिदम सैद्धांतिक इष्टतम तक पहुंचते हैं
संसाधन आवश्यकताओं को समझना: विभिन्न ट्रांसफॉर्मेशन के लिए आवश्यक क्वांटम संसाधनों को चिन्हित करना
प्रोटोकॉल डिज़ाइन को निर्देशित करना: मौजूदा प्रोटोकॉल में सुधार के लिए सैद्धांतिक मार्गदर्शन प्रदान करना

मुख्य योगदान

सार्वभौमिक सैद्धांतिक ढांचा स्थापित करना: पहली बार सामान्य अवकलनीय फलन $f: \mathrm{SU}(d) \to \mathrm{SU}(d)$ के लिए क्वेरी कॉम्प्लेक्सिटी निचली सीमा के अर्ध-निश्चित प्रोग्रामिंग (SDP) ढांचे के लिए अवकलन-आधारित विधि प्रस्तुत करना
मुख्य निचली सीमाएं साबित करना:
- यूनिटरी व्युत्क्रम: $\geq d^2$ (मौजूदा $O(d^2)$ एल्गोरिदम की स्पर्शोन्मुख इष्टतमता साबित की)
- यूनिटरी ट्रांसपोज़: $\geq 4$ ( $d=2$ ), $\geq d+3$ ( $d\geq 3$ )
- यूनिटरी जटिल संयुग्म: $\geq d-1$ (तंग सीमा)
लॉगरिदमिक गहराई सर्किट की घातीय कठिनाई: साबित करना कि भले ही इनपुट लॉगरिदमिक गहराई के $n$ -क्वबिट यूनिटरी ऑपरेशन तक सीमित हो, ये ट्रांसफॉर्मेशन अभी भी $\exp[\Theta(n)]$ क्वेरीज़ की आवश्यकता है
उत्प्रेरक प्रोटोकॉल की असंभवता: उत्प्रेरक प्रोटोकॉल के अस्तित्व के लिए आवश्यक शर्तें प्रदान करना (प्रमेय 4), साबित करना कि यूनिटरी जटिल संयुग्म और यूनिटरी पुनरावृत्ति के लिए इष्टतम उत्प्रेरक एल्गोरिदम मौजूद नहीं हैं
ढांचा विस्तार:
- आंशिक रूप से ज्ञात सेटिंग: इनपुट यूनिटरी ऑपरेशन $SU(d)$ के किसी उपसमूह से संबंधित है
- संभाव्य सेटिंग: ट्रांसफॉर्मेशन एक निश्चित संभावना के साथ सफल होता है, क्वेरी संख्या और सफलता संभावना के बीच व्यापार-बंद संबंध स्थापित करना

विधि विवरण

कार्य परिभाषा

इनपुट: ब्लैक-बॉक्स यूनिटरी ऑपरेशन $U \in SU(d)$ , जिसे क्वांटम सर्किट में क्वेरी किया जा सकता है (उपयोग किया जा सकता है) $U$

आउटपुट: ट्रांसफॉर्मेशन $f(U)$ लागू करना, जहां $f: SU(d) \to SU(d)$ एक दिया गया फलन है (जैसे $f(U)=U^{-1}$ )

उद्देश्य: $f(U)$ लागू करने के लिए आवश्यक न्यूनतम क्वेरी संख्या $N$ (क्वेरी कॉम्प्लेक्सिटी) खोजना

बाधा शर्तें:

निश्चित और सटीक: सभी $U \in SU(d)$ के लिए $f(U)$ को सटीक रूप से लागू कर सकते हैं
निश्चित क्रम क्वांटम सर्किट: निश्चित क्वांटम सर्किट संरचना (क्वांटम कंघी, quantum comb) का उपयोग करना

मुख्य विधि आर्किटेक्चर

पेपर का मूल नवाचार अवकलन-आधारित अर्ध-निश्चित प्रोग्रामिंग ढांचा है, जिसमें निम्नलिखित चरण शामिल हैं:

1. क्वांटम सर्किट प्रतिनिधित्व (चित्र S1)

$f(U)$ लागू करने वाला कोई भी $N$ -क्वेरी क्वांटम सर्किट इस प्रकार प्रतिनिधित्व किया जा सकता है: $Z(U) := V_{N+1} \prod_{j=1}^N (U \otimes I)V_j$

जहां $V_1, \ldots, V_{N+1}$ निश्चित यूनिटरी ऑपरेशन हैं, $\rho_A = |0\rangle\langle 0|$ सहायक प्रणाली की प्रारंभिक अवस्था है।

2. मुख्य समीकरण व्युत्पत्ति

$U_0$ के पास विक्षोभ $U = e^{i\epsilon H}U_0$ के माध्यम से और $\epsilon$ के संबंध में अवकलन करके, हम प्राप्त करते हैं:

शून्य-क्रम शर्त ( $\epsilon=0$ ): $\tilde{V}_{N+1}(U_0) \prod_{j=1}^N (U_0 \otimes I)V_j [|\psi\rangle \otimes |0\rangle] = |\psi\rangle \otimes |0\rangle$

प्रथम-क्रम शर्त ( $\epsilon$ का अवकलज): $\sum_{s=1}^N \sum_j M_{j,0}^{(s,right)}(U_0)^\dagger H M_{j,0}^{(s,left)}(U_0) = g_{U_0}(H) + \alpha_{U_0}(H)I$

जहां $g_{U_0}$ $U_0$ पर $f$ का अवकलज मानचित्र है: $g_{U_0}(H) := -i \frac{d}{d\epsilon}\Big|_{\epsilon=0} [f(U_0)^{-1}f(e^{i\epsilon H}U_0)]$

3. पूर्ण सकारात्मकता बाधा

रैखिक मानचित्र को परिभाषित करें: $\mathcal{E}_{U_0}(H) = \sum_{s=1}^N \sum_j M_{j,0}^{(s,left)}(U_0)^\dagger H M_{j,0}^{(s,left)}(U_0)$

मुख्य गुण:

$\mathcal{E}_{U_0}(I) = NI$
$\mathcal{E}_{U_0}(H) = g_{U_0}(H) + \alpha_{U_0}(H)I$ for $H \in su(d)$
$\mathcal{E}_{U_0}$ एक पूर्ण सकारात्मक मानचित्र (CP map) होना चाहिए

4. Choi ऑपरेटर और SDP

Choi-Jamiołkowski समरूपता का उपयोग करके, पूर्ण सकारात्मकता शर्त को अर्ध-निश्चित शर्त में परिवर्तित करें: $J_{\mathcal{E}_{U_0}} = J_{g_{U_0}} + \beta_{U_0} \otimes I \geq 0$

जहां Choi ऑपरेटर को परिभाषित किया गया है: $J_{g_{U_0}} := \sum_{j=1}^{d^2-1} G_j^* \otimes g_{U_0}(G_j)$

$\{G_j\}$ $su(d)$ का मानक ऑर्थोनॉर्मल आधार है।

मुख्य प्रमेय (प्रमेय 1)

किसी भी अवकलनीय फलन $f: SU(d) \to SU(d)$ के लिए, क्वेरी कॉम्प्लेक्सिटी निम्नलिखित SDP के समाधान से कम से कम है: