In the final remark Zalka's paper about the proof of exact optimality of Grover's algorithm for the search problem with a single marked state, we have the following suggestion for future work:

"I have here only considered oracles with the promise that there is exactly one marked element. It seems very plausible that the proof can be extended to oracles with any known(!) number of marked elements".

Has this already been done? Be it a generalization of Zalka's proof or even a different proof. I'm trying to find it, but so far, nothing.

  • 1
    $\begingroup$ Since you have found your answer, instead of editing it into the question, you should put it as an answer and accept it. $\endgroup$
    – FDGod
    Oct 7, 2023 at 22:10

1 Answer 1


I found it. For anyone interested, it's the Lemma 2 from Hamann Dunjko and Wölk paper


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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