Unlocking Quantum Complexity: Weighted Local Hamiltonian Problems & the Quantum Exponential Time Hypothesis 🔍

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