论文标题
与多项式方法对话
On converses to the polynomial method
论文作者
论文摘要
Aaronson等人的一个令人惊讶的“与多项式方法交谈”。 （CCC'16）表明，任何有界的二次多项式都可以通过1 Query算法准确地计算出与著名的Grothendieck常数有关的通用乘法因子。那里提出的一个自然问题询问是否可以通过$ 2 $ Query-Query量子算法将有限的四分之一多项式近似。 Arunachalam，Palazuelos和第一作者表明，Aaronson等人的结果没有直接的类似物。在这种情况下。我们通过以下方式对此结果进行了改进：首先，我们指出并修复了构造中的微小误差，这与从立方到四分之一的多项式的翻译有关。其次，我们根据添加剂组合学的技术给出了一个完全明确的示例。第三，我们表明，当我们允许出现小的加性错误时，结果仍然存在。为此，我们将Gribling和Laurent（QIP'19）的SDP表征应用于完全结合的近似程度。
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.
