We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as little as possible. In the zero-error regime, the optimal rates of source codes and channel codes are given by graph parameters known as the Witsenhausen rate and Shannon capacity, respectively. The Lovász theta number, a graph parameter defined by a semidefinite program, gives the best efficiently computable upper bound on the Shannon capacity and it also upper bounds its entanglement-assisted counterpart. At the same time, it was recently shown that the Shannon capacity can be increased if Alice and Bob may use entanglement. Here, we partially extend these results to the source-coding problem and to the more general source-channel coding problem. We prove a lower bound on the rate of entanglement-assisted source-codes in terms of Szegedy's number (a strengthening of the theta number). This result implies that the theta number lower bounds the entangled variant of the Witsenhausen rate. We also show that entanglement can allow for an unbounded improvement of the asymptotic rate of both classical source codes and classical source-channel codes. Our separation results use low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu, and a new application of remote state preparation.

We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.

Here, we present a new fixed parameter tractable algorithm to compute the hybridization number r of two rooted, not necessarily binary phylogenetic trees on taxon set Χ in time (6(r)r!) · poly(n), where n = |Χ|. The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on Χ, and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.