论文标题
最佳的确切量子算法，用于承诺的元素独特性问题
Optimal exact quantum algorithm for the promised element distinctness problem
论文作者
论文摘要
元素独特性问题是确定字符串$ x =（x_1，\ ldots，x_n）的$ n $元素包含两个相同值的元素（又称碰撞对），Ambainis为此提出了最佳的量子算法。 Ambainis的算法背后的想法是首先将问题减少到承诺的版本中，其中承诺最多包含一个碰撞对，然后设计算法$ \ Mathcal {a} $，需要$ O（n^{2/3}）$ QUERIES $ QUERIES $ QUERIES $ QUERIES $ QUERIES基于量子walk搜索承诺问题。但是，$ \ Mathcal {a} $是概率的，可能无法给出正确的答案。因此，在这项工作中，我们为承诺问题设计了一种精确的量子算法，该算法永远不会犯错，并且需要$ o（n^{2/3}）$查询。该算法被证明是最佳的。从技术上讲，我们将Quasi-Johnson图上的量子步行搜索操作员修改为具有任意阶段，然后使用Jordan的引理作为分析工具，将量子步行搜索操作员减少到广义的Grover的操作员。这使我们能够利用最近提出的固定轴旋转（FXR）方法来精确量子搜索，从而获得100 \％的成功。
The element distinctness problem is to determine whether a string $x=(x_1,\ldots,x_N)$ of $N$ elements contains two elements of the same value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum algorithm. The idea behind Ambainis' algorithm is to first reduce the problem to the promised version in which $x$ is promised to contain at most one colliding pair, and then design an algorithm $\mathcal{A}$ requiring $O(N^{2/3})$ queries based on quantum walk search for the promise problem. However, $\mathcal{A}$ is probabilistic and may fail to give the right answer. We thus, in this work, design an exact quantum algorithm for the promise problem which never errs and requires $O(N^{2/3})$ queries. This algorithm is proved optimal. Technically, we modify the quantum walk search operator on quasi-Johnson graph to have arbitrary phases, and then use Jordan's lemma as the analyzing tool to reduce the quantum walk search operator to the generalized Grover's operator. This allows us to utilize the recently proposed fixed-axis-rotation (FXR) method for exact quantum search, and hence achieve 100\% success.
