संभाव्य विधियों के साथ क्वांटम कंप्यूटरों का अनुकरण

हम पारंपरिक और क्वांटम गणनात्मक शक्ति के बीच की सीमा की जांच करते हैं। यह कार्य दो भागों में विभाजित है। पहले, हम नए पारंपरिक अनुकरण एल्गोरिदम विकसित करते हैं जो सैंप्लिंग विधियों पर केंद्रित हैं। इन तकनीकों का उपयोग कर, हम नए वर्ग के पारंपरिक रूप से अनुकरणीय क्वांटम सर्किट उत्पन्न करते हैं, जहां माप की संभावनाओं की सटीक गणना पर आधारित मानक तकनीकें कुशल अनुकरण प्रदान करने में विफल रहती हैं। उदाहरण के लिए, हम दिखाते हैं कि विभिन्न संयुक्तता के मैचगेट, टॉफोली, क्लिफ़ोर्ड, सीमित गहराई, फूरियर ट्रांसफॉर्म और अन्य सर्किट पारंपरिक रूप से अनुकरणीय हैं। हम यह भी साबित करते हैं कि दुर्बल क्वांटम सर्किट और CNOT और i X गेट्स से बने सर्किट पारंपरिक रूप से अनुकरणीय हो सकते हैं। दूसरे भाग में, हम अपने परिणामों को क्वांटम एल्गोरिदम के अनुकरण पर लागू करते हैं। यह दिखाया गया है कि एक हालिया क्वांटम एल्गोरिदम, जो पॉट्स मॉडल विभाजन कार्यों का अनुमान लगाने से संबंधित है, कुशलता से पारंपरिक रूप से अनुकरणीय हो सकता है। अंत में, हम दिखाते हैं कि साइमन और शोर के एल्गोरिदम की निरंतर गति इन एल्गोरिदम में अंतिम चरण पर निर्भर करती है, जो माप परिणामों की पारंपरिक उत्परिवर्तन से संबंधित है। विशेष रूप से, हम साबित करते हैं कि यदि इस चरण में पारंपरिक रूप से गणना की गई फ़ंक्शन का फूरियर स्पेक्ट्रम पर्याप्त रूप से अगल-बगल है, तो दोनों एल्गोरिदम पारंपरिक रूप से अनुकरणीय होंगे.