शोर का एल्गोरिथ्म: QFT के परिणाम को दो बार पढ़ने के बाद क्या करना है?
मैंने फूरियर ट्रांसफॉर्म प्लॉट को देखने की अवधि की पहचान करने के बारे में पूछा । ऐसा लगता है कि उत्तर पुस्तिका द्वारा वर्णित उच्च संभावनाओं से जुड़े कई मान प्राप्त करने के लिए कई बार फूरियर रूपांतरण को चलाने के लिए लगता है। तो अभी भी उसी चित्र का उपयोग करते हुए, मान लें कि मैंने इसे दो बार पढ़ा और मुझे मान मिला। 5> और | 11> | ये उच्चतम स्पाइक्स हैं (पहले उच्चतम में 0 के बाद। क्या आप गणना का उदाहरण दिखा सकते हैं?
एक समाधान का प्रयास किया । पीटर शोर का पेपर पढ़ना (पृष्ठ 320 पर), हम पाते हैं कि उनके$q$ है $q=64$हमारे उदाहरण में। शोर कह रहा है हम एक अंश प्राप्त कर सकते हैं$d/r$ सबसे कम शब्दों में (जहां) $r = 12$ यहाँ) गोलाई से $c/q$ किसी निकटतम से छोटे होने वाले निकटतम अंश तक $n=35$यहां। हमारा संभव है$c$ यहाँ है $5$ तथा $11$।
चलो कोशिश करते हैं कि। QFT के बाद, हम मिल गए$c = 5$ और हमारे पास है $q = 64$। तो हम प्राप्त करते हैं$5/64 = 0.078125$ और हम एक छोटे से कम हर पास वाले अंश के लिए उसे गोल करना चाहते हैं $35$। के लिये$5/64$, मैं निरंतर अंश ढूँढता हूँ $[0,12,1,4]$। (मैंने जाँच की कि$5/64 = 1/(12 + 1/(1 + 1/4))$, तो यह सही है।) अब, इस जारी अंश से (सूची रूप में) मुझे भिन्नों के निम्नलिखित अनुक्रम मिलते हैं: $1/4, 5/4, 64/5, 5/64$। (मुझे यकीन नहीं है कि मैं क्या कर रहा हूं।) शायद$5$क्या बुरा है? लेकिन, नहीं, एक ही बात के साथ कोशिश कर रहा है$11$ का उत्पादन भी करेगा $11/64$। भले ही मुझे पता है कि निरंतर अंश एल्गोरिथ्म की गणना कैसे की जाती है, मुझे नहीं पता कि इसके साथ क्या करना है। मुझे लगता है कि हार्डी और राइट, अध्याय X को देखना होगा।
जवाब
यह विकिपीडिया पर चरण 5 का एल्गोरिथ्म का जारी अंश है। आपने जो नापा है$y$ ऐसा है कि $\frac{yr}{Q}\approx c$, कहां है $c$ कुछ अज्ञात पूर्णांक है, $r$ छिपी अवधि (इस मामले में 12) है, और $Q=64$QFT का आकार है। इस का मतलब है कि$\frac{y}{Q}\approx \frac{c}{r}$। के लिये$y=5$, अपने पास $\frac{5}{64}\approx \frac{1}{12}$, और किसके लिए $y=11$, अपने पास $\frac{11}{64}\approx \frac{2}{12}$। तो यह मापा मूल्यों और अवधि के बीच संबंध है।
हम वास्तव में उन मूल्यों से अवधि कैसे पाते हैं, हालांकि (क्योंकि हम नहीं जानते हैं $c$ या $r$)? निरंतर अंशों के साथ। एक संख्या के लिए एक निरंतर अंश$x$ के साथ पुनरावर्ती परिभाषित किया गया है $a_0=x$, फिर साथ $b_n=\lfloor a_n\rfloor$, तथा $a_n=\frac{1}{a_{n-1}-b_{n-1}}$। के साथ इस समस्या के लिए आवेदन किया$x=\frac{5}{64}$, अपने पास
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
इससे हम सन्निकटन को फिर से संगठित कर सकते हैं, और इन सन्निकटनों का हरकारण काल होगा। सतत भिन्न संख्याओं पर विकिपीडिया पृष्ठ है कि हम लगभग अंशों की एक श्रृंखला मिल बताते हैं$\frac{h_n}{k_n}$, जहां हम एक अंश निर्धारित करते हैं $h_n=b_nh_{n-1}+h_{n-2}$ और भाजक $k_n=b_nk_{n-1}+k_{n-2}$प्रारंभिक मूल्यों के साथ $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, तथा $k_{-2}=1$। यह दो क्रम देता है:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
जो तीन अनुमानित अंश देता है: $\frac{1}{12}$, $\frac{1}{13}$, तथा $\frac{5}{64}$। आखिरी वह है जो हमने शुरू किया था और बेकार है क्योंकि 64 बहुत बड़ा है (अवधि 35 से कम होनी चाहिए, आखिरकार)। पहला एक वास्तविक अवधि है।
मैं निरंतर अंशों के बारे में ज्यादा नहीं जानता, लेकिन मुझे लगता है कि ये अनुमान मूल अंश में बहुत तेज़ी से परिवर्तित होते हैं। तो व्यवहार में, मुझे लगता है कि आप बस प्रत्येक भाजक को लगभग भिन्न भिन्न के अनुक्रम में जांचेंगे (इस मामले में, 12 और 13 दोनों) क्योंकि (ए) ऐसा नहीं होना चाहिए कि कई अनुमानित अंश, और (बी) शोर के अंतिम चरण एल्गोरिथ्म बहुत सस्ती हैं।