A set of n pure quantum states is called antidististinguishable if there exists an n-outcome measurement that never outputs the outcome 'k' on the kth quantum state.We describe sets of quantum states for which any subset of three states is antidistinguishable and use this to produce a two-player communication task that can be solved with log d qubits, but requires one-way communication of at least log(4/3)(d -1) -1 ≈ 0.415(d -1) -1 classical bits.The advantages of the approach are that the proof is simple and self-contained -not needing, for example, to rely on hard-to-establish prior results in combinatorics -and that with slight modifications, nontrivial bounds can be established in any dimension 3. The task can be framed in terms of the separated parties solving a relation.We show, however, that for this particular task, the separation disappears if two-way classical communication is allowed, or if the task need only be solved with bounded error.Finally, we state a conjecture regarding antidistinguishability of sets of states, and provide some supporting numerical evidence.If the conjecture holds, then there is a two-player communication task that can be solved with log d qubits, but requires exact one-way communication of (d log d ) classical bits.
A set of n pure quantum states is called antidististinguishable if there exists an n-outcome measurement that never outputs the outcome 'k' on the kth quantum state.We describe sets of quantum states for which any subset of three states is antidistinguishable and use this to produce a two-player communication task that can be solved with log d qubits, but requires one-way communication of at least log(4/3)(d -1) -1 ≈ 0.415(d -1) -1 classical bits.The advantages of the approach are that the proof is simple and self-contained -not needing, for example, to rely on hard-to-establish prior results in combinatorics -and that with slight modifications, nontrivial bounds can be established in any dimension 3. The task can be framed in terms of the separated parties solving a relation.We show, however, that for this particular task, the separation disappears if two-way classical communication is allowed, or if the task need only be solved with bounded error.Finally, we state a conjecture regarding antidistinguishability of sets of states, and provide some supporting numerical evidence.If the conjecture holds, then there is a two-player communication task that can be solved with log d qubits, but requires exact one-way communication of (d log d ) classical bits.
We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.
We consider the problem of bounded-error quantum state identification: given either state α0 or state α1, we are required to output '0', '1' or 'DONO' ("don't know"), such that conditioned on outputting '0' or '1', our guess is correct with high probability. The goal is to maximize the probability of not outputting 'DONO'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest.Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Ω(n1/3) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Ω((n/log n)1/3) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity where entanglement buys you much more than quantum communication does.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn:{0,1}n×{0,1}n→{0,1} that can be computed with O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n+1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that, if no entangled particles are provided, then the communication complexity of F is roughly klog2k. These two results prove communication complexity separations better than a constant number of bits.
We study the task of quantum state exclusion, focusing on antidistinguishability and its generalization to x-antidistinguishability, under global measurements and local operations with classical communication (LOCC). We also introduce weak and strong notions of antidistinguiahbaility (x-antidistinguishability) depending on whether all states or all x-tuples are exhaustively eliminated. Our results reveal striking differences between state exclusion and the more familiar task of state discrimination. In particular, we show that LOCC antidistinguishability of multipartite product states is symmetric with respect to the initiating party but this symmetry breaks down for higher-order x-antidistinguishability. Most notably, we establish a manifestation of \emph{nonlocality without entanglement} in the context of state exclusion: we prove that three bipartite product states can be globally antidistinguishable while failing to be LOCC antidistinguishable, demonstrating that three is the minimal number of states required for this phenomenon. We further extend this separation to 2-antidistinguishability and present example exhibiting the same type of nonlocality. At last, we provide an antidistinguishable tripartite product states that are not LOCC antidistinguishable across any bipartition, which ensures the phenomenon of \emph{genuine nonlocality without entanglement} in this framework.
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