Limitations on the simulation of non-sparse Hamiltonians

Abstract

The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.

v1: 12 pages. v2: 15 pages; strengthened main result

References in corpus (4)

• Exponential algorithmic speedup by quantum walk
• On the relationship between continuous- and discrete-time quantum walk
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Quantum algorithms for hidden nonlinear structures

Cited by in corpus (7)

• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Quantum Speed-ups for Semidefinite Programming
• Double-bracket quantum algorithms for diagonalization
• Braiding quantum gates from partition algebras
• Local invariants of braiding quantum gates -- associated link polynomials and entangling power
• Double-bracket algorithm for quantum signal processing without post-selection
• Efficient quantum circuits for dense and non-unitary operators