Deriving Grover's lower bound from simple physical principles

Understand

Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms.

• Quantum interference between computational paths has been posited as a key resource behind this computational speed-up.
• However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way.
• Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours---currently under experimental investigation---where classical theory is at the first level of the hierarchy and quantum theory belongs to the second.