Scott Aaronson

A long-standing open problem in quantum complexity theory is whether QMA has perfect completeness, i.e. whether any QMA verifier can be made to have completeness $c=1$. Previous constructions have yielded a completeness parameter exponentially close to 1. We improve this to doubly-exponentially close to 1. Additionally, we show that QMA has perfect completeness if one allows the verifier an infinite-dimensional (witness) space. We show that this can be achieved using a gate set which is such that the ability to use an infinite-dimensional space does not increase the computational power of QMA. We also show that when using a finite-dimensional space of polynomially many qubits, a completeness doubly-exponentially close to 1 is optimal among black-box constructions. We show that the soundness can at most be made exponentially small using black-box reductions.

Abstract Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~deg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. D(f) = O(Q(f)^4): The deterministic query complexity of f is at most quartic in the quantum query complexity of f. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if f is a nontrivial monotone graph property of an n-vertex graph specified by its adjacency matrix, then Q(f)=Omega(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Theta(sqrt{n}).