Michael J. Bremner

dblp:162/0103 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2025
0000-0001-7240-4686ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2025 Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
abstract
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.
Michael J. Bremner, Zheng-Feng Ji, Xingjian Li 0006, Luke Mathieson, Mauro E. S. Morales
ACM Trans. Quantum Comput.1