Reflections for quantum query algorithms

Understand

We show that any boolean function can be evaluated optimally by a quantum query algorithm that alternates a certain fixed, input-independent reflection with a second reflection that coherently queries the input string.

• Originally introduced for solving the unstructured search problem, this two-reflections structure is therefore a universal feature of quantum algorithms.
• Our proof goes via the general adversary bound, a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function.
• By a quantum algorithm for evaluating span programs, this lower bound is known to be tight up to a sub-logarithmic factor.