1 Search Results for "Lim, Debbie"


Document
The Power of One Clean Qubit in Communication Complexity

Authors: Hartmut Klauck and Debbie Lim

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.MFCS.2021.69,
  author =	{Klauck, Hartmut and Lim, Debbie},
  title =	{{The Power of One Clean Qubit in Communication Complexity}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{69:1--69:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.69},
  URN =		{urn:nbn:de:0030-drops-145097},
  doi =		{10.4230/LIPIcs.MFCS.2021.69},
  annote =	{Keywords: Quantum Complexity Theory, Quantum Communication Complexity, One Clean Qubit Model}
}
  • Refine by Author
  • 1 Klauck, Hartmut
  • 1 Lim, Debbie

  • Refine by Classification
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 One Clean Qubit Model
  • 1 Quantum Communication Complexity
  • 1 Quantum Complexity Theory

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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