2001/06/13 by P. Wocjan, Paweł Wocjan, Wocjan, P. +6 · 1 citation
Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Quantum Mechanics and Applications #advanced mathematical theories #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0106077
12 pages
arxiv created 2001/06/13 · arxiv updated 2009/12/01
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.