<p>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 <strong>and only if</strong> there are at least $N/4$ marked items. <a href="http://www.springerlink.com/content/a50j9m6dxld2vlxa/">Here</a> is a link to their article.</p>

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

CC BY-SA 3.0
2012-07-27T00:48:24.220Z
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
CC BY-SA 3.0
2012-07-27T19:50:17.227Z
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
CC BY-SA 3.0
2012-07-26T21:33:56.740Z
2012-07-27T19:47:23.640Z
2012-07-27T19:47:23.640Z
lamontap
<p>Lov Grover published an <a href="http://prl.aps.org/abstract/PRL/v79/i23/p4709_1" rel="nofollow">article</a> 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)$.</p>

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

CC BY-SA 3.0
2012-07-27T00:50:05.060Z
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
CC BY-SA 3.0
2012-07-27T00:53:02.140Z
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
CC BY-SA 3.0
2012-07-27T20:02:18.180Z
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
CC BY-SA 3.0
2012-07-26T21:09:22.410Z
2012-07-26T21:09:22.410Z
lamontap
<p>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?</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-07-26T14:15:40.170Z
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
CC BY-SA 3.0
2012-07-26T14:20:55.220Z
Note also that the question is not merely about the performance of Grover's algorithm.
Jamie Vicary
CC BY-SA 3.0
2012-07-27T04:19:50.307Z
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](http://arxiv.org/abs/quant-ph/9711070).
Robin Kothari
<quantum-computing><quantum-information>
Largest set allowing one-step unstructured quantum search
Jamie Vicary
# Largest set allowing one-step unstructured quantum search

(Asked by: username_0 on 2012-07-26)

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.

**Tags:** quantum-computing, quantum-information

> **Comments:**
> **username_0**: 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.  
> **username_0**: Note also that the question is not merely about the performance of Grover's algorithm.  
> **username_1**: 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](http://arxiv.org/abs/quant-ph/9711070).  

---

## 2 answers

### Answer by username_2 on 2012-07-26. Score: 6 | Accepted answer

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](http://www.springerlink.com/content/a50j9m6dxld2vlxa/) is a link to their article.

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  

---

### Answer by username_2 on 2012-07-26. Score: 0

Lov Grover published an [article](http://prl.aps.org/abstract/PRL/v79/i23/p4709_1) 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)$.

> **Comments:**
> **username_0**: 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...  
> **username_0**: 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.  
> **username_2**: 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.  

---

