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.
Recently, Doosti et al. introduced the problem of distributed quantum state verification, where
m distributed nodes are given a copy of an unknown state
ρ, and can send limited one way communication to a central node, who has a complete description of a known state
σ. They ask how many distributed nodes
m are required, before the central node can succeed at distinguishing whether
ρ=σ or
∥ρ−σ∥1≥ε with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.
Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. in Eurocrypt'08, which captures the idea that the view of any verifier in concurrent interaction can be reconstructed in almost the same time. They also constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω (log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our main result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω (1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption.