Quantum annealing has emerged as a promising approach for solving NP-hard optimization problems, leveraging quantum phenomena such as quantum tunneling to navigate complex energy landscapes. However, the extent to which quantum tunneling contributes to performance enhancements compared to classical methods remains unclear. In this work, we present a comprehensive investigation combining experimental analysis, theoretical modeling, and algorithmic development to characterize when and why quantum annealing provides computational advantages.
We introduce a novel methodology for generating synthetic Quadratic Unconstrained Binary Optimization (QUBO) problems with controlled gradient variance, enabling systematic investigation of landscape characteristics that favor quantum approaches. Our experimental evaluation encompasses four canonical NP-hard problems: Graph Partitioning, Max Cut, Number Partitioning, and Set Cover. Using D-Wave's Advantage2 quantum annealer with 4,400+ qubits, we compare quantum annealing against classical solvers including simulated annealing, stochastic gradient descent, and commercial optimization software.
Our results demonstrate that quantum annealing shows measurable advantages when energy landscapes exhibit high gradient variance (
>0.3), suggesting that quantum tunneling effects are most beneficial for rugged optimization landscapes. We provide a theoretical justification for this empirical observation through a WKB-approximation-based model connecting gradient variance to barrier width and tunneling probability. This model achieves
R2=0.90 correlation with experimental data and yields quantitative predictions for quantum advantage thresholds.
Abstract: Quantum-enhanced Stochastic Gradient Descent (Q-SGD) is a novel optimization algorithm that integrates quantum computation to accelerate exploration of the solution space, offering a significant advantage over classical methods, particularly in complex optimization problems. This paper explores the potential of quantum annealing and gate operations to refine the optimization process, leading to faster convergence and improved results. We present a theoretical framework and preliminary experiments demonstrating the efficacy of this approach.
Quantum-enhanced gradient descent offers a promising approach to accelerate and improve the training of deep learning models. This research investigates the potential of integrating quantum annealing techniques into the gradient descent optimization process, aiming to overcome limitations of classical methods in navigating complex loss landscapes. The core claim is that quantum annealing can significantly enhance convergence speed and robustness, particularly in deep learning scenarios. The paper presents a theoretical analysis and preliminary implementation demonstrating the effectiveness of this approach, highlighting the potential benefits and challenges of this novel methodology.