Classical Simulability of Dissipative Interactions of Fermions

It is widely accepted that the efficient classical simulability of free-fermion dynamics is not robust under elastic interactions. We examine how the classical simulability of fermions that are initially noninteracting changes in the presence of purely dissipative Markovian interactions described by quadratic Lindblad jump operators, including, for example, incoherent transitions or pair losses. On the one hand, we establish three broad classes of Markovian dynamics that are efficiently simulable classically, by devising efficient algorithms. On the other hand, we demonstrate that, in the worst case, simulating Markovian dynamics with quadratic Lindblad jump operators is at least as hard as simulating universal quantum circuits. To prove this result, we propose a practical scheme for universal quantum computation in cold atom systems using natural pair loss, which is of independent interest. Our proposed scheme of dissipation-assisted quantum computing might have significant advantages in the speed of two-qubit gates and, therefore, in error tolerance.