4
$\begingroup$

I need some hint on how to adapt grover's algorithm to search the minimum in a database with $N=2^n$ elements in $O(\sqrt{N}\log(N))$ queries with probability of success $\geq 2/3$. I know I can do it by basically choosing randomly a "pivot" and then applying Grover to find a number smaller than that, then update my pivot. But is there something more to it?

$\endgroup$
5
$\begingroup$

There is an algorithm by Dürr and Høyer that seems to solve your problem. This algorithm finds the correct answer in $\mathcal{O}(\sqrt{N})$ time with probability $1/2$.

The crux is that they have an oracle which flips the phase of all states with a smaller value than the currently selected one.

$\endgroup$
  • $\begingroup$ I have seen that, but it's overkill. I am looking for something more naive. $\endgroup$ – Karl Mar 14 at 14:33
  • 1
    $\begingroup$ @Karl What do you mean by more naive? $\endgroup$ – cnada Mar 14 at 14:59

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.