Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
复制标题

无振幅放大的二维网格上的量子行走搜索

DOI：
10.1007/978-3-642-35656-8_7
复制
发表时间：
2011
期刊：
--
影响因子：
--
通讯作者：
Alexander Rivosh
Alexander Rivosh
中科院分区：
--
文献类型：
--
作者：
A. Ambainis;A. Backurs;N. Nahimovs;Raitis Ozols;Alexander Rivosh

文献摘要

被引文献

相似文献

我们研究了有限二维网格上的量子漫步搜索。Ambainis，Kempe，Rivosh[AKR05]的算法对于大小的网格使用步骤并以概率O(1/logn)找到一个标记位置。这个概率很小，因此[AKR05]需要放大才能得到Θ(1)概率。在本文中，我们证明了，尽管找到标记位置的概率很小，但在标记位置的邻域内(在$O(\Sqrt[4]{N})$距离处)的概率是Θ(1)。这允许跳过幅度放大步骤并导致加速。
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] usessteps and finds a marked location with probabilityO(1 / logN) for grid of size. This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additionalfactor to the number of steps, making it.In this paper, we show that despite a small probability to find a marked location, the probability to be withinneighbourhood (at $O(\sqrt[4]{N})$ distance) of the marked location is Θ(1). This allows to skip amplitude amplification step and leads tospeed-up.