Abstract
We propose a circuit-model quantum algorithm for eigenpath traversal that is based on a combination of concepts from Grover's search and adiabatic quantum computation. Our algorithm deploys a sequence of reflections determined from eigenspaces of instantaneous Hamiltonians defined along an adiabatic schedule in order to prepare a ground state of a target problem Hamiltonian. We provide numerical evidence suggesting that, for combinatorial search problems, our algorithm can find a solution faster, on average, than Grover's search. We demonstrate our findings by applying both algorithms to solving the NP-hard MAX-2SAT problem.
Introduction
Quantum optimization algorithms typically follow two distinct paradigms: Grover-like searches, which offer quadratic speedups for unstructured data, and Adiabatic Quantum Computation (AQC), which leverages problem structure by slowly evolving a system's ground state. While Grover's search is mathematically optimal for black-box functions, it fails to exploit the internal structure of real-world problems. Conversely, AQC is highly effective for structured problems but requires continuous time evolution, which is difficult to implement on digital, gate-based quantum hardware.
We introduce the Reflection-Based Adiabatic (RBA) algorithm to bridge this gap. By utilizing a sequence of discrete reflections to navigate an "eigenpath," RBA combines the geometric efficiency of Grover-style operations with the problem-aware nature of adiabatic evolution.
Methodology: Reflection-Based Eigenpath Traversal
The core of the RBA algorithm is eigenpath traversal—moving a quantum state along the ground states of a series of intermediate Hamiltonians. Unlike the Quantum Zeno effect, which uses projective measurements that "collapse" the state, RBA utilizes discrete reflections. Geometrically, a reflection around an intermediate state provides a "double nudge" toward the target state, maintaining higher overlap with the final ground state than a binary measurement.
Circuit Implementation via QPE
Implementing reflections around unknown ground states requires a sophisticated circuit. The RBA algorithm employs Quantum Phase Estimation (QPE) to identify these states. The circuit marks the ground state by storing its energy in an ancilla register, applies a phase flip (Pauli-Z) if the energy falls below a specific threshold $E^*$, and then uncomputes the register to return the ancilla to its initial state.
The reflection schedule—the specific points along the adiabatic path where reflections occur—can be optimized classically using protocols like Nelder-Mead to maximize the final success probability.
Performance Evaluation on MAX-2SAT
To benchmark the RBA algorithm, we applied it to randomly generated instances of the MAX-2SAT problem, an NP-hard combinatorial optimization task. We tested problem sizes ranging from $n = 5$ to $13$ variables and compared the results directly against Grover’s search.
Our primary metric was Time-to-Solution (TTS), which accounts for both the probability of success and the computational cost of each iteration. While each RBA reflection is more gate-intensive than a Grover iteration due to the QPE overhead, the total number of iterations required for RBA grows much more slowly with system size.
As shown in the numerical results, RBA begins to outperform Grover's search as the problem complexity increases. For larger $n$, the TTS for RBA scales sub-linearly relative to Grover's search, suggesting a significant advantage for structured combinatorial problems.
Key Insights and Theoretical Connections
- Grover as a Boundary Case: Theoretical analysis reveals that Grover’s algorithm is a special, "low-resolution" case of RBA where the weights only alternate between the initial and final Hamiltonians. RBA generalizes this by adding intermediate steps that exploit problem structure.
- Trainability and Barren Plateaus: In hybrid quantum-classical optimization, the "barren plateau" phenomenon (vanishing gradients) is a major concern. We found that while gradient variance decays exponentially with system size, the decay rate (approximately 0.08) is significantly lower than in many other parameterized quantum circuits, indicating that RBA remains optimizable for practical problem sizes.
- Threshold Robustness: The algorithm demonstrates surprising resilience to the choice of energy thresholds in the QPE step, meaning it does not require perfect knowledge of the system's energy gaps to be effective.
Conclusion and Future Work
The Reflection-Based Adiabatic algorithm offers a promising path for digital quantum optimization by discretizing adiabatic evolution into efficient reflections. While current implementations require deep circuits that challenge NISQ-era hardware, techniques like qubitization could further reduce implementation costs. Future research will focus on scaling these findings to larger, industrially relevant problem sizes and exploring the algorithm's performance on other classes of structured optimization problems.
Summary updated