Durr and Hoyer's: A Quantum Algorithm for Finding the Minimum

I'm trying to understand this algorithm: arXiv:quant-ph/9607014 and I already have a problem on page 1, when they say that initializing the memory and "marking the elements $$j$$ such that $$T[j]" can be achieved in $$O(\log N)$$ steps. How is checking every singe element and marking it run in less than $$O(N)$$ steps? And also: is this step meant to restrict the set of states to which we apply Grover's algorithm? Can we simply forget about some kets and run it on some others?

Well, the idea is simple. You have at first a superposition of N indexes where $$N=2^n$$. So basically you are doing your operations on $$n$$ qubits, so they are $$\log_2(N)$$ in complexity. The oracle used for marking the states is just called once and is applied on about $$n$$ qubits, which marks the states where the output of the oracle is 1 (the one whose values are greater in this case).
The last questions you asked, if you mean to apply it on a subset of states in the superposition (often because we have $$N$$ which is not a power of 2, it is possible indeed. You can keep the states and do your quantum search with an oracle that will not mark them.
• Also, in order to find the actual minimum I would expect to need $O(\log(N))$ steps in which I reduce the search set by "marking". – Karl Mar 15 at 14:32
• Quantum search requires the application of $O(\sqrt(N))$ iterations of the oracle and inversion about average operator to yield a result with a probability higher than 0.5. So is this algorithm. The marking of better indexes is logarithmic. – cnada Mar 15 at 17:05
• Exactly, the marking of new indexes is logarithmic, so in my view you basically run Grover $O(\log(N))$ times, but Grover itself takes $O(\sqrt{N})$ so in my view a naive time estimate would be $O(\sqrt{N}\log(N))$. Is this wrong? – Karl Mar 15 at 17:17