  In the study of open quantum systems, one typically obtains the decoherence
dynamics by solving a master equation. The master equation is derived using
knowledge of some basic properties of the system, the environment and their
interaction: one basically needs to know the operators through which the system
couples to the environment and the spectral density of the environment. For a
large system, it could become prohibitively difficult to even write down the
appropriate master equation, let alone solve it on a classical computer. In
this paper, we present a quantum algorithm for simulating the dynamics of an
open quantum system. On a quantum computer, the environment can be simulated
using ancilla qubits with properly chosen single-qubit frequencies and with
properly designed coupling to the system qubits. The parameters used in the
simulation are easily derived from the parameters of the system+environment
Hamiltonian. The algorithm is designed to simulate Markovian dynamics, but it
can also be used to simulate non-Markovian dynamics provided that this dynamics
can be obtained by embedding the system of interest into a larger system that
obeys Markovian dynamics. We estimate the resource requirements for the
algorithm. In particular, we show that for sufficiently slow decoherence a
single ancilla qubit could be sufficient to represent the entire environment,
in principle.
