An entanglement perspective on the quantum approximate optimization algorithm
arXiv:2206.07024 · doi:10.1103/PhysRevA.106.022423
Abstract
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 -qubit product state 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.
12 pages, 7 figures
References in corpus (8)
- The density-matrix renormalization group in the age of matrix product states
- Thermalization and its mechanism for generic isolated quantum systems
- Localization of interacting fermions at high temperature
- The distribution of the ratio of consecutive level spacings in random matrix ensembles
- A class of quantum many-body states that can be efficiently simulated
- Criticality, the area law, and the computational power of PEPS
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Entanglement of random vectors