Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity

Abstract

We consider a quantum computer consisting of n spins with an arbitrary but fixed pair-interaction Hamiltonian and describe how to simulate other pair-interactions by interspersing the natural time evolution with fast local transformations. Calculating the minimal time overhead of such a simulation leads to a convex optimization problem. Lower and upper bounds on the minimal time overhead are derived in terms of chromatic indices of interaction graphs and spectral majorization criteria. These results classify Hamiltonians with respect to their computational power. For a specific Hamiltonian, namely \sigma_z\otimes\sigma_z-interactions between all spins, the optimization is mathematically equivalent to a separability problem of n-qubit density matrices. We compare the complexity defined by such a quantum computer with the usual gate complexity.