2022-07-04
On converses to the polynomial method
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4230/LIPIcs.TQC.2022.6 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Networks , Marie Skłodowska-Curie | |
| 17th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2022 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Briët, J., & Escudero Gutiérrez, F. (2022). On converses to the polynomial method. In Conference on the Theory of Quantum Computation, Communication and Cryptography (pp. 6:1–6:10). doi:10.4230/LIPIcs.TQC.2022.6 |
|
