By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of the communication protocol? Protocols that achieve this are referred to as clean and the associated cost as the clean communication complexity. Here we present clean protocols for calculating the inner product of two n-bit strings, showing that (in the absence of preshared entanglement) at most n+3 qubits or n+O(sqrt[n]) bits of communication are required. The quantum protocol provides inspiration for obtaining the optimal method to implement distributed cnot gates in parallel while minimizing the amount of quantum communication. For more general functions, we show that nearly all Boolean functions require close to 2n bits of classical communication to compute and close to n qubits if the parties have access to preshared entanglement. Both of these values are maximal for their respective paradigms.
By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of the communication protocol? Protocols that achieve this are referred to as clean and the associated cost as the clean communication complexity. Here we present clean protocols for calculating the inner product of two n-bit strings, showing that (in the absence of preshared entanglement) at most n+3 qubits or n+O(sqrt[n]) bits of communication are required. The quantum protocol provides inspiration for obtaining the optimal method to implement distributed cnot gates in parallel while minimizing the amount of quantum communication. For more general functions, we show that nearly all Boolean functions require close to 2n bits of classical communication to compute and close to n qubits if the parties have access to preshared entanglement. Both of these values are maximal for their respective paradigms.
We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.
We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form f∘Gn, where f:{0,1}n→{±1} and G is an inner product function of Θ(logn) bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models.
As a corollary, we show that any hybrid protocol communicating c classical bits followed by q qubits to compute f∘Gn must satisfy c+q2=Ω(max{deg(f),bs(f)}⋅logn), where deg(f) is the degree of f and bs(f) is the block sensitivity of f. For read-once formula f, this yields an almost tight trade-off: either they have to exchange Θ(n⋅logn) classical bits or Θ(n⋅logn) qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.
We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(logN) in this model, however, every interactive randomized protocol has cost Ω(N), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ω(logN) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(logN). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions F of the following form: F(x,y)=fn(x1⋅y1,x2⋅y2,...,xn⋅yn), where fn is a {\em symmetric} Boolean function on n Boolean inputs, and xi, yi are the i'th bit of x and y, respectively. His proof critically depends on the symmetry of fn. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F is the ``block-composition'' of a ``building block'' gk:{0,1}k×{0,1}k→{0,1}, and an fn:{0,1}n→{0,1}, such that F(x,y)=fn(gk(x1,y1),gk(x2,y2),...,gk(xn,yn)), where xi and yi are the i'th k-bit block of x,y∈{0,1}nk, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.
Communicational complexity problem among three parties for the calculation of a three party inner product modular function is discussed, where each party possess some of the function’s input. Classical communicational complexity of this function can be evaluated by three classical bits. In classical theory, the three party modular function can’t be evaluated by two classical bits, but using quantum entanglement in quantum theory two classical bits are sufficient to calculate the three party problem.
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 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 one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f:X×Y→Z∪{⊥} be a partial function and μ be a distribution with support contained in f−1(Z) . Denote d=|Z| . Let Rϵ1,μ(f) be the classical one-way communication complexity of f ; Qϵ1,μ(f) be the quantum one-way communication complexity of f and Qϵ1,μ,∗(f) be the entanglement-assisted quantum one-way communication complexity of f , each with distributional error (average error over μ ) at most ϵ . We show:1) If μ is a product distribution, η>0 and 0≤ϵ≤1−1/d , then, R2ϵ−dϵ2/(d−1)+η1,μ(f)≤2Qϵ1,μ,∗(f)+O(loglog(1/η)). 2)If μ is a non-product distribution and Z={0,1} , then ∀ϵ,η>0 such that ϵ/η+η<0.5 , R3η1,μ(f)=O(Qϵ1,μ(f)⋅CS(f)/η3), where CS(f)=maxyminz&am