Genuine Multipartite Entanglement in Quantum Optimization

The ability to generate bipartite entanglement in quantum computing technologies is widely regarded as pivotal. However, the role of genuinely multipartite entanglement is much less understood than bipartite entanglement, particularly in the context of solving complicated optimization problems using quantum devices. It is thus crucial from both the algorithmic and hardware standpoints to understand whether multipartite entanglement contributes to achieving a good solution. Here, we tackle this challenge by analyzing genuine multipartite entanglement - quantified by the generalized geometric measure - generated in Trotterized quantum annealing and the quantum approximate optimization algorithm. Using numerical benchmarks, we analyze its occurrence in the annealing schedule in detail. We observe a multipartite-entanglement barrier, and we explore how it correlates to the algorithm's success. We also prove how multipartite entanglement provides an upper bound to the overlap of the instantaneous state with an exact solution. Vice versa, the overlaps to the initial and final product states, which can be easily measured experimentally, offer upper bounds for the multipartite entanglement during the entire schedule. Our results help to shed light on how complex quantum correlations come to bear as a resource in quantum optimization.