Engineers from JPMorgan have found a method to improve Grover’s algorithm.
Their innovation leads to a performance improvement because it removes, “X gates from the inversion-by-the-mean step in the standard Grover iterate that is used in search, amplitude estimation, counting, and other quantum algorithms that offer a quadratic speedup over the classical counterparts.“
This optimization serves two purposes: from a practical perspective, it can lead to a performance improvement; from a theoretical one, it leads to a novel interpretation of the actual nature of this step. This step is a reflection, which is realized by (a) cancelling the superposition of a general state to revert to the original all-zeros state, (b) flipping the sign of the amplitude of the all-zeros state, and finally (c) reverting back to the superposition state.
Rather than canceling the superposition, their approach allows for going forward to another state that makes the reflection easier.
They have validated this approach on set and array search, and confirm their results experimentally on real quantum hardware.
The paper can be read there.
