1
Return

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

delete2025-09-16
delete0
PRE
AI
M
Michael J. Bremner
Z
Zhengfeng Ji
X
Xingjian Li
L
Luke Mathieson
M
Mauro E. S. Morales
DOI：10.1145/3759156delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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.

Journal

A
ACM Transactions on Quantum Computing
IF:
6.8
Papers:
539
Citations:
508

Organization

No organization information available
Cited Papers

Cited Papers

Citing Papers

Citing Papers