Vanishing-Error Approximate Degree and QMA Complexity

The $ϵ$-approximate degree of a function $f\text{\hspace{0.17em}⁣}:X\to \{0,1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$forall$x \in X$\mathrm{.}Wedeterminethe$\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 $ϵ\mathrm{.}$ 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 $\mathrm{\Omega }(n^{1\mathrm{/}4})$. This improves on the previous best lower bound of $\mathrm{\Omega }(n^{1\mathrm{/}6})$ due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of $O(n^{1\mathrm{/}3})$.