On relating one-way classical and quantum communication complexities
Title：On relating one-way classical and quantum communication complexities
Time：Nov. 05, 2021, 14:30~15:30
Place：Rm104: Chin-Pao Yang Lecture Hall, CCMS & New Physics Building, NTU
Abstract:
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob try to compute a function $f (x, y) $, where $x$ is given to Alice and $y$ is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between quantum and classical communication complexities, i.e., how much shorter the message can be if the parties are sending a quantum state instead of bit strings? It is known that quantum one-way communication complexity, $Q^1(f)$, can be exponentially smaller than classical one-way communication complexity, $D^1(f)$, if $f$ is a partial function. However, when $f$ is a total function, whether $Q^1(f)$ and $D^1(f)$ can be separated at all is still an open question. In this work, we give better understanding on the separation between $Q^1(f)$ and $D^1(f)$ by giving a general framework which converts a quantum one-way communication protocol into a classical one-way communication protocol. Using this framework, we proved two theorems which state that $D^1(f)=O(Q^1(f)) $ under certain circumstances, giving evidence that $Q^1(f)$ and $D^1(f)$ might not be separated for a total function $f$.
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob try to compute a function $f (x, y) $, where $x$ is given to Alice and $y$ is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between quantum and classical communication complexities, i.e., how much shorter the message can be if the parties are sending a quantum state instead of bit strings? It is known that quantum one-way communication complexity, $Q^1(f)$, can be exponentially smaller than classical one-way communication complexity, $D^1(f)$, if $f$ is a partial function. However, when $f$ is a total function, whether $Q^1(f)$ and $D^1(f)$ can be separated at all is still an open question. In this work, we give better understanding on the separation between $Q^1(f)$ and $D^1(f)$ by giving a general framework which converts a quantum one-way communication protocol into a classical one-way communication protocol. Using this framework, we proved two theorems which state that $D^1(f)=O(Q^1(f)) $ under certain circumstances, giving evidence that $Q^1(f)$ and $D^1(f)$ might not be separated for a total function $f$.
