Document Open Access Logo

The Complexity of Quantum Disjointness

Author Hartmut Klauck

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.15.pdf
  • Filesize: 431 kB
  • 13 pages

Document Identifiers

Author Details

Hartmut Klauck

Cite As Get BibTex

Hartmut Klauck. The Complexity of Quantum Disjointness. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.15

Abstract

We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the Vector-in-Subspace and Non-Disjointness problems.  We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p).

We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.

Subject Classification

Keywords
  • Communication Complexity
  • Quantum Proof Systems

Metrics

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

References

  1. S. Aaronson. Qma/qpoly ⊆ pspace/poly: De-merlinizing quantum protocols. In Proceedings of 21st IEEE Conference on Computational Complexity, 2006. Google Scholar
  2. S. Aaronson and A. Ambainis. Quantum search of spatial regions. In Proceedings of 44th IEEE FOCS, pages 200-209, 2003. Google Scholar
  3. S. Aaronson and G. Kuperberg. Quantum versus classical proofs and advice. Theory of Computing, 3(1):129-157, 2007. Google Scholar
  4. S. Aaronson and A. Wigderson. Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory, 1(1), 2009. Google Scholar
  5. D. Aharonov and T. Naveh. Quantum np - a survey. quant-ph/0210077, 2002. Google Scholar
  6. L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proceedings of 27th IEEE FOCS, pages 337-347, 1986. Google Scholar
  7. Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. Information theory methods in communication complexity. In Proceedings of 17th IEEE Conference on Computational Complexity, pages 93-102, 2002. Google Scholar
  8. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53-74. AMS, 2002. quant-ph/0005055. Google Scholar
  9. M. Braverman, A. Garg, Young K.K., J. Mao, and D. Touchette. Near-optimal bounds on bounded-round quantum communication complexity of disjointness. In IEEE 56th Annual Symposium on Foundations of Computer Science, pages 773-791, 2015. Google Scholar
  10. A. Chakrabarti, G. Cormode, A. McGregor, J. Thaler, and S. Venkatasubramanian. Verifiable stream computation and arthur-merlin communication. In 30th Conference on Computational Complexity, pages 217-243, 2015. Google Scholar
  11. S. Dasgupta and A. Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures &Algorithms, 22(1):60-65, 2003. Google Scholar
  12. M. Göös, T. Pitassi, and T. Watson. Zero-information protocols and unambiguity in arthur-merlin communication. Algorithmica, 76(3):684-719, 2016. Google Scholar
  13. L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212-219, 1996. Google Scholar
  14. B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992. Earlier version in Structures'87. Google Scholar
  15. A. Yu. Kitaev. Quantum NP, January 1999. Talk given at AQIP'99, DePaul University, Chicago. Google Scholar
  16. B. Klartag and O. Regev. Quantum one-way communication is exponentially stronger than classical communication. In Proceedings of 43rd ACM STOC, 2011. Google Scholar
  17. H. Klauck. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of 32nd ACM STOC, pages 644-651, 2000. Google Scholar
  18. H. Klauck. Rectangle size bounds and threshold covers in communication complexity. In 18th Annual IEEE Conference on Computational Complexity, pages 118-134, 2003. Google Scholar
  19. H. Klauck. A strong direct product theorem for disjointness. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 77-86, 2010. Google Scholar
  20. H. Klauck. On arthur merlin games in communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, pages 189-199, 2011. Google Scholar
  21. H. Klauck and S. Podder. Two Results about Quantum Messages. In Proceedings of MFCS, 2014. Google Scholar
  22. I. Kremer. Quantum communication. Master’s thesis, Hebrew University, Computer Science Department, 1995. Google Scholar
  23. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  24. R. Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of 31st ACM STOC, pages 358-367, 1999. Google Scholar
  25. R. Raz and A. Shpilka. On the power of quantum proofs. In 19th Annual IEEE Conference on Computational Complexity, pages 260-274, 2004. Google Scholar
  26. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. Google Scholar
  27. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, mathematics, 67(1):159-176, 2003. quant-ph/0204025. Google Scholar
  28. A. Sherstov. The pattern matrix method for lower bounds on quantum communication. In Proceedings of 40th ACM STOC, pages 85-94, 2008. Google Scholar
  29. R. de Wolf. Quantum communication and complexity. Theoretical Computer Science, 287(1):337-353, 2002. Google Scholar
  30. A. C-C. Yao. Some complexity questions related to distributive computing. In Proceedings of 11th ACM STOC, pages 209-213, 1979. 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