Jack Cole wrote: > We show that the spectral gap problem is undecidable. Specifically, > we construct families of translationally-invariant, nearest-neighbor > Hamiltonians on a 2D square lattice of d-level quantum systems > (d constant), for which determining whether the system is gapped or > gapless is an undecidable problem[...]
Interesting issue. I believe it's undecidable if dimension is unbounded. (See - Corollary 8 (Undecidability of spectral gap for unconstrained dimension, in the reference - http://arxiv.org/pdf/1502.04573v2.pdf) I was the first to conjecture the power of adiabatic quantum computation. (See "Adiabatic Quantum Computation & Eigenvalue Gaps" https://groups.google.com/forum/#!msg/comp.theory.dynamic-sys/fdC1qvp_qxw/Vhex2D14A4YJ - and - "Adiabatic Quantum Computation and Search" https://groups.google.com/forum/#!msg/sci.physics.research/9N_-WbzsapI/H4SuchFYf-kJ) - predating anything in Arxiv, so, this is an issue I'm interested in. For finite N-dimensional hamiltonians, (N=2^n where n = # of 'qubits') though, the size of the spectral gap is definitely computable, but takes 'exponential' time (time~2^n) - so is probably 'NP-complete' -- 'n' is effectively the size of the 'classical' system.
