Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

Quantum Parameterized Complexity

Michael Bremner, Zhengfeng Ji, Luke Mathieson, Mauro Morales, Alexis Shaw, and I have just uploaded to arXiv our paper "Quantum Parameterized Complexity".

In this paper we establish a quantum equivalent of classical parameterized complexity theory, motivated by the need for new tools for the classifications of the complexity of real-world problems. We introduce the quantum analogues of a range of parameterized complexity classes and examine the relationship between these classes, their classical counterparts, and well-studied problems. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems, demonstrating, for example, a clear separation between the Quantum Circuit Satisfiability problem and the Local Hamiltonian problem.