本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我們引入了一種量子演算法，用於對經典記憶隨機過程產生的罕見事件進行記憶體有效的偏置採樣。使用兩個效率指標來比較罕見事件採樣的量子資源和經典資源。對於固定隨機過程，第一個是所需記憶體的經典與量子比率。我們透過兩個範例過程證明，對於任何大實數 r，存在無限數量的罕見事件類，其採樣記憶體比率大於 r。然後，對於每個由整數大小 N 標記的製程序列，我們比較經典和量子所需的記憶體如何與 N 縮放。在這種設定中，由於兩個記憶體可以發散為 N -> 無窮大，因此效率指標追蹤它們發散的速度。當經典記憶體在極限 N -> 無限大時發散，但量子記憶體具有有限界限時，就存在極端的量子記憶體優勢。然後，我們證明有限狀態馬可夫過程和自旋鏈在幾乎所有罕見事件類別的採樣方面都表現出記憶體優勢。