论文标题
加权当地哈密顿问题的参数化复杂性和量子指数时间假设
Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
论文作者
论文摘要
我们研究了当地汉密尔顿问题的参数化版本，称为加权当地的哈密顿问题，其中相关的量子状态是hamming权重$ k $的计算基础状态的叠加。锤子的重量约束可以将物理解释作为对系统中允许的激发数量的限制或系统中的粒子数量的限制。我们证明了这个问题在QW [1]中，这是量子纬度层次结构的第一级，对于QM [1]，M [1]的量子类似物很难[1]。我们的结果表明，除非指数时间假设（ETH）的某些自然量子类似物（eth）是错误的，否则这个问题不能是固定参数量子术（FPQT）。
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 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.
