  Quantum permutation matrices and quantum magic squares are generalizations of
permutation matrices and magic squares, where the entries are no longer numbers
but elements from arbitrary (non-commutative) algebras. The famous
Birkhoff--von Neumann Theorem characterizes magic squares as convex
combinations of permutation matrices. In the non-commutative case, the
corresponding question is: Does every quantum magic square belong to the matrix
convex hull of quantum permutation matrices? That is, does every quantum magic
square dilate to a quantum permutation matrix? Here we show that this is false
even in the simplest non-commutative case. We also classify the quantum magic
squares that dilate to a quantum permutation matrix with commuting entries, and
prove a quantitative lower bound on the diameter of this set. Finally, we
conclude that not all Arveson extreme points of the free spectrahedron of
quantum magic squares are quantum permutation matrices.
