Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity (pp117-132)
        Pawel Wocjan, Dominik Janzing, and Thomas Beth
          doi: https://doi.org/10.26421/QIC2.2-2
Abstracts: 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.
Key words: simulating pair-interactions, quantum control theory, quantum complexity, graph sectra, chromatic index