Document Open Access Logo

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms

Authors Nikhil Bansal, Makrand Sinha, Ronald de Wolf

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2022.28.pdf
  • Filesize: 1.33 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Oracles and decision trees
Keywords
  • Aaronson-Ambainis conjecture
  • Quantum query complexity
  • Classical query complexity
  • Free probability
  • Completely bounded norm
  • Analysis of Boolean functions
  • Influence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-d block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance k-fold Forrelation. Our main technical result relies on connections to free probability theory.

Cite As Get BibTex

Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.28

Author Details

Nikhil Bansal
  • University of Michigan, Ann Arbor, MI, USA
Makrand Sinha
  • Simons Institute, Berkeley, CA, USA
  • University of California Berkeley, CA, USA
Ronald de Wolf
  • QuSoft, CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands

Funding

  • Bansal, Nikhil: Supported in part by the NWO VICI grant 639.023.812.
  • Sinha, Makrand: Supported by a Simons-Berkeley postdoctoral fellowship.
  • de Wolf, Ronald: Partially supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037), and through QuantERA ERA-NET Cofund project QuantAlgo (680-91-034).

Acknowledgements

We thank Scott Aaronson, Srinivasan Arunachalam, Jop Briët, Shachar Lovett and Ryan O'Donnell for helpful comments and pointers to the literature.

References

  1. Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133-166, 2014. Google Scholar
  2. Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM Journal on Computing, 47(3):982-1038, 2018. Google Scholar
  3. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 863-876, 2016. Google Scholar
  4. Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, pages 1330-1342, 2021. URL: http://arxiv.org/abs/2010.12629.
  5. Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of BQP. CoRR, abs/2111.10409, 2021. URL: http://arxiv.org/abs/2111.10409.
  6. Leonard M. Adleman, Jonathan Demarrais, and Ming-Deh A. Huang. Quantum computability. SIAM Journal on Computing, 26(5):1524-1540, 1997. Google Scholar
  7. Andris Ambainis. Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences, 72(2):220-238, 2006. Google Scholar
  8. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Journal of the ACM, 64(5):32:1-32:24, 2017. Google Scholar
  9. Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum query algorithms are completely bounded forms. SIAM Journal on Computing, 48(3):903-925, 2019. Google Scholar
  10. Nikhil Bansal and Makrand Sinha. k-Forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1303-1316, 2021. Google Scholar
  11. Howard Barnum, Michael E. Saks, and Mario Szegedy. Quantum query complexity and semi-definite programming. In Proceedings of 18th Annual IEEE Conference on Computational Complexity, pages 179-193, 2003. Google Scholar
  12. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. Google Scholar
  13. Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-sensitivity functions from unambiguous certificates. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, volume 67 of LIPIcs, pages 28:1-28:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  14. Sergey Bravyi, David Gosset, Daniel Grier, and Luke Schaeffer. Classical algorithms for forrelation, 2021. URL: http://arxiv.org/abs/2102.06963.
  15. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. Google Scholar
  16. Benoît Collins and Camille Male. The strong asymptotic freeness of Haar and deterministic matrices. Annales Scientifiques de l'ENS, (4) 47, fascicule 1:147-163, 2014. URL: http://arxiv.org/abs/1105.4345.
  17. Benoît Collins and Ion Nechita. Random matrix techniques in quantum information theory. Journal of Mathematical Physics, 57(1):015215, 2016. Google Scholar
  18. Andreas Defant, Mieczyslaw Mastylo, and Antonio Pérez. On the Fourier spectrum of functions on Boolean cubes. Mathematische Annalen, 374:653-680, 2018. Google Scholar
  19. Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 437-446, 2006. Google Scholar
  20. Sander Gribling and Monique Laurent. Semidefinite programming formulations for the completely bounded norm of a tensor, 2019. arXiv:1901.04921. Google Scholar
  21. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212-219, 1996. Google Scholar
  22. Uffe Haagerup. An example of a non nuclear C^*-algebra, which has the metric approximation property. Inventiones Mathematicae, 50:279-293, 1978/79. Google Scholar
  23. Todd Kemp and Roland Speicher. Strong Haagerup inequalities for free R-diagonal elements. Journal of Functional Analysis, 251(1):141-173, 2007. URL: http://arxiv.org/abs/math/0512481.
  24. Gatis Midrijanis. On randomized and quantum query complexities, 2005. URL: http://arxiv.org/abs/quant-ph/0501142.
  25. Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12):122206, 2012. Google Scholar
  26. Alexandru Nica and Roland Speicher. Lectures on the Combinatorics of Free Probability. London Mathematical Society Lecture Note Series. Cambridge University Press, 2006. Google Scholar
  27. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4(4):301-313, 1994. Google Scholar
  28. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  29. Ryan O'Donnell, Michael E. Saks, Oded Schramm, and Rocco A. Servedio. Every decision tree has an influential variable. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 31-39, 2005. Google Scholar
  30. Ryan O'Donnell and Yu Zhao. Polynomial bounds for decoupling, with applications. In Proceedings of 31st Conference on Computational Complexity, volume 50 of LIPIcs, pages 24:1-24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  31. Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An optimal separation of randomized and quantum query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1289-1302, 2021. Google Scholar
  32. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. Google Scholar
  33. Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474-1483, 1997. Google Scholar
  34. Avishay Tal. Towards optimal separations between quantum and randomized query complexities. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 228-239, 2020. Google Scholar
  35. Dan Voiculescu. A strengthened asymptotic freeness result for random matrices with applications to free entropy. International Mathematics Research Notices, 1998:41-63, 1998. Google Scholar
  36. Z. Yin, A. W. Harrow, M. Horodecki, M. Marciniak, and A. Rutkowski. Random and free observables saturate the Tsirelson bound for CHSH inequality. Physical Review A, 95(032101), 2017. URL: http://arxiv.org/abs/1512.00223.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact