क्वांटम चरण आकलन एल्गोरिदम

क्वांटम कम्प्यूटिंग में, क्वांटम चरण अनुमान एल्गोरिदम (जिसे क्वांटम आइजेनवैल्यू अनुमान एल्गोरिदम भी कहा जाता है), एक एकात्मक ऑपरेटर के आइजेनवेक्टर के चरण (या आइजेनवैल्यू) का अनुमान लगाने के लिए एक क्वांटम एल्गोरिथ्म है। अधिक सटीक रूप से, एक एकात्मक मैट्रिक्स $U$ और एक क्वांटम अवस्था दी गई है, जिससे कि $|\psi \rangle$ ऐसा है कि $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$, एल्गोरिथम के मूल्य का अनुमान लगाता है $\theta$ के मान का अनुमान लगाता है योगात्मक त्रुटि के भीतर उच्च संभावना के साथ $\varepsilon$ का उपयोग करके $O(\log(1/\varepsilon ))$ क्वैबिट्स (इजेनवेक्टर स्थिति को एन्कोड करने के लिए उपयोग किए जाने वाले क्वैबिट्स की गिनती किए बिना) और $O(1/\varepsilon )$ क्वांटम लॉजिक गेट नियंत्रित-यू संचालन। एल्गोरिदम को शुरुआत में 1995 में एलेक्सी किताएव द्वारा पेश किया गया था।

चरण अनुमान का उपयोग अक्सर अन्य क्वांटम एल्गोरिदम में एक सबरूटीन के रूप में किया जाता है, जैसे कि शोर का एल्गोरिदम, समीकरणों की रैखिक प्रणालियों के लिए क्वांटम एल्गोरिदम, और क्वांटम गिनती एल्गोरिदम।

समस्या

मान लीजिए कि U एक एकात्मक संचालिका है जो एक eigenvalues ​​​​और eigenvectors के साथ m qubit पर काम करता है$|\psi \rangle ,$ ऐसा है कि $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1$.

हम आइजेनवैल्यू और आइजेनवेक्टर ढूंढना चाहेंगे $e^{2\pi i\theta }$का $|\psi \rangle$, जो इस मामले में चरण का अनुमान लगाने के बराबर है $\theta$, परिशुद्धता के एक सीमित स्तर तक। हम eigenvalue को फॉर्म में लिख सकते हैं $e^{2\pi i\theta }$ चूँकि U एक जटिल सदिश समष्टि पर एक एकात्मक संचालिका है, इसलिए इसके eigenvalues ​​​​पूर्ण मान 1 के साथ जटिल संख्याएँ होनी चाहिए।

एल्गोरिदम

क्वांटम चरण आकलन के लिए सर्किट।

सेटअप

इनपुट में दो क्वांटम_रजिस्टर (अर्थात्, दो भाग) होते हैं: ऊपरी $n$ क्वैबिट में पहला रजिस्टर और निचला रजिस्टर शामिल होता है $m$ क्वैबिट दूसरा रजिस्टर है।

सिस्टम की प्रारंभिक स्थिति है:

$|0\rangle ^{\otimes n}|\psi \rangle .$

एन-बिट Hadamard_transform#Hadamard_gate_operations लागू करने के बाद $H^{\otimes n}$ पहले रजिस्टर पर, राज्य बन जाता है:

${\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle$.

होने देना $U$ eigenvector के साथ एकात्मक ऑपरेटर बनें $|\psi \rangle$ ऐसा है कि $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$. इस प्रकार,

$U^{2^{j}}|\psi \rangle =e^{2\pi i2^{j}\theta }|\psi \rangle$.

कुल मिलाकर, क्वांटम_गेट#कंट्रोल्ड_गेट्स द्वारा दो रजिस्टरों पर परिवर्तन लागू किया गया $U,U^{2},U^{2^{2}},\ldots ,U^{2^{n-1}}$ है

$$|k\rangle |\psi \rangle \mapsto |k\rangle U^{k}|\psi \rangle$$

इसे के विघटन द्वारा देखा जा सकता है $k$ इसके बिटस्ट्रिंग में $k_{n-1}k_{n-2}\ldots k_{1}k_{0}$ और बाइनरी संख्या $2^{n-1}k_{n-1}+2^{n-2}k_{n-2}+\ldots +2k_{1}+k_{0}$, कहाँ $k_{n-1},\ldots ,k_{1},k_{0}\in \{0,1\}$. स्पष्ट रूप से, $U^{k}$ बन जाता है

$$U^{2^{n-1}k_{n-1}+\ldots +2^{2}k_{2}+2k_{1}+k_{0}}=U^{2^{n-1}k_{n-1}}\ldots U^{2^{2}k_{2}}U^{2k_{1}}U^{k_{0}}$$

प्रत्येक $U^{2^{j}k_{j}}$ केवल तभी लागू होगा जब qubit $k_{j}$ है $1$, जिसका अर्थ है कि यह उस बिट द्वारा नियंत्रित होता है। इसलिए समग्र परिवर्तन $|k\rangle U^{k}|\psi \rangle$ नियंत्रित के समतुल्य है $U^{2^{j}}$ प्रत्येक से द्वार $j$-वें क्वबिट.

इसलिए, राज्य को नियंत्रित द्वारा बदल दिया जाएगा $U^{2^{j}}$ ऐसे गेट:

$${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle |\psi \rangle$$

इस बिंदु पर, eigenvector के साथ दूसरे रजिस्टर की आवश्यकता नहीं है। चरण आकलन के दूसरे दौर में इसका पुन: उपयोग किया जा सकता है। बिना राज्य $|\psi \rangle$ है

${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle$

व्युत्क्रम क्वांटम फूरियर रूपांतरण लागू करें

व्युत्क्रम क्वांटम फूरियर को लागू करने पर परिवर्तन होता है

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle$ पैदावार

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .$

हम इसके मूल्य का अनुमान लगा सकते हैं $\theta \in [0,1]$ गोल करके $2^{n}\theta$ निकटतम पूर्णांक तक. इस का मतलब है कि $2^{n}\theta =a+2^{n}\delta ,$ कहाँ $a$ के निकटतम पूर्णांक है $2^{n}\theta ,$ और अंतर $2^{n}\delta$ संतुष्ट $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$.

इस अपघटन का उपयोग करके हम स्थिति को इस प्रकार पुनः लिख सकते हैं ${\textstyle \sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$ कहाँ

$c_{x}\equiv {\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}(x-2^{n}\theta )}={\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}.$

माप

पहले रजिस्टर पर कम्प्यूटेशनल आधार पर क्वांटम यांत्रिकी में माप करने से परिणाम मिलता है $|y\rangle$ संभाव्यता के साथ

$$\Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.$$

यह इस प्रकार है कि $\operatorname {Pr} (a)=1$ अगर $\delta =0$, तभी $\theta$ के रूप में लिखा जा सकता है $\theta =a/2^{n}$, व्यक्ति को हमेशा परिणाम मिलता है $y=a$. दूसरी ओर, यदि $\delta \neq 0$, संभावना पढ़ती है

$$\operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.$$

इस अभिव्यक्ति से हम यह देख सकते हैं $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$ कब $\delta \neq 0$. इसे देखने के लिए हम इसे की परिभाषा से देखते हैं $\delta$ हमारे यहां असमानता है $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$, और इस तरह:

$$n$$