Have a personal or library account? Click to login
The Overlap Gap Property Limits Limit Swapping in the QAOA Cover

The Overlap Gap Property Limits Limit Swapping in the QAOA

Quantum Information & Computation
Volume 25 (2025): Issue 4 (August 2025)
By: Mark Goh  
Open Access
|Aug 2025

Figures & Tables

Figure 1.

Plot of a typical cluster of solutions. Y-axis indicates fraction of clauses satisfied and X-axis represents the Hamming distance from the state |1〉⊗n (e.g.the state |–1〉⊗n/2 ⊗ |1⊗n/2 hasavalue 0.5 on the X-axis.
Plot of a typical cluster of solutions. Y-axis indicates fraction of clauses satisfied and X-axis represents the Hamming distance from the state |1〉⊗n (e.g.the state |–1〉⊗n/2 ⊗ |1⊗n/2 hasavalue 0.5 on the X-axis.

Figure 2.

Typical evolution of the overlap spectrum of a n = 30 Max-3-XORSAT instance with constant degree 15. Here, the plot is based on the Hamming distance rather than overlaps. Typically, the optimal solution and the first few optimal solutions do not exhibit the OGP. At some distance ϵ away from the optimal solution, the OGP occurs. Increasing ϵ further includes additional sub-optimal solution until the set of overlaps is dense.
Typical evolution of the overlap spectrum of a n = 30 Max-3-XORSAT instance with constant degree 15. Here, the plot is based on the Hamming distance rather than overlaps. Typically, the optimal solution and the first few optimal solutions do not exhibit the OGP. At some distance ϵ away from the optimal solution, the OGP occurs. Increasing ϵ further includes additional sub-optimal solution until the set of overlaps is dense.

Figure 3.

The overlap spectrum of an instance of the SK model with = 45. No gap was observed and including additional suboptimal solution merely monotonically increases the overlap until the set of overlap is dense.
The overlap spectrum of an instance of the SK model with = 45. No gap was observed and including additional suboptimal solution merely monotonically increases the overlap until the set of overlap is dense.
DOI: https://doi.org/10.2478/qic-2025-0018 | Journal eISSN: 3106-0544 | Journal ISSN: 1533-7146
Journal RSS Feed
Language: English
Page range: 329 - 343
Submitted on: Apr 29, 2025
Accepted on: Jun 24, 2025
Published on: Aug 22, 2025
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
QAO,
overlap gap property,
combinatorial optimization,
spin glass
Related subjects:
Physics,
Quantum physics,
Mathematics,
Applied mathematics,
Computer sciences,
Computer sciences in the humanities,
Computer sciences,
Computer sciences in natural sciences

© 2025 Mark Goh, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Previous articleVolume 25 (2025): Issue 4 (August 2025)Next article