ECCC-Report TR19-121https://eccc.weizmann.ac.il/report/2019/121Comments and Revisions published for TR19-121en-usTue, 17 Sep 2019 02:55:59 +0300
Paper TR19-121
| Vanishing-Error Approximate Degree and QMA Complexity |
Justin Thaler,
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2019/121The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are $\Theta(n^{2/3} \log^{1/3}(1/\epsilon))$, $\tilde\Theta(n^{3/4} \log^{1/4}(1/\epsilon))$, and $\Theta(n^{1/3} \log^{2/3}(1/\epsilon))$, respectively. Previously, these bounds were known only for constant $\epsilon.$
We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is $\Omega(n^{1/4})$. This improves on the previous best lower bound of $\Omega(n^{1/6})$ due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of $O(n^{1/3})$.Tue, 17 Sep 2019 02:55:59 +0300https://eccc.weizmann.ac.il/report/2019/121