  Last years witnessed a remarkable interest in application of quantum
computing for solving problems in quantum chemistry more efficiently than
classical computers allow. Very recently, even first proof-of-principle
experimental realizations have been reported. However, so far only the
non-relativistic regime (i.e. Schroedinger equation) has been explored, while
it is well known that relativistic effects can be very important in chemistry.
In this letter we present the first quantum algorithm for relativistic
computations of molecular energies. We show how to efficiently solve the
eigenproblem of the Dirac-Coulomb Hamiltonian on a quantum computer and
demonstrate the functionality of the proposed procedure by numerical
simulations of computations of the spin-orbit splitting in the SbH molecule.
Finally, we propose quantum circuits with 3 qubits and 9 or 10 CNOTs, which
implement a proof-of-principle relativistic quantum chemical calculation for
this molecule and might be suitable for an experimental realization.
