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

Learn about parameterized complexity in quantum computing through a conference talk presented at the 18th Theory of Quantum Computation Conference (TQC 2023). Explore the weighted local Hamiltonian problem, where quantum states are constrained by specific Hamming weights, and understand its implications for quantum complexity theory. Delve into the proof that this problem belongs to QW[1] while being hard for QM[1], and examine how these findings relate to fixed-parameter quantum tractability and the quantum exponential time hypothesis. Follow along as the speaker covers classical complexity theory, quantum parameterized complexity, quantum circuits, sparse Hamiltonians, and presents detailed proof sketches with lower bounds. Gain insights into how Hamming weight constraints can represent physical limitations like excitation numbers or particle counts in quantum systems.