Speed-ups for Quantum Algorithms with Easier Inputs
When
-
Abstract: The difficulty of solving a problem is often input dependent. For example, if you are searching an unordered list for an item, it is easier to find one if there are multiple copies. Quantum algorithms should also do better on easier inputs, but prior work for an important class of query algorithms only gives an improvement if you know ahead of time that you have an easier input. We designed an algorithm that matches the complexity (up to log factors) of the prior algorithm, but without knowing the difficulty of the input in advance.