Document Open Access Logo

The Power of One Clean Qubit in Communication Complexity

Authors Hartmut Klauck, Debbie Lim

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.69.pdf
  • Filesize: 1.11 MB
  • 23 pages

Document Identifiers

Author Details

Hartmut Klauck
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Debbie Lim
  • Centre for Quantum Technologies, National University of Singapore, Singapore

Funding

This work is funded by the Singapore Ministry of Education and by the Singapore National Research Foundation. Also supported by Majulab UMI 3654.

Cite As Get BibTex

Hartmut Klauck and Debbie Lim. The Power of One Clean Qubit in Communication Complexity. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 69:1-69:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.69

Abstract

We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse.
We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions.
We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those.
We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity.
Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n).
We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Complexity Theory
  • Quantum Communication Complexity
  • One Clean Qubit Model

Metrics

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

Related Versions

References

  1. S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9:143-252, 2013. Google Scholar
  2. A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  3. A. Ambainis, R. Špalek, and R. de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. In Proceedings of 38th ACM STOC, pages 618-633, 2006. quant-ph/0511200. Google Scholar
  4. L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory.pdf. In Proceedings FOCS, 1986. Google Scholar
  5. M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. In Proceedings of the Royal Society A, volume 467, pages 459-472, 2011. Google Scholar
  6. D. J. Brod. The complexity of simulating constant-depth boson sampling. Physical Review A, 91(4), 2015. Google Scholar
  7. J. Brody, S. Chen, P. A. Papakonstantinou, H. Song, and X. Sun. Space-bounded communication complexity. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS '13, pages 159-172, 2013. Google Scholar
  8. H. Buhrman, R. Cleve, M. Koucký, B. Loff, and F. Speelman. Computing with a full memory: Catalytic space. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 857-866. ACM, 2014. Google Scholar
  9. C. Cade and A. Montanaro. The quantum complexity of computing schatten p-norms, 2017. URL: http://arxiv.org/abs/1706.09279v1.
  10. R. Cleve, W. van Dam, M. Nielsen, and A. Tapp. Quantum entanglement and the communication complexity of the inner product function. In Proceedings of 1st NASA QCQC conference, volume 1509 of Lecture Notes in Computer Science, pages 61-74. Springer, 1998. URL: http://arxiv.org/abs/quant-ph/9708019.
  11. R. de Wolf. Quantum communication and complexity. Theoretical Computer Science, 287:337-353, 2002. Google Scholar
  12. K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pages 13:1-13:14, 2016. Google Scholar
  13. R. Jain and H. Klauck. The partition bound for classical communication complexity and query complexity. In 25th Annual Conference on Computational Complexity, pages 247-258, 2010. URL: http://arxiv.org/abs/0910.4266v2.
  14. R. Jozsa and M. V. den Nest. Classical simulation complexity of extended clifford circuits. Quantum Information and Computation, 14(7-8):0633-0648,, 2014. Google Scholar
  15. B. Klartag and O. Regev. Quantum one-way communication is exponentially stronger than classical communication. In Proceedings of 43rd ACM STOC, 2011. Google Scholar
  16. H. Klauck. Quantum and classical communication-space tradeoffs from rectangle bounds. In FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 24th International Conference, pages 384-395, 2004. Google Scholar
  17. H. Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20-46, 2007. Earlier version in FOCS'01. quant-ph/0106160. Google Scholar
  18. H. Klauck and D. Lim. The power of one clean qubit in communication complexity. arXiv, 2018. URL: http://arxiv.org/abs/1807.07762.
  19. H. Klauck and D. Lim. The abc problem and equator sampling renyi divergences. arXiv, 2019. URL: http://arxiv.org/abs/1912.11275.
  20. H. Klauck, R. Špalek, and R. 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'04. quant-ph/0402123. Google Scholar
  21. E. Knill and R. Laflamme. On the power of one bit of quantum information. Phys.Rev.Lett., 81:5672-5675, 1998. URL: http://arxiv.org/abs/quant-ph/9802037v1.
  22. I. Kremer. Quantum communication. Master’s Thesis, 1995. Google Scholar
  23. I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21-49, 1999. Earlier version in STOC'95. Correction at http://www.eng.tau.ac.il/~ danar/Public/KNR-fix.ps. Google Scholar
  24. E. Kushilevitz and N. Nisan. Communication Complexity. CUP, 1997. Google Scholar
  25. N. Linial and A. Shraibman. Learning complexity vs communication complexity. Combinatorics, Probability and Computing, 18:227-245, 2009. Google Scholar
  26. T. Morimae, K. Fujii, and J. F. Fitzsimons. On the hardness of classically simulating the one clean qubit model. Phys. Rev. Lett., 112, 130502, 2014. Google Scholar
  27. T. Morimae and T. Koshiba. Classical simulatability of the one clean qubit model, 2014. URL: http://arxiv.org/abs/1405.6840v2.
  28. A. Nayak. Optimal lower bounds for quantum automata and random access codes. In In Proceedings of 40th IEEE FOCS, 1999. Google Scholar
  29. X. Ni and M. V. den Nest. Commuting quantum circuits: Efficient classical simulations versus hardness results. Quantum Information and Computation, 13(1-2):0054-0072, 2013. Google Scholar
  30. D. Poulin, R. Blume-Kohout, R. Laflamme, and H. Ollivier. Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect. Phys. Rev. Lett., 92, 177906, 2004. Google Scholar
  31. D. Poulin, R. Laflamme, G. J. Milburn, and J. P. Paz. Testing integrability with a single bit of quantum information. Phys. Rev. A, 68(2):022302-1-022302-6, 2003. Google Scholar
  32. A. A. Razborov. On the distributional complexity of disjointness. Theoret. Comput. Sci., 106:385-390, 1992. Google Scholar
  33. A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. Google Scholar
  34. P. W. Shor and S. P. Jordan. Estimating jones polynomials is a complete problem for one clean qubit. Quantum Information and Computation, 8:681, 2008. URL: http://arxiv.org/abs/0707.2831v3.
  35. Y. Takahashi, S. Tani, T. Yamazaki, and K. Tanaka. Commuting quantum circuits with few outputs are unlikely to be classically simulatable. Computing and Combinatorics, 21st International Conference, COCOON 2015, 9198 of Lecture Notes in Computer Science:223-234, 2015. Google Scholar
  36. Y. Takahashi, T. Yamazaki, and K. Tanaka. Hardness of classically simulating quantum circuits with unbounded toffoli and fan-out gates. Quantum Information and Computation, 14(13-14):1149-1164, 2014. Google Scholar
  37. B. M. Terhal and D. P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Information and Computation, 4(2):134-145, 2004. Google Scholar
  38. A. C. Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209-213. ACM, 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