论文标题
量子参数化复杂性
Quantum Parameterized Complexity
论文作者
论文摘要
参数化的复杂性理论是在1990年代开发的，以丰富取决于一系列参数的问题的复杂性理论分析。在本文中，我们建立了相当于经典参数化复杂性理论的量子，这是由于需要新工具来促进现实世界问题复杂性的分类。我们介绍了一系列参数化复杂性类别的量子类似物，并检查了这些类别，经典对应物和经过充分研究的问题之间的关系。该框架揭示了QMA-硬性问题的参数化版本的复杂性的丰富分类，例如，量子电路的满意度问题与当地的哈密顿量问题之间存在明确的分离。
Parameterized complexity theory was developed in the 1990s to enrich the complexity-theoretic analysis of problems that depend on a range of parameters. 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.
