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]<T[y]$" 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.

  • $\begingroup$ Hi, thanks for your reply. I was just trying to understand the procedure. After you mark them, you then proceed with applying Grover only on the marked kets? And then you mark again, this time the kets that correspond to an element smaller than the new pivot, which means you apply grover on a subset of the one at the previous iteration and so on? $\endgroup$ – Karl Mar 15 '19 at 14:27
  • $\begingroup$ 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". $\endgroup$ – Karl Mar 15 '19 at 14:32
  • $\begingroup$ Well the Grover inversion about average operator is applied on all the kets actually, amplifying the amplitudes of the marked ones. Then you go on with Grover iterations to continue amplifying them to get with high probability a desired one. The outcome of the measurement becomes your new index of minimum. And then you reapply a quantum search but with the new index as input. $\endgroup$ – cnada Mar 15 '19 at 17:01
  • $\begingroup$ 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. $\endgroup$ – cnada Mar 15 '19 at 17:05
  • $\begingroup$ 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? $\endgroup$ – Karl Mar 15 '19 at 17:17

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.