Published by the Department of Computer Science, The University of Chicago.

Abstract

The ε-approximate degree of a function $f\colon X \to $∞ 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 ε-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})$.

• The article: PDF (257 KB)
• Source material: ZIP (97 KB)
• BibTeX entry for this article (290 bytes)

Submitted February 20, 2020, revised April 16, 2022, published June 30, 2023.

© 2023 Alexander Sherstov and Justin Thaler
Licensed under a Creative Commons Attribution License

Volume 2023, Article 2

Volume 2024 Article 1

Volume 2023

Published articles