# Finding all marked elements using Grover's algorithm

Grover's algorithm uses an oracle function $f(x) \to \{0,1\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an assignment I am supposed to design a variant of the algorithm that finds all of the $t$ marked elements ($t$ is known). I want to do this by repeating the following procedure $t$-times:

1. Use Grover's algorithm to find any marked element $x$.
2. Delete $x$ from the data base.

I think my solution is correct, but I am still not feeling comfortable with quantum computing. In particular, I am unsure of how one could implement the removal step since it would mean to manipulate the function $f$.

Can anyone clarify?

• I'm not at all an expert in quantum computing, but it seems to me that Grover's algorithm won't give you just one answer if you have $t$ element such that $f(x)=1$. – wece Jul 30 '13 at 15:06
• I didn't read all of this but it can give you some good intuition I think katzgraber.org/teaching/FS08/files/solca.pdf – wece Jul 30 '13 at 15:21
• @wece: Actually, you get a super-position of the t answers. But it collapses to one particular answer if measured. – Michael Nett Jul 31 '13 at 2:02

Second of all, you ought to justify whether or not you can easily delete arbitrary elements from the database. The oracle function $f$ need not be (indeed probably won't be) a literal lookup in a literal database. One good example might be an $f$ that tells you whether $x$ is a factor of $N$ for some $x$ and $N$ integers. You can't just stop $x$ from being a factor of $N$ once you find it, but you might well be able to use $f$ to manufacture a new function that tells you when $y$ is a factor of $N$ that is not $x$. If you can come up with a function that flips the $x$ component of the state, then you can just do $f$, which flips the $x$ component, and then flip it back, to get the desired modified indicator.
• There's a variant of Grover's Algorithm that works if $t$ elements are marked; that's not the problem. I was thinking of obtaining a super-position of all $t$ solutions and then manipulating the superposition exclude, say $2$, if we already know that $2$ is a marked element from previous applications of GA. Do you think that would work? – Michael Nett Aug 1 '13 at 4:38
• I don't off the top of my head see how to exclude $2$, but if you could then that seems like it would work. – Ben Millwood Aug 1 '13 at 11:13