Our work on generalizing Grover’s algorithm to multiple inversion states is finally published!


In Grover’s algorithm, you need to repeated apply two operators, one is the Oracle, and the other is a phase inversion of the state |+++++>, which is a superposition of all possible states.  Although with the Oracle you can invert the phase on many states, for the other operator you can only invert the phase on one and only one state.

What we did here is to generalize this so that you can invert the phase on more than one of the states.  This makes Grover’s algorithm easier to execute in certain cases, and also can speed it up by reducing resources.  Along the way we uncover some neat properties of the Grover Hamiltonian.  Interestingly it shows you can do Grover by not doing Grover at all — using phase estimation instead!  This makes phase estimation a pretty powerful quantum subroutine indeed, you can factor, search, quantum simulate, and more!


Comments are closed.