Simulating Arbitrary Pair-Interactions by a Given Hamiltonian: Graph-Theoretical Bounds on the Time Complexity

Preprint

13 June 2001

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.quant-ph/0106077

Abstract

We use an n-spin system with permutation symmetric zz-interaction for simulating arbitrary pair-interaction Hamiltonians. The calculation of the required time overhead is mathematically equivalent to a separability problem of n-qubit density matrices. We derive lower and upper bounds in terms of chromatic index and the spectrum of the interaction graph. The complexity measure defined by such a computational model is related to gate complexity and a continuous complexity measure introduced in a former paper. We use majorization of graph spectra for classifying Hamiltonians with respect to their computational power.

Keywords

ARBITRARY PAIR INTERACTION
SIMULATING ARBITRARY PAIR
INTERACTION HAMILTONIANS
BOUNDS ON THE TIME
PERMUTATION
GRAPH

All Related Versions

Version 1, 2001-06-13, ArXiv

This publication has 0 references indexed in Scilit: