Parameterized Complexity of Weighted Local Hamiltonian Problems - Xingjian Li | TQC 2023

Xingjian Li Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis http://arxiv.org/abs/2211.05325 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 $latex 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. July 25, 2023 --------- TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal http://tqc-conference.org 18th Conference on the Theory of Quantum Computation, Communication and Cryptography. TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field. Organisation: Squids - Schools for Quantum Information Development Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica Sponsors: Phasecraft, UK Google Quantum AI, USA QuSoft, The Netherlands Quantum for Life Centre, Denmark Technology Innovation Institute, UAE ML4Q, Germany Dulwich Quantum