Suppose I am solving the TSP formulated as a QUBO problem using QAOA. I understand from the original paper that there is a parameter $p$ which sets the number of steps used in the alternating ansatz. Also, $p$ represents the locality of the terms in the ansatz.

So what does this "locality" mean for our real world TSP problem? Does it mean that we can only find optimal paths that are locally optimised up to $p$ edges radius?


1 Answer 1


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 = \exp\left(-i\beta_1 X \right)\exp\left(-i\gamma_1 H \right) \dots \exp\left(-i\beta_p X \right)\exp\left(-i\gamma_p H \right) |+\rangle^{\otimes n}$$ The expectation value of an operator $A$ under this ansatz is $\langle A \rangle = \langle\mathbf{\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(i\gamma_1 H)\exp(i\beta_1 X)A\exp(-i\beta_1 X)\exp(-i\gamma_1 H) |+\rangle^{\otimes n} \\ &= \langle +|^{\otimes n} \exp\left(i\gamma_1 H\right)\exp\left(i\beta_1 (\sigma_2^x + \sigma_3^x)\right)A\exp\left(-i\beta_1 (\sigma_2^x + \sigma_3^x)\right)\exp\left(-i\gamma_1 H\right) |+\rangle^{\otimes n} \\ &= \langle +|^{\otimes n} \exp\left(i\gamma_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^z\right)\right)\exp\left(i\beta_1 (\sigma_2^x + \sigma_3^x)\right)A\\&\qquad\exp\left(-i\beta_1 (\sigma_2^x + \sigma_3^x)\right)\exp\left(-i\gamma_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^z\right)\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.

  • $\begingroup$ Thanks Joe. Admittedly I've stepped back from this topic for quite some time now so it's hard for me to give your answer all the attention it deserves. For the first half, yes I was working with that as a premise. For the second half, I suppose the answer is we don't really know. It's been 5 months with no specific answer so maybe it's the topic of a research project. $\endgroup$ Commented Jan 1, 2021 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.