Report
The Parameterized Complexity of Quantum Verification
| العنوان: | The Parameterized Complexity of Quantum Verification |
|---|---|
| المؤلفون: | Arunachalam, Srinivasan, Bravyi, Sergey, Nirkhe, Chinmay, O'Gorman, Bryan |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity |
| الوصف: | We initiate the study of parameterized complexity of $\textsf{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 ($\textsf{ETH}$). Lastly, we explore the parameterized complexity of the quantum non-identity check problem. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4230/LIPIcs.TQC.2022.3 |
| URL الوصول: | http://arxiv.org/abs/2202.08119 |
| رقم الانضمام: | edsarx.2202.08119 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4230/LIPIcs.TQC.2022.3 |
|---|