2025/04/14 by Ningyi Xie, Xinwei Lee, Xie, Ningyi +9 · 1 citation
Computer Science · Engineering · #FOS: Physical sciences #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems #Quantum Physics (quant-ph) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2504.10651
openalex publication_date 2025/04/14 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
The variational quantum eigensolver (VQE) is an algorithm for finding the ground states of a given Hamiltonian. Its application to binary-formulated combinatorial optimization (CO) has been widely studied in recent years. However, typical VQE approaches for CO problems often suffer from local minima or barren plateaus, limiting their ability to achieve optimal solutions. The quantum imaginary time evolution (QITE) offers an alternative approach for effective ground-state preparation but requires large circuits to approximate non-unitary operations. Although compressed QITE (cQITE) reduces circuit depth, accumulated errors eventually cause energy increases. To address these challenges, we propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization. In numerical simulations for MaxCut on unweighted regular graphs, AWQV achieves near-optimal approximation ratios, while for weighted Erdős-Rényi instances, it outperforms the classical Goemans-Williamson algorithm.