LIPIcs.TQC.2022.6.pdf
- Filesize: 0.63 MB
- 10 pages
Document
On Converses to the Polynomial Method
Authors
-
Part of:
Volume:
17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-07-04
File
Document Identifiers
Acknowledgements
We want to thank Srinivasan Arunachalam, Sander Gribling and Carlos Palazuelos for useful discussions. We also want to thank the referees of TQC for their helpful comments.
Cite AsGet BibTex
Jop Briët and Francisco Escudero Gutiérrez. On Converses to the Polynomial Method. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.TQC.2022.6
https://doi.org/10.4230/LIPIcs.TQC.2022.6
Abstract
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Functional analysis
- Theory of computation → Quantum complexity theory
Keywords
- Quantum query complexity
- polynomial method
- completely bounded polynomials
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):1-9, 2021.
- Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, quantum query complexity, and Grothendieck’s inequality. In 31st Conference on Computational Complexity, CCC 2016, pages 25:1-25:19, 2016. URL: http://arxiv.org/abs/1511.08682.
-
Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum query algorithms are completely bounded forms. SIAM J. Comput, 48(3):903-925, 2019. Preliminary version in ITCS'18.
- Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding Quantum-Classical Separations for Classes of Nonlocal Games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:11, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Available at https://arxiv.org/abs/1811.11068. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.12.
- Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.00212.
- Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. URL: https://doi.org/10.1145/502090.502097.
-
S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
-
Jop Briët and Carlos Palazuelos. Failure of the trilinear operator space Grothendieck inequality. Discrete Analysis, 2019. Paper No. 8.
-
Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18), pages 297-310, 2018.
-
Peter C Fishburn and James A Reeds. Bell inequalities, Grothendieck’s constant, and root two. SIAM Journal on Discrete Mathematics, 7(1):48-56, 1994.
- Sander Gribling and Monique Laurent. Semidefinite programming formulations for the completely bounded norm of a tensor. arXiv preprint, 2019. URL: http://arxiv.org/abs/1901.04921.
-
Godfrey Harold Hardy, Edward Maitland Wright, et al. An introduction to the theory of numbers. Oxford university press, 1979.
- Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2009. URL: https://doi.org/10.1017/cbo9781139814782.
-
Gilles Pisier. Grothendieck’s theorem, past and present. Bulletin of the American Mathematical Society, 49(2):237-323, 2012.
- T. Tao. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Society, 2012. URL: https://books.google.nl/books?id=L51VAwAAQBAJ.
- Terence Tao and Joni Teräväinen. Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.02158.
-
Terence Tao and Van H Vu. Additive combinatorics, volume 105. Cambridge University Press, 2006.
- B. S. Tsirelson. Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics, 1980. URL: https://doi.org/10.1007/BF00417500.
- N. Th. Varopoulos. On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory. J. Functional Analysis, 16:83-100, 1974. URL: https://doi.org/10.1016/0022-1236(74)90071-8.