Bounds on the number of time steps for simulating arbitrary interaction graphs

Abstract

In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for general simulations. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.

12 pages, 3 figures, some corrections of Theorem 1 and its proof

References in corpus (9)

• Quantum error-correcting codes associated with graphs
• Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries
• Universal simulation of Hamiltonian dynamics for qudits
• Optimal simulation of two-qubit Hamiltonians using general local operations
• Efficient Refocussing of One Spin and Two Spin Interactions for NMR Quantum Computation
• Graphs, Quadratic Forms, and Quantum Codes
• Quantum computing via measurements only
• Simulating Hamiltonians in Quantum Networks: Efficient Schemes and Complexity Bounds
• Complexity of decoupling and time-reversal for n spins with pair-interactions: Arrow of time in quantum control