Performance requirements for ensemble implementations of quantum algorithms

We consider the statistical performance of quantum algorithms when implemented on ensemble quantum computers. In particular we consider an ensemble quantum computer initially in a pseudo-pure initial state and determine the minimum polarization needed so that the quantum algorithm outperforms classical probabilistic competitors. We propose a general method for finding the minimum polarization and apply it to single bit output algorithms such as the Deutsch-Jozsa algorithm and the multiple output bit Grover search algorithm.