Document Open Access Logo

Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem

Authors João F. Doriguello , Ashley Montanaro

PDF
Thumbnail PDF

File

LIPIcs.TQC.2020.1.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

João F. Doriguello
  • School of Mathematics, University of Bristol, United Kingdom
  • Quantum Engineering Centre for Doctoral Training, University of Bristol, United Kingdom
Ashley Montanaro
  • School of Mathematics, University of Bristol, United Kingdom

Funding

  • Doriguello, João F.: EPSRC grant EP/L015730/1.
  • Montanaro, Ashley: QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo project); the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 817581); and EPSRC grants EP/L021005/1, and EP/R043957/1.

Acknowledgements

We would like to thank Ronald de Wolf for pointing out Ref. [Shi et al., 2012], and Makrand Sinha for useful discussions about the hypercontractive inequality.

Cite AsGet BibTex

João F. Doriguello and Ashley Montanaro. Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.TQC.2020.1

Abstract

In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Quantum complexity theory
Keywords
  • Communication Complexity
  • Quantum Communication Complexity
  • Boolean Hidden Matching Problem

Metrics

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

Related Versions

References

  1. Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM Journal on Computing, 47(3):982-1038, 2018. arXiv:1411.5729. Google Scholar
  2. Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, quantum query complexity, and Grothendieck’s inequality. In 31st Conference on Computational Complexity, 2016. arXiv:1511.08682. Google Scholar
  3. James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):135-148, 1994. Google Scholar
  4. Ziv Bar-Yossef, Thathachar S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 128-137. ACM, 2004. Google Scholar
  5. William Beckner. Inequalities in Fourier analysis. Ann. of Math., 102:159-182, 1975. Google Scholar
  6. Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 477-486. IEEE, 2008. arXiv:0705.3806. Google Scholar
  7. Aline Bonami. Étude des coefficients Fourier des fonctions de L^p(G). In Annales de l'institut Fourier, volume 20(2), pages 335-402, 1970. Google Scholar
  8. Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. Nonlocality and communication complexity. Reviews of modern physics, 82(1):665, 2010. arXiv:0907.3584. Google Scholar
  9. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. quant-ph/0102001. Google Scholar
  10. Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In Proc. 22superscriptnd Annual IEEE Conf. Computational Complexity, pages 24-32, 2007. Google Scholar
  11. Jo~ao F. Doriguello and Ashley Montanaro. Exponential quantum communication reductions from generalizations of the boolean hidden matching problem. arXiv preprint arXiv:2001.05553, 2020. Google Scholar
  12. Jo~ao Fernando Doriguello and Ashley Montanaro. Quantum sketching protocols for Hamming distance and beyond. Phys. Rev. A, 99:062331, 2019. arXiv:1810.12808. Google Scholar
  13. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  14. Dmitry Gavinsky. Classical interaction cannot replace a quantum message. In Proc. 40superscriptth Annual ACM Symp. Theory of Computing, pages 95-102, 2008. quant-ph/0703215. Google Scholar
  15. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. SIAM Journal on Computing, 38(5):1695-1708, 2008. quant-ph/0611209. Google Scholar
  16. Carl Wilhelm Helstrom. Quantum detection and estimation theory. Academic press, 1976. Google Scholar
  17. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Proc. 29superscriptth Annual Symp. Foundations of Computer Science, pages 68-80. IEEE, 1988. Google Scholar
  18. Hartmut Klauck. Lower bounds for quantum communication complexity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 288-297. IEEE, 2001. quant-ph/0106160. Google Scholar
  19. Ashley Montanaro. A new exponential separation between quantum and classical one-way communication complexity. Quantum Inf. Comput., 11(7&8):574-591, 2011. arXiv:1007.3587. Google Scholar
  20. Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67-71, 1991. Google Scholar
  21. Ran Raz. Fourier analysis for probabilistic communication complexity. Computational Complexity, 5(3-4):205-221, 1995. Google Scholar
  22. Ran Raz. Exponential separation of quantum and classical communication complexity. In STOC, volume 99, pages 358-367. Citeseer, 1999. Google Scholar
  23. Oded Regev and Bo'az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43superscriptrd Annual ACM Symp. Theory of Computing, pages 31-40, 2011. arXiv:1009.3640. Google Scholar
  24. Yaoyun Shi, Xiaodi Wu, and Wei Yu. Limits of quantum one-way communication by matrix hypercontractive inequality, 2012. Google Scholar
  25. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26:1484-1509, 1997. quant-ph/9508027. Google Scholar
  26. Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 11-25. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  27. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227. IEEE, 1977. Google Scholar
  28. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209-213. ACM, 1979. Google Scholar
  29. Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352-361. IEEE, 1993. 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 Imprint Privacy Contact