2026-07-22T10:56:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16510 2024-03-06T10:57:42Z ddc:004 open_access

The Parametrized Complexity of Quantum Verification Arunachalam, Srinivasan Bravyi, Sergey Nirkhe, Chinmay O'Gorman, Bryan parametrized complexity quantum verification QMA We initiate the study of parameterized complexity of QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + t T-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most t qubits (independent of the system size). Furthermore, we derive new lower bounds on the T-count of circuit satisfiability instances and the T-count of the W-state assuming the classical exponential time hypothesis (ETH). Lastly, we explore the parameterized complexity of the quantum non-identity check problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Sergey Bravyi and Chinmay Nirkhe and Bryan O'Gorman 2022 Is Part Of LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2022.3 urn:nbn:de:0030-drops-165104 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.3 eng https://creativecommons.org/licenses/by/4.0/legalcode