The Parametrized Complexity of Quantum Verification
| Autor: | Arunachalam, Srinivasan, Bravyi, Sergey, Nirkhe, Chinmay, O'Gorman, Bryan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Quantum Physics Computer Science - Computational Complexity Computer Science::Emerging Technologies Theory of computation → Quantum computation theory FOS: Physical sciences parametrized complexity QMA Computational Complexity (cs.CC) Quantum Physics (quant-ph) quantum verification |
| DOI: | 10.4230/lipics.tqc.2022.3 |
| Popis: | 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. LIPIcs, Vol. 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), pages 3:1-3:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|