solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3113次
Element Distinctness Revisited. (arXiv:1711.11336v1 [quant-ph])
来源于:arXiv
The element distinctness problem is the problem of determining whether the
elements of a list are distinct. Classically, it requires $N$ queries, where
$N$ is the number of elements. In the quantum case, it is possible to solve the
problem in $O(N^{2/3})$ queries. The problem can be extended by asking whether
there are $k$ colliding elements, known as element $k$-distinctness.
This work obtains optimal values of two critical parameters of Ambainis'
seminal algorithm [\textit{SIAM Journal on Computing}, 37(1):210-239, 2007].
The first critical parameter is the number of repetitions of the algorithm's
main block, which inverts the phase of the marked elements and calls a
subroutine. The second parameter is the number of quantum walk steps interlaced
by oracle queries. We show that, when the optimal values of the parameters are
used, the algorithm's success probability is $1-O(N^{1/(k+1)})$, quickly
approaching to 1. 查看全文>>