Nuclear magnetic resonance (NMR) is well-suited to implement quantum algorithms experimentally. However, there are serious problems associated with the noisy mixed initial state that is described by the thermal equilibrium density operator of NMR spectroscopy. Here we present a new strategy to dramatically increase the sensitivity of a NMR quantum computing experiment. Para hydrogen can be used to prepare a density operator in a suitable molecule that is very close to a pure state, an improvement on the order of 10(4) compared to "conventional" NMR quantum computing. Our strategy is demonstrated experimentally solving the Deutsch-Jozsa problem based on para hydrogen and Vaska's complex.