Vanishing-Error Approximate Degree and QMA Complexity

Abstract

The $\epsilon$-approximate degree of a function $f:X\to \{0,1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)|\le \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})$.

Cited by in corpus (4)

• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
• Improved Approximate Degree Bounds For k-distinctness
• Quantum Proofs of Proximity
• The Acrobatics of BQP