# Largest set allowing one-step unstructured quantum search

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.

• 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. – Jamie Vicary Jul 26 '12 at 14:15
• Note also that the question is not merely about the performance of Grover's algorithm. – Jamie Vicary Jul 26 '12 at 14:20
• 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. – Robin Kothari Jul 27 '12 at 4:19

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.

• 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. – Jamie Vicary Jul 27 '12 at 0:48
• 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. – Niel de Beaudrap Jul 27 '12 at 19:50

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)$.

• 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... – Jamie Vicary Jul 27 '12 at 0:50
• 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. – Jamie Vicary Jul 27 '12 at 0:53
• 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. – lamontap Jul 27 '12 at 20:02