Quantum Parameterized Complexity
| Title: | Quantum Parameterized Complexity |
|---|---|
| Authors: | Bremner, Michael J., Ji, Zhengfeng, Mann, Ryan L., Mathieson, Luke, Morales, Mauro E. S., Shaw, Alexis T. E. |
| Publication Year: | 2022 |
| Collection: | Computer Science Quantum Physics |
| Subject Terms: | Quantum Physics, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms |
| More Details: | 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. Comment: 23 pages, 1 figure |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2203.08002 |
| Accession Number: | edsarx.2203.08002 |
| Database: | arXiv |
| Description not available. |