  We present a number of results related to quantum algorithms with small error
probability and quantum algorithms that are zero-error. First, we give a tight
analysis of the trade-offs between the number of queries of quantum search
algorithms, their error probability, the size of the search space, and the
number of solutions in this space. Using this, we deduce new lower and upper
bounds for quantum versions of amplification problems. Next, we establish
nearly optimal quantum-classical separations for the query complexity of
monotone functions in the zero-error model (where our quantum zero-error model
is defined so as to be robust when the quantum gates are noisy). Also, we
present a communication complexity problem related to a total function for
which there is a quantum-classical communication complexity gap in the
zero-error model. Finally, we prove separations for monotone graph properties
in the zero-error and other error models which imply that the evasiveness
conjecture for such properties does not hold for quantum computers.
