Abstract:
Nuclear magnetic resonance (NMR) has been widely used as a
demonstrative medium for showcasing the ability for quantum
computations to outperform classical ones. A large number of
such experiments performed have been implementations of the
Deutsch-Jozsa algorithm. It is known, however, that in some cases
the Deutsch-Jozsa problem can be solved classically using as
many queries to the black-box as in the quantum solution. In this
paper we describe experiments in which we take the contrasting
approach of using NMR as a classical computing medium, treating
the nuclear spin vectors classically and utilising an alternative
embedding of bits into the physical medium. This allows us to
determine the actual Boolean function computed by the black-box
for the n = 1, 2 cases, as opposed to only the nature (balanced or
constant) as conventional quantum algorithms do. Discussion of
these experiments leads to some clarification of the complications
surrounding the comparison of different quantum algorithms,
particularly black-box type algorithms.