Document Open Access Logo

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Authors Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.7.pdf
  • Filesize: 0.73 MB
  • 47 pages

Document Identifiers

Author Details

Scott Aaronson
  • University of Texas at Austin, TX, USA
Robin Kothari
  • Microsoft Quantum, Redmond, WA, USA
  • Microsoft Research, Redmond, WA, USA
William Kretschmer
  • University of Texas at Austin, TX, USA
Justin Thaler
  • Georgetown University, Washington, D.C., USA

Funding

  • Aaronson, Scott: Supported by a Vannevar Bush Fellowship from the US Department of Defense, a Simons Investigator Award, and the Simons quotedblleft It from Qubitquotedblright collaboration.
  • Kretschmer, William: Supported by a Vannevar Bush Fellowship from the US Department of Defense and a Simons Investigator Award.
  • Thaler, Justin: Supported by NSF CAREER award CCF-1845125.

Acknowledgements

We are grateful to many people: Paul Burchard, for suggesting the problem of approximate counting with queries and QSamples; MathOverflow user quotedblleft fedjaquotedblright for letting us include Lemma 22 and Lemma 23; Ashwin Nayak, for extremely helpful discussions, and for suggesting the transformation of linear programs used in our extension of the method of dual polynomials to the Laurent polynomial setting; Thomas Watson, for suggesting the intersection approach to proving an SBP vs. QMA oracle separation; and Patrick Rall, for helpful feedback on writing. JT would particularly like to thank Ashwin Nayak for his warm hospitality and deeply informative discussions during a visit to Waterloo.

Cite As Get BibTex

Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 7:1-7:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.7

Abstract

