  We show that for every positive $\epsilon > 0$, unless NP $\subset$ BPQP, it
is impossible to approximate the maximum quadratic assignment problem within a
factor better than $2^{\log^{1-\epsilon} n}$ by a reduction from the maximum
label cover problem. Our result also implies that Approximate Graph Isomorphism
is not robust and is in fact, $1 - \epsilon$ vs $\epsilon$ hard assuming the
Unique Games Conjecture.
  Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem
based on rounding of the linear programming relaxation often used in the state
of the art exact algorithms.
