We present a new scheme for the compression of one-way quantum messages, in the setting of coherent entanglement assisted quantum communication. For this, we present a new technical tool that we call the convex split lemma, which is inspired by the c
lassical compression schemes that use rejection sampling procedure. As a consequence, we show new bounds on the quantum communication cost of single-shot entanglement-assisted one-way quantum state redistribution task and for the sub-tasks quantum state splitting and quantum state merging. Our upper and lower bounds are tight up to a constant and hence stronger than previously known best bounds for above tasks. Our protocols use explicit quantum operations on the sides of Alice and Bob, which are different from the decoupling by random unitaries approach used in previous works. As another application, we present a port-based teleportation scheme which works when the set of input states is restricted to a known ensemble, hence potentially saving the number of required ports. Furthermore, in case of no prior knowledge about the set of input states, our average success fidelity matches the known average success fidelity, providing a new port-based teleportation scheme with similar performance as appears in literature.
In this work we introduce, both for classical communication complexity and query complexity, a modification of the partition bound introduced by Jain and Klauck [2010]. We call it the public-coin partition bound. We show that (the logarithm to the ba
se two of) its communication complexity and query complexi
We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed classical two-prover constant-bit interactive proof syst
ems are known not to be entanglement-resistant. This is currently the strongest expressive power of any known constant-bit answer multi-prover interactive proof system that achieves a constant gap. Our result is based on an oracularizing property of certain private information retrieval systems, which may be of independent interest.
