论文标题
马尔可夫链的量子近似计数和对碰撞计数的应用
Quantum Approximate Counting for Markov Chains and Application to Collision Counting
论文作者
论文摘要
在本文中，我们展示了如何概括由Brassard，Høyer和Tapp [ICALP 1998]开发的量子近似计数技术到更通用的环境：估计马尔可夫链的明显状态数（马尔可夫链可以看作是在具有加权边缘的图形上的随机步行）。这使得基于Magniez，Nayak，Roland和Santha建立的强大的“基于量子步行的搜索”框架，从量子搜索算法中构建量子近似计数算法[SIAM Journal on Computing 2011]。作为应用程序，我们将这种方法应用于Ambainis的量子元素独特性算法[Siam Journal on Computing 2007]：对于一组$ n $元素的两个注射功能，我们通过在相对错误$ε$中估算两个功能的数字$ m $ M $ M $，从$ \ tilde {o} \ left（\ frac {1} {ε^{25/24}} \ big（\ frac {n} {\ sqrt {\ sqrt {m}} \ big） $θ\ big（\ frac {1}ε\ frac {n} {\ sqrt {m}}} \ big）$ - 当$ m \ ll n $时，基于随机采样时查询经典算法。
In this paper we show how to generalize the quantum approximate counting technique developed by Brassard, Høyer and Tapp [ICALP 1998] to a more general setting: estimating the number of marked states of a Markov chain (a Markov chain can be seen as a random walk over a graph with weighted edges). This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha [SIAM Journal on Computing 2011]. As an application, we apply this approach to the quantum element distinctness algorithm by Ambainis [SIAM Journal on Computing 2007]: for two injective functions over a set of $N$ elements, we obtain a quantum algorithm that estimates the number $m$ of collisions of the two functions within relative error $ε$ by making $\tilde{O}\left(\frac{1}{ε^{25/24}}\big(\frac{N}{\sqrt{m}}\big)^{2/3}\right)$ queries, which gives an improvement over the $Θ\big(\frac{1}ε\frac{N}{\sqrt{m}}\big)$-query classical algorithm based on random sampling when $m\ll N$.
