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

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

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

समस्या

मान लीजिए कि U एक एकात्मक संचालिका है जो एक आइगेनवैल्यू ​​​​और आइजन्वेक्टर के साथ m क्वैबिट पर काम करता है$|\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$ में परिशुद्धता के एक सीमित स्तर तक चरण का अनुमान लगाने के सामान है। हम आइगेनवैल्यू को इस रूप में लिख सकते हैं, $e^{2\pi i\theta }$ क्योंकि U एक सम्मिश्र सदिश समष्टि पर एक एकात्मक संचालिका है इसलिए इसके आइगेनवैल्यू ​​​​पूर्ण मान 1 के साथ सम्मिश्र संख्याएँ होनी चाहिए।

एल्गोरिदम

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

स्थापित करना

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

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

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

एन-बिट पहले रजिस्टर पर एन-बिट हैडामर्ड गेट संचालिका लागू करने के बाद $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$ आइजन्वेक्टर के साथ एकात्मक संचालिका $|\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}}$ केवल तभी लागू होगा जब क्वैबिट $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$$

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