论文标题
如何从连续时间量子步行的限制分布中采样
How to Sample From The Limiting Distribution of a Continuous-Time Quantum Walk
论文作者
论文摘要
我们介绍了$ \ varepsilon $ -Projectors，我们可以通过限制连续时间量子步行的分布来对其进行采样。来自与给定量子步行的限制分布的分布采样的标准算法是在一个大间隔内随机选择的量子步行，并测量所得量子状态。这种方法通常会导致指数运行时间。 我们表明，使用$ \ varepsilon $ -Projectors，我们可以从限制分布中精确采样。在黑框设置中，我们只能查询对图的邻接矩阵的访问，我们的采样算法的时间与$δ^{ - 1} $成正比，其中$δ$是图表的独特特征值之间的最小间距。在非黑色框设置中，我们提供了图形的示例，其算法的运行速度比标准采样算法更快。
We introduce $\varepsilon$-projectors, using which we can sample from limiting distributions of continuous-time quantum walks. The standard algorithm for sampling from a distribution that is close to the limiting distribution of a given quantum walk is to run the quantum walk for a time chosen uniformly at random from a large interval, and measure the resulting quantum state. This approach usually results in an exponential running time. We show that, using $\varepsilon$-projectors, we can sample exactly from the limiting distribution. In the black-box setting, where we only have query access to the adjacency matrix of the graph, our sampling algorithm runs in time proportional to $Δ^{-1}$, where $Δ$ is the minimum spacing between the distinct eigenvalues of the graph. In the non-black-box setting, we give examples of graphs for which our algorithm runs exponentially faster than the standard sampling algorithm.
