Implementing the Deutsch-Jozsa algorithm with macroscopic ensembles

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.

Figure 1

The Deutsch-Jozsa algorithm. (a) The function $f\left(x\right)$ which determines the oracle. (b) The quantum circuit for the Deutsch-Jozsa algorithm. The gates marked by $H$ are Hadamard gates, $U_f$ is the oracle, and the meter symbols denote a measurement in $S^Z$ basis. The labeling of the qubits and ensembles for $n\in [0,M]$ is shown.

Figure 2

The probability $p^{\left(m\right)}$ of remaining in the initial state $|{\psi }_{\text{init}}\rangle$ after evolving with a Hamiltonian $\pi {\prod }_{n=1}^m{S}_n^Z$, as defined in (82). (a) $m=1$ with $N_1=N$ as marked. (b) $m=1$ on a logarithmic scale with $N_1=N$ as marked (solid lines), with the approximation (86) (dashed lines). (c) $m=2$ with $N_1=N_2=N$ as marked. (d) $m=3$ with $N_1=N_2=N_3=N$ as marked.

Figure 3

Error probabilities as defined in (95). This corresponds to the probability for the measurement yielding $|{\psi }_{\text{init}}\rangle$ for a balanced function for various order terms, after the first-order term is applied. (a), (b) The second-order error probability $m=2$ for $N_1=20$ and $N_2$ as marked. (c) The third-order error probability $m=3$, for $N_1=20$ and $N_2,N_3$ as marked. (d) The second $m=2$ at time $\tau =1/2N$ and third $m=3$ error probabilities at time $\tau =1/2N^2$ as a function of the particle number $N$. The particle numbers are set as marked, and $N_1=N$.