I wonder about the effectiveness of the Grover algorithm in real life. In particular, if I think of a number in $\{0,...,2^n -1\}$, is it possible to build a "real" machine that guesses my number (with high probability) in $\sim \sqrt{2^n}$ steps ?
By a "machine", I mean some kind of big box or any complicated device (a particle accelerator, if you desire) that could contain, for example, $n$ entangled qbits, combined with a screen and a two-key keyboard ("yes" and "no") such that
1) the screen displays some number in $\{0,...,2^n -1\}$ and the sentence "is this your number?"
2) the machine waits for a human user to press either of the two keys of the keyboard
3) the machine repeats steps 1), 2) for about $\sqrt{2^n}$ times
4) the screen displays some number in $\{0,...,2^n -1\}$ and the sentence "this is your number".
EDIT : I know the Grover algorithm, the problem I have is about the "nature" of the oracle.
No comments:
Post a Comment