  We study the influence of errors and decoherence on both the performance of
Shor's factoring algorithm and Grover's search algorithm, and on the amount of
interference in these algorithms using a recently proposed interference
measure. We consider systematic unitary errors, random unitary errors, and
decoherence processes. We show that unitary errors which destroy the
interference destroy the efficiency of the algorithm, too. However, unitary
errors may also create useless additional interference. In such a case the
total amount of interference can increase, while the efficiency of the quantum
computation decreases. For decoherence due to phase flip errors, interference
is destroyed for small error probabilities, and converted into destructive
interference for error probabilities approaching one, leading to success
probabilities which can even drop below the classical value. Our results show
that in general interference is necessary in order for a quantum algorithm to
outperform classical computation, but large amounts of interference are not
sufficient and can even lead to destructive interference with worse than
classical success rates.
