Theory of the Quantum Speed Up
  Insofar as quantum computation is faster than classical, it appears to be irreversible. In all quantum algorithms found so far the speed-up depends on the extra-dynamical irreversible projection representing quantum measurement. Quantum measurement performs a computation that dynamical computation cannot accomplish as efficiently. 
Giuseppe Castagnoli, David Ritz Finkelstein