Optimal Quantum Algorithms for Ordered SearchResearch Paper
Finding the first occurrence of a target in a sorted list is a basic comparison problem. Classical binary search uses logarithmically many comparisons. A quantum query can compare a superposition of positions, so the relevant question is how much this changes the coefficient of the logarithm when the answer must be correct with certainty. The held…