ON THE POWER OF QUANTUM COMPUTATION

This paper surveys the use of the 'hybrid argument' to prove that quan tum corrections are insensitive to small perturbations. This property of quantum computations is used to establish that quantum circuits are robust against inaccuracy in the implementation of its elementary gat es. The insensitivity to small perturbations is also used to establish lower-bounds, including showing that relative to an oracle, the class NP requires exponential time on a quantum computer and that quantum a lgorithms are polynomially related to deterministic algorithms in the black-box model.