论文标题
Grothendieck的不平等表征与多项式方法的对话
Grothendieck inequalities characterize converses to the polynomial method
论文作者
论文摘要
Aaronson等人的一个令人惊讶的“与多项式方法交谈”。 （CCC'16）表明，任何有界的二次多项式都可以通过1 Query算法准确地计算出与著名的Grothendieck常数有关的通用乘法因子。在这里，我们表明，即使我们允许加性近似值，这种结果也不会推广到四分之一的多项式和2 Query算法。我们还表明，对界的双线性形式所隐含的结果所隐含的添加剂近似是紧密的，这从1 Query量子算法方面给出了Grothendieck常数的新表征。在此过程中，我们提供了形式的完全有限规范及其双重规范的重新制定。
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. Here we show that such a result does not generalize to quartic polynomials and 2-query algorithms, even when we allow for additive approximations. We also show that the additive approximation implied by their result is tight for bounded bilinear forms, which gives a new characterization of the Grothendieck constant in terms of 1-query quantum algorithms. Along the way we provide reformulations of the completely bounded norm of a form, and its dual norm.
