Landscape-Similarity-Guided Optimization in QAOA

Across diverse synthetic and real-world interaction graphs, the variational landscapes of reduced Quantum Approximate Optimization Algorithm (QAOA) instances obtained via variable freezing exhibit a robust universality. Leveraging this structure, we introduce Doubly Optimized QAOA (DO-QAOA), which lowers runtime and quantum measurement overhead while maintaining a competitive approximation ratio gap (ARG). Adapting the replica-overlap framework of spin-glass physics, we define a landscape-overlap order parameter q to quantify geometric correlations between energy landscapes, revealing a sharp landscape-similarity transition as graph connectivity is tuned. Notwithstanding this transition, the dominant convex features of nearly all conditioned sub-instances remain aligned across both phases. Exploiting this persistence, DO-QAOA collapses the nominal 2^m reduced instances generated by freezing m qubits into K = O(1) effective landscape classes, eliminating the exponential proliferation in m. By leveraging landscape structure, DO-QAOA provides a scalable route to hybrid quantum-classical optimization under realistic hardware constraints, with potential applicability across variational quantum algorithms.