arXiv:2603.20567

Topological Obstructions in Quantum Adiabatic Algorithms

Prathamesh S. Joshi, Emil Prodan

quant-phSubmitted Mar 20, 2026• Announced Mar 24, 2026• 0 citations

Abstract

We point out that, when an optimization problem has more than one solution, the quantum adiabatic algorithms (QAA) encounter topological obstructions leading to adiabatic spectral flows where spectral branches unavoidably traverse the spectral gap above the ground states of the quantum Hamiltonians. This raises serious doubts about the validity of the algorithms in such situations. However, using the Max-Cut problem as an example, we explain and demonstrate here that QAAs correctly detect all existing solutions in one single run. This newly discovered capacity of QAAs to simultaneously detect multiple solutions to an optimization problem can have an important impact on future developments of quantum variational algorithms

Related papers

Topological Obstructions for Quantum Adiabatic Algorithms: Evidence from MaxCut Instances

Prathamesh S. Joshi

Quantum adiabatic algorithms are commonly analyzed through local spectral properties of an interpolating Hamiltonian, most notably the minimum energy gap. While this perspective captures an important constraint on adiabatic runtimes, it does not fully describe the global structure of spectral evolution in optimization problems with degenerate solution manifolds. In this work, we show that degeneracy alone imposes unavoidable global constraints on spectral flow, even in instances where adiabatic algorithms succeed with high probability. Focusing on digitized quantum adiabatic evolutions, we analyze the eigenphases of the cumulative unitary operator generated along the interpolation path. By explicitly tracking eigenphase trajectories, we demonstrate that multiple spectral bands are forced to interact, braid, and permute before coalescing into a degenerate manifold at the end of the evolution. This global reordering manifests as persistent spectral congestion and nontrivial band permutations that cannot be removed by increasing evolution time or refining the digitization. Using MaxCut instances with controlled degeneracy as a concrete setting, we extract quantitative diagnostics of spectral congestion and explicitly compute the induced band permutations. Our results show that successful adiabatic optimization can coexist with complex and constrained spectral flow, revealing a form of topological obstruction rooted in the global connectivity of eigenstates rather than in local gap closures. These findings highlight intrinsic limitations of gap-based analyses and motivate spectral-flow-based diagnostics for understanding adiabatic algorithms in degenerate optimization landscapes.

quant-pharXiv:2601.02255Jan 6, 20260 citations

Discrete Ricci Flow for Detecting Gaps in Adiabatic Quantum Processes

A. A. Rompokos, Paul Bogdan, EDMOND A. JONCKHEERE

Adiabatic Quantum Processes have been known to solve combinatorial optimization problems intractable by classical computational methods by exploiting the adiabatic theorem. The solution of the optimization problem is encoded in the ground state of a final Hamiltonian, which in turn can be targeted by adiabatically transitioning from the known ground state of an easy-to-prepare Hamiltonian to the ground state of the problem Hamiltonian. Our focus is to characterize topologically the minimum gap between the ground state and the first excited state, which is the bottleneck of the process in terms of its speed. Since the gap occurs at topologically steep ascent/descent of the ground/first excited states, it is proposed to utilize the curvature uniformization process of the Ricci flow to identify such gaps as areas of heavy curvature transport. Our results indicate that such gaps can be detected automatically in various Adiabatic Quantum Processes.

IEEE Conference on Decision and Control (CDC)Dec 9, 20250 citations

Energy landscapes for the quantum approximate optimization algorithm

Choy Boy, David J. Wales

Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024

Physical Review AJun 3, 20247 citations

Case studies in quantum adiabatic optimization

David Gosset

Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We

Jan 1, 20111 citation

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

WANG Fumin, NI Ming, ZHOU Ming, WU Yongzheng

When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.

Jan 1, 20200 citations

Adiabatic Quantum Optimization and Anderson Localization

B. L. Altshuler

Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. It turns out that due to a phenomenon similar to Anderson localization exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm.

Jan 1, 20100 citations