Abstract

Parameterized complexity theory is a flourishing area that enriches complexity-theoretic analysis of problems that depend on a range of parameters. 

In this talk, we discuss a quantum equivalent of classical parameterized complexity theory, motivated by the need for new tools for classifying the complexity of real-world problems. After briefly introducing the basic definitions, we study the complexity of the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight k. We show 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 analog of M[1]. 

Our results show that this problem cannot be fixed-parameter quantum tractable (FPQT) unless a natural quantum analog of the exponential time hypothesis (ETH) is false. 

Time

2023-06-18  09:00 - 09:30   

Speaker

Zhengfeng Ji, Tsinghua University

Room

Guangdong Hotel