Several central problems in quantum information theory (such as measurement compatibility and quantum steering) can be rephrased as membership in the minimal matrix convex set corresponding to special polytopes (such as the hypercube or its dual). In this article, we generalize this idea and introduce the notion of polytope compatibility, by considering arbitrary polytopes. We find that semiclassical magic squares correspond to Birkhoff polytope compatibility. In general, we prove that polytope compatibility is in one-to-one correspondence with measurement compatibility, when the measurements have some elements in common and the post-processing of the joint measurement is restricted. Finally, we consider how much tuples of operators with appropriate joint numerical range have to be scaled in the worst case in order to become polytope compatible and give both analytical sufficient conditions and numerical ones based on linear programming.
We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where ϵ is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).
We give a method for computing asymptotic formulas and approximations for the volumes of spectrahedra, based on the maximum-entropy principle from statistical physics. The method gives an approximate volume formula based on a single convex optimization problem of minimizing −logdetP over the spectrahedron. Spectrahedra can be described as affine slices of the convex cone of positive semi-definite (PSD) matrices, and the method yields efficient deterministic approximation algorithms and asymptotic formulas whenever the number of affine constraints is sufficiently dominated by the dimension of the PSD cone. Our approach is inspired by the work of Barvinok and Hartigan who used an analogous framework for approximately computing volumes of polytopes. Spectrahedra, however, possess a remarkable feature not shared by polytopes, a new fact that we also prove: central sections of the set of density matrices (the quantum version of the simplex) all have asymptotically the same volume. This allows for very general approximation algorithms, which apply to large classes of naturally occurring spectrahedra. We give two main applications of this method. First, we apply this method to what we call the "multi-way Birkhoff spectrahedron" and obtain an explicit asymptotic formula for its volume. This spectrahedron is the set of quantum states with maximal entanglement (i.e., the quantum states having univariant quantum marginals equal to the identity matrix) and is the quantum analog of the multi-way Birkhoff polytope. Second, we apply this method to explicitly compute the asymptotic volume of central sections of the set of density matrices.