Maximum Speedup in Quantum Search: O(1) Running Time

We consider the running time of the generalized quantum search Hamiltonian. We provide the surprising result that the maximum speedup of quantum search in the generalized Hamiltonian is an O(1) running time regardless of the number of total states. This seems to violate the proof of Zalka that the quadratic speedup is optimal in quantum search. However the argument of Giovannetti et al. that a quantum speedup comes from the interaction between subsystems (or, equivalently entanglement) (and is concerned with the Margolus and Levitin theorem) supports our result.