We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S ⊆ [N], in two natural generalizations of quantum query complexity.
Our first result holds in the standard Quantum Merlin - Arthur (QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes T quantum queries to S, and also receives an (untrusted) m-qubit quantum witness, then either m = Ω(|S|) or T = Ω(√{N/|S|}). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of S. As a corollary, this resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA.
In our second result, we ask what if, in addition to a membership oracle for S, a quantum algorithm is also given "QSamples" - i.e., copies of the state |S⟩ = 1/√|S| ∑_{i ∈ S} |i⟩ - or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(√{N/|S|}) queries or else Θ(min{|S|^{1/3},√{N/|S|}}) QSamples or accesses to the unitary. 
Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Oracles and decision trees
Keywords
  • Approximate counting
  • Laurent polynomials
  • QSampling
  • query complexity

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum lower bound for the collision problem. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing - STOC 2002, pages 635-642, 2002. quant-ph/0111102. URL: https://doi.org/10.1145/509907.509999.
  2. Scott Aaronson. Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1-28, 2005. Earlier version in CCC'2004. quant-ph/0402095. URL: https://doi.org/10.4086/toc.2005.v001a001.
  3. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 461(2063):3473-3482, 2005. quant-ph/0412187. URL: https://doi.org/10.1098/rspa.2005.1546.
  4. Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Info. Comput., 12(1-2):21-28, January 2012. URL: http://dl.acm.org/citation.cfm?id=2231036.2231039.
  5. Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified, 2019. URL: http://arxiv.org/abs/1908.10846.
  6. Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595-605, 2004. URL: https://doi.org/10.1145/1008731.1008735.
  7. Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC 2003, pages 20-29, 2003. quant-ph/0301023. URL: https://doi.org/10.1145/780542.780546.
  8. 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. Earlier version in FOCS'1998, pp. 352-361. quant-ph/9802049. URL: https://doi.org/10.1145/502090.502097.
  9. Aleksandrs Belovs and Ansis Rosmanis. Tight quantum lower bound for approximate counting with quantum states. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.06879.
  10. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510-1523, 1997. quant-ph/9701001. URL: https://doi.org/10.1137/S0097539796300933.
  11. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. URL: https://doi.org/10.1016/j.jcss.2006.05.001.
  12. Adam D. Bookatz. QMA-complete Problems. Quantum Info. Comput., 14(5&6):361-383, April 2014. URL: http://dl.acm.org/citation.cfm?id=2638661.2638662.
  13. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation, volume 305, pages 53-74. American Mathematical Society, 2002. URL: https://doi.org/10.1090/conm/305/05215.
  14. Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum counting. In Automata, Languages and Programming, pages 820-831, 1998. arXiv:quant-ph/9805082. URL: https://doi.org/10.1007/bfb0055105.
  15. Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In LATIN'98: Theoretical Informatics, pages 163-169, 1998. URL: https://doi.org/10.1007/BFb0054319.
  16. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21-43, 2002. URL: https://doi.org/10.1016/s0304-3975(01)00144-x.
  17. 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 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 297-310, 2018. URL: https://doi.org/10.1145/3188745.3188784.
  18. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. In Automata, Languages, and Programming, pages 303-314, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_26.
  19. Mark Bun and Justin Thaler. Hardness amplification and the approximate degree of constant-depth circuits. In Automata, Languages, and Programming, pages 268-280, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_22.
  20. Don Coppersmith and T. J. Rivlin. The growth of polynomials bounded at equally spaced points. SIAM J. Math. Anal., 23(4):970-983, July 1992. URL: https://doi.org/10.1137/0523054.
  21. Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1-17, January 1991. Earlier version in STOC'1989. URL: https://doi.org/10.1145/102782.102783.
  22. H. Ehlich and K. Zeller. Schwankung von Polynomen zwischen Gitterpunkten. Mathematische Zeitschrift, 86:41-44, 1964. URL: https://doi.org/10.1007/BF01111276.
  23. Oded Goldreich and Shafi Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540-563, 2000. Google Scholar
  24. Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6(2):97-116, 1993. Google Scholar
  25. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on computing, 18(1):186-208, 1989. Google Scholar
  26. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. URL: https://doi.org/10.1137/15M103145X.
  27. Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002. URL: http://arxiv.org/abs/quant-ph/0208112.
  28. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC 1996, pages 212-219, 1996. quant-ph/9605043. URL: https://doi.org/10.1145/237814.237866.
  29. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM, 51(4):671-697, 2004. Earlier version in STOC'2001. URL: https://doi.org/10.1145/1008731.1008738.
  30. Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(1), 2017. URL: https://doi.org/10.1038/s41534-017-0013-7.
  31. Hartmut Klauck, Robert Špalek, and Ronald de Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing, 36(5):1472-1493, 2007. Earlier version in FOCS'2004. quant-ph/0402123. URL: https://doi.org/10.1137/05063235X.
  32. William Kretschmer. Lower bounding the AND-OR tree via symmetrization, 2019. URL: http://arxiv.org/abs/1907.06731.
  33. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. URL: https://doi.org/10.4086/toc.2015.v011a006.
  34. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631-633, 2014. arXiv:1307.0401. URL: https://doi.org/10.1038/nphys3029.
  35. Andrei Andreyevich Markov. On a question by DI Mendeleev. Zapiski Imperatorskoi Akademii Nauk, 62:1-24, 1890. Google Scholar
  36. Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, June 2005. URL: https://doi.org/10.1007/s00037-005-0194-x.
  37. Daniele Micciancio and Salil P Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Annual International Cryptology Conference, pages 282-298. Springer, 2003. Google Scholar
  38. Peter Bro Miltersen and N. V. Vinodchandran. Derandomizing Arthur-Merlin games using hitting sets. In 40th Annual Symposium on Foundations of Computer Science, pages 71-80, October 1999. URL: https://doi.org/10.1109/SFFCS.1999.814579.
  39. Marvin Minsky and Seymour A. Papert. Perceptrons (2nd edition). MIT Press, 1988. First appeared in 1968. Google Scholar
  40. Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC '99, pages 384-393, New York, NY, USA, 1999. ACM. URL: https://doi.org/10.1145/301250.301349.
  41. Donald J. Newman. Rational approximation to | x|. The Michigan Mathematical Journal, 11(1):11-14, 1964. URL: https://doi.org/10.1307/mmj/1028999029.
  42. Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, USA, 2014. Google Scholar
  43. Ramamohan Paturi. On the degree of polynomials that approximate symmetric Boolean functions. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC 1992, pages 468-474, 1992. URL: https://doi.org/10.1145/129712.129758.
  44. Chris Peikert and Vinod Vaikuntanathan. Noninteractive statistical zero-knowledge proofs for lattice problems. In Annual International Cryptology Conference, pages 536-553. Springer, 2008. Google Scholar
  45. Ran Raz and Amir Shpilka. On the power of quantum proofs. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 260-274. IEEE, 2004. Google Scholar
  46. T. J. Rivlin and E. W. Cheney. A comparison of uniform approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis, 3(2):311-320, 1966. URL: https://doi.org/10.1137/0703024.
  47. Rocco Servedio, Li-Yang Tan, and Justin Thaler. Attribute-efficient learning andweight-degree tradeoffs for polynomial threshold functions. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 14.1-14.19, 2012. URL: http://proceedings.mlr.press/v23/servedio12.html.
  48. Alexander A. Sherstov. The intersection of two halfspaces has high threshold degree. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS '09, pages 343-362, Washington, DC, USA, 2009. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=1747597.1748051.
  49. Alexander A. Sherstov. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 523-532, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1806689.1806762.
  50. Alexander A Sherstov and Justin Thaler. Vanishing-error approximate degree and QMA complexity. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.07498.
  51. Yaoyun Shi. Approximating linear restrictions of boolean functions. Available at http://web.eecs.umich.edu/~shiyy/mypapers/, 2002.
  52. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, 1989. URL: https://doi.org/10.1016/0890-5401(89)90067-9.
  53. Robert Špalek. A dual polynomial for OR. CoRR, abs/0803.4516, 2008. URL: http://arxiv.org/abs/0803.4516.
  54. Larry Stockmeyer. On approximation algorithms for #P. SIAM Journal on Computing, 14(4):849-861, 1985. URL: https://doi.org/10.1137/0214060.
  55. Justin Thaler. Lower Bounds for the Approximate Degree of Block-Composed Functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.17.
  56. Nikolai K. Vereshchagin. On the power of PP. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pages 138-143, 1992. URL: https://doi.org/10.1109/SCT.1992.215389.
  57. Mark Zhandry. How to construct quantum random functions. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS '12, pages 679-687. IEEE, 2012. URL: https://doi.org/10.1109/FOCS.2012.37.
  58. Mark Zhandry. Quantum lightning never strikes the same state twice. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 408-438. Springer, 2019. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact