论文标题
量子验证的参数化复杂性
The Parameterized Complexity of Quantum Verification
论文作者
论文摘要
我们启动了问题描述中的非克利福德门数的$ \ textsf {qma} $问题的参数化复杂性的研究。我们表明，对于参数化的量子电路的问题，存在一种经典算法，该算法解决了问题，并在非克利福德门的数量中指数缩放，但仅在系统大小上是多条件上的。该结果取决于我们的主要结果，即对于任何Clifford + $ t $ t $ t $ t $ - gate量子电路的满意度问题，最佳证人的搜索空间可以减少为稳定剂亚空间同构，以最多$ t $ Qubits（与系统大小无关）。此外，我们在$ t $ cousd of Criess Explibalibility实例的$ t $ count上得出了新的下限，并假设$ w $ state的$ t $计数假设经典指数时间假设（$ \ textsf {eth et en} $）。最后，我们探讨了量子非身份检查问题的参数化复杂性。
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.
