Determinstic Grover's Algorithm: Finding the Needle in the Haystack Every Time … Well Most Times

Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sqrt{N}$</tex> searches as opposed to the best classical algorithm, which requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N/2$</tex> [1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N=4$</tex>, drops to 87% for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N=7$</tex>, is near 100% for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N=9$</tex>, and is below 94% for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N=15$</tex>. This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.