What is the implication of locality in QAOA?

Consider a nearest-neighbor Ising Hamiltonian $$H = sum_{i=1}^n J_i sigma_i^z sigma_{i+1}^z.$$ Let $X = sum_{i=1}^n sigma_i^x$. The QAOA ansatz is $$|mathbf{beta}, mathbf{gamma}rangle = expleft(-ibeta_1 X right)expleft(-igamma_1 H right) dots expleft(-ibeta_p X right)expleft(-igamma_p H right) |+rangle^{otimes n}$$ The expectation value of an operator $A$ under this ansatz is $langle A rangle = langlemathbf{beta}, mathbf{gamma}|A|mathbf{beta}, mathbf{gamma}rangle$.

Let's say that $A$ is supported only on sites $2$ and $3$. And consider $p=1$. Then we see that begin{align*} langle A rangle &= langle +|^{otimes n} exp(igamma_1 H)exp(ibeta_1 X)Aexp(-ibeta_1 X)exp(-igamma_1 H) |+rangle^{otimes n} \ &= langle +|^{otimes n} expleft(igamma_1 Hright)expleft(ibeta_1 (sigma_2^x + sigma_3^x)right)Aexpleft(-ibeta_1 (sigma_2^x + sigma_3^x)right)expleft(-igamma_1 Hright) |+rangle^{otimes n} \ &= langle +|^{otimes n} expleft(igamma_1 left(J_1 sigma_1^z sigma_2^z + J_2 sigma_2^z sigma_3^z + J_3 sigma_3^z sigma_4^zright)right)expleft(ibeta_1 (sigma_2^x + sigma_3^x)right)A\&qquadexpleft(-ibeta_1 (sigma_2^x + sigma_3^x)right)expleft(-igamma_1 left(J_1 sigma_1^z sigma_2^z + J_2 sigma_2^z sigma_3^z + J_3 sigma_3^z sigma_4^zright)right) |+rangle^{otimes n} \ end{align*} where:

• in the second line we used that all the other $sigma_i^x$ terms commuted through $A$ and canceled, since $A$ is only supported on 2 and 3.
• in the third line we used that all the other $sigma_i^z sigma_{i+1}^z$ terms in $H$ commute through $A$ and canceled.

Now look at the last line. Imagine if $p=2$. Then we would have another $exp(-i beta_2 X)$ to worry about. This time though, the $sigma_1^z$ and $sigma_4^z$ terms would get in the way of $sigma_1^x$ and $sigma_4^x$ commuting all the way through $A$ and canceling out. And then similarly, when we add the $exp(-i gamma_2 H)$ term, the $sigma_4^z sigma_5^z$ term would not commute all the way through and cancel, because now we have a $sigma_4^x$ term that gets in the way. You can imagine doing this again with $p=3$, and so on.

So in summary:

• we want to determine the expectation value of some local observable $A$.
• when we look at $langle A rangle$ at $p=1$, almost all of the terms commute through $A$ and cancel. So only the qubits very close to the support of $A$ actually contribute to $langle A rangle$.
• for each successive $p$, you get more terms (e.g. $sigma_i^x$ terms) "in the way", so the full expression for $langle A rangle$ includes qubit terms that are less local to $A$.
• eventually, all the qubits will contibute to $langle A rangle$, even though $A$ itself is only supported locally on a small number of qubits.

Potentially this is everything you already knew. For the TSP specifically, the exact meaning of $p$ depends on the particular Ising/QUBO formulation of the TSP. But certainly $p$ is related to the number of variables that are being taken into account at a time when calculating some observable quantity (this is what we just showed above). With TSP, variables are presumably related to nodes that must be visited, perhaps at a certain time interval. So then trying to optimize $langle A rangle$ for some $A$ would only take into account nodes to are somehow $f(p)$-local to $A$, where $f$ is just some monotonically increasing function. But recall with QAOA that you are trying to optimize $langle H rangle$. $H$ is composed of a sum of local observables. So I don't think it is right to say that level-$p$ gives you something related to a $p$-locally optimized solution. I think it is much more complicated, because you are optimizing a global sum of a bunch of $f(p)$-local quantities, which is itself still somehow global.

So in summary, how exactly $p$ is related to properties of the resulting solution to TSP is very nontrivial. Truthfully, it may be that this is a good thing. If we could say something as definite as "QAOA${}_p$ gives a $p$-locally optimized solution", then we would almost definitely find that classical "$p$"-local greedy methods would compete with and/or outperform QAOA${}_p$. The complicated behavior of how a solution is related to $p$ is potentially a reason that QAOA could give us heuristically better performance than classical approximation methods.

This is all just my impression, which could of course be wrong.