We consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored recently by Buhrman et al. We study the information cost of memoryless quantum protocols by looking at a canonical problem: bounded-round quantum communication protocols for the one-bit AND function. We prove directly a tight lower bound of
Θ(log(k)/k) for the information cost of AND for
k-round memoryless quantum protocols and for the input distribution needed for the Disjointness function. It is not clear if memoryless protocols allow for a reduction between AND and Disjointness, due to the absence of private workspaces. We enhance the model by allowing the players to keep in their private classical workspace apart from their input also some classical private coins. Surprisingly, we show that every quantum protocol can be transformed into an equivalent quantum protocol with private coins that is perfectly private, i.e. the players only learn the value of the function and nothing more. Last, we consider the model where the players are allowed to use one-shot coins, i.e. private coins that can be used only once during the protocol. While in the classical case, private coins and one-shot coins are equivalent, in the quantum case, we prove that they are not. More precisely, we show that every quantum memoryless protocol with one-bit inputs that uses one-shot coins can be transformed into a memoryless quantum protocol without private coins and without increasing too much its information cost. Hence, while private coins always allow for private quantum protocols, one-shot coins do not.
We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of
n processors at most
t of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost
n/3 processor failures and terminates in
t+4 rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.