Chicago Journal of Theoretical Computer Science

Volume 2023

Article 3

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

Vanishing-Error Approximate Degree and QMA Complexity

Alexander A. Sherstov
Computer Science Department
University of California Los Angeles
Los Angeles, CA
sherstov AT cs DOT ucla DOT edu


Justin Thaler
Department of Computer Science
Georgetown University
Washington DC
justin DOT thaler AT georgetown DOT edu

June 30, 2023


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

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

DOI: 10.4086/cjtcs.2023.002

[] Volume 2023, Article 2 [] Volume 2024 Article 1 ---->
[back] Volume 2023 [back] Published articles
[CJCTS home]