  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 $\Theta(\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.
