Simulating Arbitrary Pair-Interactions by a Given Hamiltonian: Graph-Theoretical Bounds on the Time Complexity
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.
12 pages
References in corpus (5)
- Conditions for a class of entanglement transformations
- Time Optimal Control in Spin Systems
- Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries
- Efficient implementation of selective recoupling in heteronuclear spin systems using Hadamard matrices
- Characterizing mixing and measurement in quantum mechanics