8
$\begingroup$

What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle?

The question is interesting since Grover's algorithm, which for unstructured search on an $N$-element set requires $O(\sqrt{N})$ calls to the oracle, can in fact search a 4-element set using only a single call.

In general, it is interesting to ask for the minimum number of calls to a quantum oracle required to deterministically search an unstructured set of size $N$ for a single marked element.

Note that Grover's algorithm is optimal up to a constant factor in the limit of large $N$, although of course that does not mean it is optimal for any given finite set.

$\endgroup$
3
  • $\begingroup$ Hi Niel. Thanks for your comments. I've edited the question to make clear I'm interested for simplicity in the case of a single marked element, although I did mention this explicitly later in the question. $\endgroup$ – Jamie Vicary Jul 26 '12 at 14:15
  • $\begingroup$ Note also that the question is not merely about the performance of Grover's algorithm. $\endgroup$ – Jamie Vicary Jul 26 '12 at 14:20
  • 2
    $\begingroup$ Grover's algorithm is exactly optimal (not just in the limit of large N). This was shown by Zalka: Grover's quantum searching algorithm is optimal. $\endgroup$ – Robin Kothari Jul 27 '12 at 4:19
6
$\begingroup$

Perhaps a more appropriate for your question: Dong Pyo Chi and Jinsoo Kim showed that for any "Grover-like" algorithm, in which we may change the phase of the diffusion operator and the oracle gate from $-1$ to possibly independent and arbitrary complex phases, a marked element can be found with a single query if and only if there are at least $N/4$ marked items. Here is a link to their article.

Note that the case $t=N/4$ was discovered earlier by Brassard, Boyer, Hoyer and Tapp.

$\endgroup$
2
  • $\begingroup$ Thanks Philippe, that's an interesting different approach. And it's in the spirit of the question, which is not solely about the performance of Grover's algorithm. But still, I don't think it answers the question. $\endgroup$ – Jamie Vicary Jul 27 '12 at 0:48
  • $\begingroup$ Upon reading the linked article, I've suggested an edit which I think better emphasises the result in a way which suggests the importance to the question being asked. $\endgroup$ – Niel de Beaudrap Jul 27 '12 at 19:50
0
$\begingroup$

Lov Grover published an article in 1997 in which he shows that if you can query the database on multiple items, then a single query suffices to find the marked element. However, it requires a number of preprocessing and postprocessing steps in $\Omega(N\log N)$.

If you let $S_1, \dots, S_N$ denote the elements of the database, you query the oracle with the string $S_{i_1}, \dots, S_{i_\eta}$ for some number $\eta$ and the oracle returns $1$ if the marked state appears an odd number of times in the string and $0$ if it appears an even number of times. You query this oracle on a superposition $(|S_1\rangle+ \dots+ |S_N\rangle)^\eta$ and then apply the inversion about the mean operator from Grover's algorithm. Now in each the the $\eta$ subsystems, the marked element has a greater amplitude than the unmarked ones. Measuring all subsystems yield the marked state with greater probability and to have sufficient certitude about the resulting state, $\eta$ must be in $\Omega(N\log N)$.

$\endgroup$
3
  • $\begingroup$ I'm not sure what it means to 'query the database on multiple items'. Ordinary Grover search does this by preparing the input qubit in a superposition of all possible database elements. Is the oracle still of type $\mathbb{C}^n \otimes \mathbb{C}^2 \to \mathbb{C}^n \otimes \mathbb{C}^2$? I guess I should just read the paper... $\endgroup$ – Jamie Vicary Jul 27 '12 at 0:50
  • $\begingroup$ Oh: I think you mean that we're calling our oracle multiple times in parallel. I think that's outside the scope of the question, unless you can show it can be done with a single use of the function $f: N \to \{0,1\}$, if you see what I mean. $\endgroup$ – Jamie Vicary Jul 27 '12 at 0:53
  • $\begingroup$ Actually the oracles considered in the article are yes/no questions about the elements of the database. For example, the oracle could answer the question "is the marked element in the first $N/2$ elements?" or, in this case, "does the marked element appear an odd number of times in this string of elements?" This is just my understanding of it, I read the article quickly yesterday so I might be wrong. $\endgroup$ – lamontap Jul 27 '12 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.