Entanglement-assisted variational algorithm for discrete optimization problems
arXiv:2501.09078 · doi:10.1038/s42005-025-02338-0
Abstract
From fundamental sciences to economics and industry, discrete optimization problems are ubiquitous. Yet, their complexity often renders exact solutions intractable, necessitating the use of approximate methods. Heuristics inspired by classical physics have long played a central role in this domain. More recently, quantum annealing has emerged as a promising alternative, with hardware implementations realized on both analog and digital quantum devices. Here, we develop a heuristic inspired by quantum annealing, using Generalized Coherent States as a parameterized variational Ansatz to represent the quantum state. This framework allows for the analytical computation of energy and gradients with low-degree polynomial complexity, enabling the study of large problems with thousands of spins. Concurrently, these states capture non-trivial entanglement, crucial for the effectiveness of quantum annealing. We benchmark the heuristic on the three-dimensional Edwards-Anderson model and compare the solution quality and runtime of our method to other popular heuristics. Our findings suggest that it offers a scalable way to leverage quantum effects for complex optimization problems, with the potential to complement or improve upon conventional alternatives in large-scale applications.
References in corpus (22)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Quantum annealing with more than one hundred qubits
- Quantum Annealing and Analog Quantum Computation
- Defining and detecting quantum speedup
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- Quantum versus Classical Annealing of Ising Spin Glasses
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- A deceptive step towards quantum speedup detection
- Ground state approximation for strongly interacting systems in arbitrary dimension
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
- Performance evaluation of coherent Ising machines against classical neural networks
- Reexamination of the evidence for entanglement in the D-Wave processor
- Multidimensional hyperspin machine
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- A variational method based on weighted graph states
- A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model
- Extending relax-and-round combinatorial optimization solvers with quantum correlations
- Generalization of group-theoretic coherent states for variational calculations
- Qudit-inspired optimization for graph coloring