  Many quantum algorithms seek to output a specific bitstring solving the
problem of interest--or a few if the solution is degenerate. It is the case for
the quantum approximate optimization algorithm (QAOA) in the limit of large
circuit depth, which aims to solve quadratic unconstrained binary optimization
problems. Hence, the expected final state for these algorithms is either a
product state or a low-entangled superposition involving a few bitstrings. What
happens in between the initial $N$-qubit product state $\vert 0\rangle^{\otimes
N}$ and the final one regarding entanglement? Here, we consider the QAOA
algorithm for solving the paradigmatic Max-Cut problem on different types of
graphs. We study the entanglement growth and spread resulting from randomized
and optimized QAOA circuits and find that there is a volume-law entanglement
barrier between the initial and final states. We also investigate the
entanglement spectrum in connection with random matrix theory. In addition, we
compare the entanglement production with a quantum annealing protocol aiming to
solve the same Max-Cut problems. Finally, we discuss the implications of our
results for the simulation of QAOA circuits with tensor network-based methods
relying on low-entanglement for efficiency, such as matrix product states.
