The Power of One Clean Qubit in Communication Complexity

DOI10.4230/LIPICS.MFCS.2021.69MaRDI QIDQ6168487zbMATH OpenOpenAlexFDO

Authors Hartmut Klauck, Debbie Lim

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/1807.07762

zbMATH Keywords

one-clean-qubit modelquantum communication complexityquantum complexity theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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(logn)$ qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error $1/poly(n)$ needs communication $Omega(n)$. We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within {em constant} additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.

Recommendations

• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Exponential separation of quantum and classical one-way communication complexity
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• A new exponential separation between quantum and classical one-way communication complexity
• New One Shot Quantum Protocols With Application to Communication Complexity
• New bounds on classical and quantum one-way communication complexity
• Communication Complexity of One-Shot Remote State Preparation
• Experimental multipartner quantum communication complexity employing just one qubit
• Power of quantum computation with few clean qubits
• On the near-optimality of one-shot classical communication over quantum channels

Cited in

(3)

• Experimental multipartner quantum communication complexity employing just one qubit
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• scientific article; zbMATH DE number 5573021 (Why is no real title available?)

This page was built for publication: The Power of One Clean Qubit in Communication Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168487)