  Quantum computing implementations under consideration today typically deal
with systems with microscopic degrees of freedom such as photons, ions, cold
atoms, and superconducting circuits. The quantum information is stored
typically in low-dimensional Hilbert spaces such as qubits, as quantum effects
are strongest in such systems. It has however been demonstrated that quantum
effects can be observed in mesoscopic and macroscopic systems, such as
nanomechanical systems and gas ensembles. While few-qubit quantum information
demonstrations have been performed with such macroscopic systems, a quantum
algorithm showing exponential speedup over classical algorithms is yet to be
shown. Here we show that the Deutsch-Jozsa algorithm can be implemented with
macroscopic ensembles. The encoding that we use avoids the detrimental effects
of decoherence that normally plagues macroscopic implementations. We discuss
two mapping procedures which can be chosen depending upon the constraints of
the oracle and the experiment. Both methods have an exponential speedup over
the classical case, and only require control of the ensembles at the level of
the total spin of the ensembles. It is shown that both approaches reproduce the
qubit Deutsch-Jozsa algorithm, and are robust under decoherence.
