  We consider quantum computing with pseudo-pure states. This framework arises
in certain implementations of quantum computing using NMR. We analyze quantum
computational protocols which aim to solve exponential classical problems with
polynomial resources and ask whether or not entanglement of the pseudo-pure
states is needed to achieve this aim. We show that for a large class of such
protocols, including Shor's factorization, entanglement is necessary. We also
show that achieving entanglement is not sufficient: if the noise in the state
is sufficiently large, exponential resources are needed even if entanglement is
present.
