Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
| Title: | Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis |
|---|---|
| Authors: | Bremner, Michael J., Ji, Zhengfeng, Li, Xingjian, Mathieson, Luke, Morales, Mauro E. S. |
| Publication Year: | 2022 |
| Collection: | Computer Science Quantum Physics |
| Subject Terms: | Computer Science - Computational Complexity, Quantum Physics |
| More Details: | 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. Comment: 37 pages, 10 figures |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2211.05325 |
| Accession Number: | edsarx.2211.05325 |
| Database: | arXiv |
| Description not available. |