We analyze the effects of quantum correlations, such as entanglement and discord, on the efficiency of phase estimation by studying four quantum circuits that can be readily implemented using NMR techniques. These circuits define a standard strategy of repeated single-qubit measurements, a classical strategy where only classical correlations are allowed, and two quantum strategies where nonclassical correlations are allowed. In addition to counting space (number of qubits) and time (number of gates) requirements, we introduce mixedness as a key constraint of the experiment. We compare the efficiency of the four strategies as a function of the mixedness parameter. We find that the quantum strategy gives enhancement over the standard strategy for the same amount of mixedness. This result applies even for highly mixed states that have nonclassical correlations but no entanglement.
