Obstacles to Variational Quantum Optimization from Symmetry Protection

Area of Science:

• Quantum computing
• Quantum algorithms
• Optimization

Background:

• The quantum approximate optimization algorithm (QAOA) uses parameterized quantum circuits to find solutions for optimization problems.
• QAOA's ability to outperform classical algorithms remains an open research question.

Purpose of the Study:

• To investigate the fundamental limitations of the standard QAOA.
• To propose and evaluate a modified, nonlocal version of QAOA.

Main Methods:

• Analysis of QAOA limitations stemming from variational state symmetry and locality.
• Numerical simulations comparing standard QAOA, a nonlocal QAOA variant, and the classical Goemans-Williamson algorithm.

Main Results:

• Identified inherent limitations in standard QAOA due to state symmetry and locality.
• Demonstrated that the classical Goemans-Williamson algorithm surpasses standard QAOA for specific MaxCut problem instances.
• Showcased significant performance improvements of the nonlocal QAOA over the standard version for frustrated Ising models.

Conclusions:

• Standard QAOA faces fundamental limitations that hinder its performance.
• A nonlocal QAOA approach offers a promising avenue for enhanced optimization capabilities.
• The proposed nonlocal QAOA variant demonstrates superior performance on challenging optimization problems.