An entanglement perspective on the quantum approximate optimization algorithm

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 $N$-qubit product state $|0{⟩}^{\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.

arXiv comment12 pages, 7 figures

References in corpus (58)

• The density-matrix renormalization group in the age of matrix product states
• Variational Quantum Algorithms
• Chaos and Quantum Thermalization
• Thermalization and its mechanism for generic isolated quantum systems
• Area laws for the entanglement entropy - a review
• Ising formulations of many NP problems
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Localization of interacting fermions at high temperature
• Efficient simulation of one-dimensional quantum many-body systems
• Average Entropy of a Subsystem
• Adiabatic Quantum Computing
• An Area Law for One Dimensional Quantum Systems
• 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
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum entanglement in condensed matter systems
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Criticality, the area law, and the computational power of PEPS
• Classical simulation of quantum many-body systems with a tree tensor network
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Classical simulation of noninteracting-fermion quantum circuits
• Diffusive hydrodynamics of out-of-time-ordered correlators with charge conservation
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• What limits the simulation of quantum computers?
• $XY$-mixers: analytical and numerical results for QAOA
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Isometric Tensor Network States in Two Dimensions
• Filtering variational quantum algorithms for combinatorial optimization
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Benchmarking the Quantum Approximate Optimization Algorithm
• Implementation of the XY interaction family with calibration of a single pulse
• Quantum Entanglement of the Sachdev-Ye-Kitaev Models
• Two-component Structure in the Entanglement Spectrum of Highly Excited States
• Training A Quantum Optimizer
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Random free fermions: An analytical example of eigenstate thermalization
• Probing symmetries of quantum many-body systems through gap ratio statistics
• How many qubits are needed for quantum computational supremacy?
• The Page Curve for Fermionic Gaussian States
• Entanglement of random vectors
• Entanglement growth in diffusive systems
• Classical simulation of lossy boson sampling using matrix product operators
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution
• Progress toward favorable landscapes in quantum combinatorial optimization
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Quantum computing critical exponents
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation

Cited by in corpus (2)

• Entanglement entropy production in Quantum Neural Networks
• Information scrambling and entanglement in quantum approximate optimization algorithm circuits