Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis

摘要

We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight k. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or the particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy, and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.