current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|cite|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

After discussing the problem with some people from my institute that work on quantum computing, it turns out that one can augment the oracle to not provide elements that have already been found in previous iterations of the search. The trick is to modify Grover's algorithm as follows:

Say, we already know that 2 is an answer (from a previous iteration). After using the oracle to invert the phase of the marked elements within Grover's algorithm, we apply another operation that inverses the phase of the known answers again (thus cancelling the previous inversion for answers that are already known). Accordingly, the inversion about the mean in Grover's algorithm will not amplify the amplitude of these states.

share|cite|improve this answer
up vote 1 down vote

This approach suffers from a couple of problems. First of all, Grover's algorithm in its usual form depends on the fact that there is exactly one good item in the search space, so you'll need to modify it to account for the fact that there are now several.

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.

You ought to think about whether you really need to do that, though. You're working with a probabilistic algorithm anyway, so it probably wouldn't hurt to get the same answer twice a few times.

share|cite|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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