Document Open Access Logo

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead

Authors Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.32.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Quantum communication complexity
Keywords
  • Quantum query complexity
  • quantum communication complexity
  • approximate degree
  • approximate spectral norm

Metrics

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

Abstract

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the bounded-error quantum query complexity of f. Note that the bounded-error randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the bounded-error randomized query complexity of f. Thus, the BCW simulation has an extra O(log n) factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. Razborov (IZV MATH'03) showed that the bounded-error quantum communication complexity of Set-Disjointness is Ω(√n). The BCW simulation yields an upper bound of O(√n log n). Høyer and de Wolf (STACS'02) showed that this can be reduced to c^(log^* n) for some constant c, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is NOR_n ∘ ∧) is O(Q(NOR_n)).
Perhaps somewhat surprisingly, we show that when • = ⊕, then the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F:{-1,1}ⁿ → {-1,1} such that Q^{cc}(F ∘ ⊕) = Θ(Q(F) log n).
To the best of our knowledge, it was not even known prior to this work whether there existed a total function F and 2-bit function •, such that Q^{cc}(F ∘ •) = ω(Q(F)).

Cite As Get BibTex

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, and Manaswi Paraashar. Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.32

Author Details

Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Arkadev Chattopadhyay
  • Tata Institute of Fundamental Research, Mumbai, India
Nikhil S. Mande
  • Georgetown University, Washington, D.C., USA
Manaswi Paraashar
  • Indian Statistical Institute, Kolkata, India

Acknowledgements

We thank Ronald de Wolf and Srinivasan Arunachalam for various discussions on this problem. They provided us with a number of important pointers that were essential for our understanding of the problem and its importance. We thank Justin Thaler for referring us to Claim 31. We thank the anonymous CCC 2020 reviewers for invaluable comments. In particular, we thank one of the reviewers for pointing out the contrasts between the classical query model and the quantum query model that our results imply (Remark 5).

References

  1. Scott Aaronson and Andris Ambainis. Quantum search of spatial regions. Theory of Computing, 1(1):47-79, 2005. Google Scholar
  2. Anil Ada, Omar Fawzi, and Hamed Hatami. Spectral norm of symmetric functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 338-349, 2012. Google Scholar
  3. Andris Ambainis and Ronald de Wolf. How low can approximate degree and quantum query complexity be for total boolean functions? Computational Complexity, 23(2):305-322, 2014. Google Scholar
  4. Anurag Anshu, Naresh Goud Boddu, and Dave Touchette. Quantum log-approximate-rank conjecture is also false. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 982-994, 2019. Google Scholar
  5. Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved bounds on fourier entropy and min-entropy. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pages 45:1-45:19, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.45.
  6. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. Google Scholar
  7. Ethan Bernstein and Umesh V. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411-1473, 1997. Google Scholar
  8. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  9. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 63-68, 1998. Google Scholar
  10. Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379-395, 2007. Google Scholar
  11. Arkadev Chattopadhyay and Nikhil S. Mande. A lifting theorem with applications to symmetric functions. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, pages 23:1-23:14, 2017. Google Scholar
  12. Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 42-53, 2019. Google Scholar
  13. Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993-3002, 1996. Google Scholar
  14. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212-219, 1996. Google Scholar
  15. Peter Høyer and Ronald de Wolf. Improved quantum communication complexity bounds for disjointness and equality. In STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, pages 299-310, 2002. Google Scholar
  16. Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra. Revisiting bourgain-kalai and fourier entropies. CoRR, abs/1911.10579, 2019. URL: http://arxiv.org/abs/1911.10579.
  17. Matthias Krause and Pavel Pudlák. On the computational power of depth-2 circuits with threshold and modulo gates. Theor. Comput. Sci., 174(1-2):137-156, 1997. Google Scholar
  18. Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. Google Scholar
  19. Ashley Montanaro, Harumichi Nishimura, and Rudy Raymond. Unbounded-error quantum query complexity. Theor. Comput. Sci., 412(35):4619-4628, 2011. Google Scholar
  20. Alexander A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. Google Scholar
  21. Alexander A. Sherstov. Algorithmic 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 311-324, 2018. Google Scholar
  22. Makrand Sinha and Ronald de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 966-981, 2019. Google Scholar
  23. Ronald de Wolf. Quantum communication and complexity. Theor. Comput. Sci., 287(1):337-353, 2002. URL: https://doi.org/10.1016/S0304-3975(02)00377-8.
  24. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213, 1979. Google Scholar
  25. Andrew Chi-Chih Yao. Quantum circuit complexity. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 352-361, 1993. Google Scholar
  26. Shengyu Zhang. On the tightness of the Buhrman-Cleve-Wigderson simulation. In Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, pages 434-440, 2009. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact