Simple Communication Complexity Separation from Quantum State Antidistinguishability

Abstract

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 $k$-th 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\approx 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, non-trivial bounds can be established in any dimension $\ge 3$. The task can be framed in terms of the separated parties solving a relation, and the separation is also robust to multiplicative error in the output probabilities. We show, however, that for this particular task, the separation disappears if two-way classical communication is allowed. 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 one-way communication of $\Omega (d\log d)$ classical bits.

References in corpus (23)

• Quantum fingerprinting
• Symmetric Informationally Complete Quantum Measurements
• On the reality of the quantum state
• Non-locality and Communication Complexity
• Einstein, incompleteness, and the epistemic view of quantum states
• The Communication Cost of Simulating Bell Correlations
• Is the quantum state real? An extended review of $\psi$-ontology theorems
• SIC-POVMs: A new computer study
• The cost of exactly simulating quantum entanglement with classical communication
• No $\psi$-epistemic model can fully explain the indistinguishability of quantum states
• Conditions for compatibility of quantum state assignments
• Conclusive Exclusion of Quantum States
• Classical Teleportation of a Quantum Bit
• Coherence Optimization and Best Complex Antipodal Spherical Codes
• Communication tasks with infinite quantum-classical separation
• Antidistinguishability of Pure Quantum States
• Epistemic view of quantum states and communication complexity of quantum channels
• Communication of partial ignorance with qubits
• Communication complexity and the reality of the wave-function
• Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement
• Doubly infinite separation of quantum information and communication
• Necessary and sufficient optimality conditions for classical simulations of quantum communication processes
• Quantum states cannot be transmitted efficiently classically

Cited by in corpus (15)

• Noncontextuality Inequalities from Antidistinguishability
• Simple Information Processing Tasks with Unbounded Quantum Advantage
• On the optimal error exponents for classical and quantum antidistinguishability
• A note on the inner products of pure states and their antidistinguishability
• Tight bounds for antidistinguishability and circulant sets of pure quantum states
• Operational Interpretation of the Choi Rank Through k-State Exclusion
• Experimental demonstration of optimal unambiguous two-out-of-four quantum state elimination
• Single-shot Distinguishability and Anti-distinguishability of Quantum Measurements
• The pretty bad measurement
• Failure of epistemic models to explain the antidistinguishability of quantum mixed preparations
• How contextuality and antidistinguishability are related
• Quantum state exclusion for group-generated ensembles of pure states
• Single-shot antidistinguishability of unitary operations
• Random Exclusion Codes: Quantum Advantages of Single-Shot Communication
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources