Amplitude amplification

Amplitude amplification, as developed by Brassard, Høyer, Mosca, and Tapp, takes a quantum procedure that produces a "good" outcome with probability a and a check that recognizes good outcomes. Using that procedure and its inverse on the order of 1/√a times raises the success probability to a constant. Classically, repeating the procedure would take on the order of 1/a trials.

Grover's algorithm is the special case in which the procedure prepares the uniform superposition and the check is the search oracle. The same paper also estimates the unknown probability a, which is the amplitude-estimation half of the title. The quadratic improvement is optimal in the black-box sense already proved for search: amplification does not outrun the query-complexity lower bound. It relocates Grover's idea to any procedure you can run forwards and backwards. HHL uses it on a postselection whose success probability is on the order of 1/κ², so that on the order of κ repetitions replace on the order of κ² naive repetitions. That count is a use of the subroutine, not a new search bound.