Hamiltonian-Oriented Homotopy QAOA

Akash Kundu, Ludmila Botelho, Adam GlosarXiv 2023 · DOI · arXiv

Hamiltonian-Oriented Homotopy QAOA

Abstract

The classical homotopy optimization approach has the potential to deal with highly nonlinear landscapes, such as the energy landscape of QAOA problems. Following this motivation, we introduce Hamiltonian-Oriented Homotopy QAOA (HOHo-QAOA), a heuristic method for combinatorial optimization using QAOA based on classical homotopy optimization. The method utilizes a homotopy map that produces an optimization problem for each value of an interpolating parameter. Consequently, HOHo-QAOA decomposes the optimization of QAOA into several loops, each using a mixture of the mixer and the objective Hamiltonian for cost function evaluation. We conclude that HOHo-QAOA improves the search for low-energy states in the nonlinear energy landscape and outperforms other variants of QAOA.

Introduction: The Challenge of the QAOA Landscape

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for achieving quantum advantage on Near-Intermediate Scale Quantum (NISQ) devices. Its success depends on finding optimal variational parameters (angles) to minimize the expectation value of a target Hamiltonian. However, the "energy landscape" of these parameters is notoriously difficult to navigate. As illustrated in Figure 1, the landscape is highly non-linear and characterized by a multitude of local minima, which often trap standard optimization algorithms and prevent them from reaching the global minimum.

The normalized energy landscape $E_{\text{norm}}$ as a function of the variational parameters $\gamma_j$ and $\beta_j$ for different layers, showing high non-linearity and multiple local minima.

The authors provide a mathematical proof that this complexity scales poorly: the energy landscape is a sum of numerous cosine functions, with the number of "waves" increasing quadratically or exponentially with problem size, explaining why standard optimization often fails.

Methodology: HOHo-QAOA and Homotopy Optimization

To overcome these "bumpy" landscapes, the researchers propose Hamiltonian-Oriented Homotopy QAOA (HOHo-QAOA). This heuristic leverages classical homotopy optimization by defining a continuous transformation (a homotopy map) between a simple, solvable problem and the complex target problem.

The map is defined as: $$H(\alpha) = (1-\alpha)H_{\text{mix}} + \alpha H_{\text{obj}}$$ where $\alpha \in [0, 1]$ is the interpolating parameter. At $\alpha = 0$, the system is governed by the mixer Hamiltonian ($H_{\text{mix}}$), which is trivial to optimize. As $\alpha$ increases toward 1, the objective Hamiltonian ($H_{\text{obj}}$) becomes dominant.

HOHo-QAOA proceeds iteratively: it finds optimal parameters for a small $\alpha$, then uses those results as the starting point for the next, slightly larger $\alpha$. This "solution tracking" allows the algorithm to stay within a favorable region of the landscape as it evolves toward the target problem.

The Role of Initialization

A critical finding of the study is the importance of the initialization strategy. The authors compared three approaches: Random-Random (RR), Non-Zero Random (NZR), and Zero-Random (ZR). As shown in Figure 4, the Zero-Random (ZR) strategy is exceptionally effective. By starting problem angles at zero, the algorithm begins precisely at the ground state of the mixer Hamiltonian, providing a stable and mathematically rigorous "anchor" for the homotopy path.

Comparison of normalized energy $E^*_{\text{norm}}(\alpha)$ across different initialization strategies (RR, NZR, ZR). The ZR strategy (right) shows the most consistent and lowest energy paths as the homotopy parameter $\alpha$ approaches 1.

Key Results and Robustness

HOHo-QAOA was benchmarked on Weighted Max-Cut problems using Barabási-Albert graphs (6 to 18 qubits). Key findings include:

  • Superior Performance: HOHo-QAOA consistently outperformed standard QAOA and Trajectory-based QAOA (T-QAOA), particularly as the number of layers ($L$) or qubits ($N$) increased.
  • Region of Stability: The method is remarkably robust to the choice of the initial parameter $\alpha_{\text{init}}$ and the step size $\alpha_{\text{step}}$. This "region of stability" reduces the need for extensive hyperparameter tuning.
  • Lower Energy States: In benchmarks on 10-node graphs, HOHo-QAOA achieved significantly lower median energy levels than competing heuristics, indicating higher-quality solutions.

Conclusion and Future Outlook

HOHo-QAOA provides a robust framework for navigating the complex optimization landscapes inherent in quantum algorithms. While currently demonstrated on classical simulations, future work will involve testing on actual quantum hardware to assess sensitivity to noise and decoherence. Additionally, the researchers suggest extending this homotopy approach to other mixer types and more complex combinatorial optimization problems.

Summary updated

Abstract

The classical homotopy optimization approach has the potential to deal with highly nonlinear landscape, such as the energy landscape of QAOA problems. Following this motivation, we introduce Hamiltonian-Oriented Homotopy QAOA (HOHo-QAOA), that is a heuristic method for combinatorial optimization using QAOA, based on classical homotopy optimization. The method consists of a homotopy map that produces an optimization problem for each value of interpolating parameter. Therefore, HOHo-QAOA decomposes the optimization of QAOA into several loops, each using a mixture of the mixer and the objective Hamiltonian for cost function evaluation. Furthermore, we conclude that the HOHo-QAOA improves the search for low energy states in the nonlinear energy landscape and outperforms other variants of QAOA.
BibTeX
@misc{kundu2023hamiltonian,
  author = {Akash Kundu and Ludmila Botelho and Adam Glos},
  title = {{Hamiltonian-Oriented Homotopy QAOA}},
  year = {2023},
  eprint = {2301.13170},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.13170},
}
Figure