#

### 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`

and

Justin Thaler

Department of Computer Science

Georgetown University

Washington DC

`justin DOT thaler AT georgetown DOT edu`

*June 30, 2023*
#### 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.

Volume 2023, Article 2
Volume 2024 Article 1
---->

Volume 2023
Published articles