ピーク浅量子回路の古典的シミュレーション

n-क्विबिट क्वांटम सर्किट को पीक्ड कहा जाता है यदि इसका आउटपुट संभाव्यता कम से कम इनवर्स-पॉलीनोमियल रूप से n के एक फ़ंक्शन के रूप में बड़ी होती है। हम एक क्लासिकल एल्गोरिदम का वर्णन करते हैं जिसमें लगभग पॉलीनोमियल रनटाइम nO(logn) है जो पीक्ड कॉन्स्टेंट-डेप्थ सर्किट के आउटपुट वितरण से अनुमानित सैंपल करता है। हम D-आयाम के क्विबिट्स के निकटतम-पड़ोस गेट्स से युक्त सर्किट्स के लिए और भी तेज़ एल्गोरिदम देते हैं, जिसमें पॉलीनोमियल रनटाइम nO(1) है यदि D=2 और लगभग-पॉलीनोमियल रनटाइम nO(loglogn) है यदि D>2। हमारे सैंपलिंग एल्गोरिदम का उपयोग shallow circuits की आउटपुट संभावनाओं का अनुमान लगाने के लिए दिया गया है जिसके साथ किसी दिए गए इनवर्स-पॉलीनोमियल ऐडिटिव त्रुटि के भीतर, जो पहले से ज्ञात तरीकों में सुधार करता है। एक सरल अनुप्रयोग के रूप में, हम shallow circuit के आउटपुट राज्य में किसी भी पाउली ऑब्जर्वेबल के अपेक्षित मूल्य के परिमाण का अनुमान लगाने के लिए एक क्वासिपॉलीनोमियल एल्गोरिदम प्राप्त करते हैं (जो पीक्ड हो सकता है या नहीं)। यह पिछले अत्याधुनिक एल्गोरिदम की तुलना में एक नाटकीय सुधार है जिसमें √n में एक गुणात्मक वृद्धि थी।