The Phase Matrix

Reducing the error of quantum algorithms is often achieved by applying a primitive called amplitude amplification. Its use leads in many instances to quantum algorithms that are quadratically faster than any classical algorithm. Amplitude amplification is controlled by choosing two complex numbers

φ

s

and

φ

t

of unit norm, called phase factors. If the phases are well-chosen, amplitude amplification reduces the error of quantum algorithms, if not, it may increase the error. We give an analysis of amplitude amplification with a emphasis on the influence of the phase factors on the error of quantum algorithms. We introduce a so-called phase matrix and use it to give a straightforward and novel analysis of amplitude amplification processes. We show that we may always pick identical phase factors

φ

s

=

φ

t

with argument in the range

${{\pi}\over{3}}{\leq} {\rm arg}(\phi_{s}){\leq} {\pi}$

. We also show that identical phase factors

φ

s

=

φ

t

with

$-{{\pi}\over{2}}< {\rm arg}(\phi_{s})< {{\pi}\over{2}}$

never leads to an increase in the error, generalizing a recent result of Lov Grover who shows that amplitude amplification becomes a quantum analogue of classical repetition if we pick phase factors

φ

s

=

φ

t

with

${\rm arg}(\phi_{s}) = {{\pi}\over{3}}$

.