2024-11-12
Grothendieck inequalities characterize converses to the polynomial method
Publication
Publication
Quantum , Volume 8
A surprising ‘converse to the polynomial method’ of Aaronson et al. (CCC’16) shows that any bounded quadratic polynomial can be computed exactly in expec- tation by a 1-query algorithm up to a universal multiplicative factor related to the famousGrothendieckconstant. Hereweshowthatsucharesultdoesnotgeneralize 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.
Additional Metadata | |
---|---|
doi.org/10.22331/q-2024-11-18-1526 | |
Quantum | |
Marie Skłodowska-Curie , Networks | |
Organisation | Algorithms and Complexity |
Briët, J., Escudero Gutiérrez, F., & Gribling, S. (2024). Grothendieck inequalities characterize converses to the polynomial method. Quantum, 8. doi:10.22331/q-2024-11-18-1526 |