A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the famous Grothendieck constant. A natural question posed there asks if bounded quartic polynomials can be approximated by $2$-query quantum algorithms. Arunachalam, Palazuelos and the first author showed that there is no direct analogue of the result of Aaronson et al. in this case. We improve on this result in the following ways: First, we point out and fix a small error in the construction that has to do with a translation from cubic to quartic polynomials. Second, we give a completely explicit example based on techniques from additive combinatorics. Third, we show that the result still holds when we allow for a small additive error. For this, we apply an SDP characterization of Gribling and Laurent (QIP'19) for the completely-bounded approximate degree.
翻译:与Aaronson等人(CCC'16)的多元量子算法(CCC'16)有惊人的“反差”表明,任何受约束的二次多元量子计算方法都可以完全按照与著名的Grothendieck常数相关的普遍多倍化系数而预期的1号拼算法进行计算。一个自然问题问受约束的二次多元量子算法是否近似于$2美元。Arunachalam、Palazuelos和第一作者表明,在本案中,Aaronson等人的结果没有直接的类比。我们从以下方法改进了这一结果:首先,我们指出并纠正了构造中一个小的错误,这个错误涉及从立方到四面多倍数的翻译。第二,我们给出了一个基于添加组合器组合法技术的完全明确的例子。第三,我们证明当我们允许一个小的添加误差时,结果仍然有效。我们用SDP对Gribling和Laurent(QIP'19)的精确度应用一个完全接近度的SDP特性。