  We prove concentration bounds for the following classes of quantum states:
(i) output states of shallow quantum circuits, answering an open question from
[DPMRF22]; (ii) injective matrix product states; (iii) output states of dense
Hamiltonian evolution, i.e. states of the form $e^{\iota H^{(p)}} \cdots
e^{\iota H^{(1)}} |\psi_0\rangle$ for any $n$-qubit product state
$|\psi_0\rangle$, where each $H^{(i)}$ can be any local commuting Hamiltonian
satisfying a norm constraint, including dense Hamiltonians with interactions
between any qubits. Our proofs use polynomial approximations to show that these
states are close to local operators. This implies that the distribution of the
Hamming weight of a computational basis measurement (and of other related
observables) concentrates.
  An example of (iii) are the states produced by the quantum approximate
optimisation algorithm (QAOA). Using our concentration results for these
states, we show that for a random spin model, the QAOA can only succeed with
negligible probability even at super-constant level $p = o(\log \log n)$,
assuming a strengthened version of the so-called overlap gap property. This
gives the first limitations on the QAOA on dense instances at super-constant
level, improving upon the recent result [BGMZ22].
