We study the problem of finding the optimal code of size k for a given classical-quantum channel, with input space X and output space of dimension d, from an algorithmic point of view. We show that unlike the classical case, the relevant function is not submodular, and does not have the diminishing returns property. We also study a semidefinite programming relaxation, which corresponds to the setting where the sender and receiver have a non-signalling box, and show that it can be rounded in two different ways. If the SDP gives a value of p for the success probability, then a simple rounding strategy returns a code of size k with success probability at least p/O(log IXI log d). The second rounding method is p based on the pretty good measurement and returns a code with success probability close to p, but the code is smaller: it has size k · Ω(p2).

Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that (i) all prefix sums of the ordering are nonnegative and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. call this problem the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms. We consider a related problem, which we call the alternating stock size problem , where the numbers of positive and negative integers in the input set S are equal. The problem is the same as that shown earlier, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79. Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovász, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.