Vanishing-Error Approximate Degree and QMA Complexity

Understand

The $\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})$.