  The QCD axion fails to solve the strong CP problem unless all explicit PQ
violating, Planck-suppressed, dimension n<10 operators are forbidden or have
exponentially small coefficients. We show that all theories with a QCD axion
contain an irreducible source of explicit PQ violation which is proportional to
the determinant of the Yukawa interaction matrix of colored fermions.
Generically, this contribution is of low operator dimension and will
drastically destabilize the axion potential, so its suppression is a necessary
condition for solving the strong CP problem. We propose a mechanism whereby the
PQ symmetry is kept exact up to n=12 with the help of the very same flavor
symmetries which generate the hierarchical quark masses and mixings of the SM.
This "axion flavor protection" is straightforwardly realized in theories which
employ radiative fermion mass generation and grand unification. A universal
feature of this construction is that the heavy quark Yukawa couplings are
generated at the PQ breaking scale.
