Entanglement-assisted variational algorithm for discrete optimization problems
Lorenzo Fioroni, Vincenzo Savona · 2025
Read Entanglement-assisted variational algorithm for discrete optimization problems by Lorenzo Fioroni, Vincenzo Savona (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09078.txt.
Introduction
Lorenzo Fioroni and Vincenzo Savona offer a 2025 paper on hard choice problems that need the best pick from many options. Exact answers are often out of reach, so people use fast rules of thumb drawn from physics. The authors build a new rule of thumb that borrows ideas from quantum annealing, a method that lets a system settle into a low-energy state.
Their method uses smooth quantum states that can hold entanglement, the link that makes quantum systems hard to copy. Energy and slopes can be worked out with modest math, so problems with thousands of spins can be tried. Tests on a glass-like magnet model show speed and quality close to well-known rival methods.
Catalog record
| CREATOR | Lorenzo Fioroni, Vincenzo Savona |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09078
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Entanglement-assisted variational algorithm for discrete optimization problems Lorenzo Fioroni, Vincenzo Savona 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. I Introduction Optimization problems play a pivotal role in a wide range of fields. From optimizing the allocation of medical resources in healthcare systems [ 18 , 12 ] to improving energy distribution in smart grids [ 33 , 39 ] and enhancing traffic flow in urban areas [ 20 , 27 ] , these tasks aim to identify which input from a pre-defined set minimizes a given metric, referred to as the loss function . A paradigmatic class of optimization problems is that of Quadratic Unconstrained Binary Optimization (QUBO) [ 37 ] , where the loss function is a quadratic form of binary variables. Despite their simple formulation, QUBO problems are known to be computationally challenging, as they belong to the NP-Hard complexity class [ 7 , 58 ] . This means that no algorithm is known to solve an arbitrary QUBO instance in polynomial time, and the required computational resources grow exponentially with the problem size. At the same time, QUBO problems are of great practical relevance, as any other NP problem can be efficiently reduced to them [ 40 ] . Consequently, the development of fast algorithms for approximating the optimal solution of these problems is of great interest. These can be broadly divided into two categories: approximation algorithms and heuristics . Approximation algorithms aim to find a solution that is guaranteed to be up to a certain factor off the optimal one [ 15 , 24 ] , while heuristics aim to find a good solution in a reasonable amount of time, without any guarantee of optimality [ 8 ] . Multiple heuristics have been developed to tackle QUBO problems efficiently, often inspired by various areas of physics [ 60 , 29 , 11 , 57 , 51 , 61 ] . For example, simulated annealing [ 36 ] emulates the behavior of a system at finite temperature, exploring the configuration space via thermal fluctuations, while simulated bifurcation [ 25 ] draws inspiration from nonlinear dynamics to navigate the solution landscape efficiently. These physics-inspired heuristics have further motivated the development of specialized hardware accelerators, such as the Coherent Ising Machine [ 46 ] and the Fujitsu Digital Annealer [ 44 , 56 , 43 ] , among others. Quantum physics offers a promising approach to solving QUBO problems through quantum annealing [ 22 , 54 , 17 , 3 , 16 ] . In quantum annealing, the classical problem is first mapped onto the ground state of a quantum Hamiltonian, which is then obtained via adiabatic state preparation. Despite being the subject of extensive research, a definitive demonstration of the advantage of quantum annealing over classical heuristics remains an open question. Numerous studies have been conducted, aimed at simulating its underlying physical process to understand the effects of finite temperature, noise, diabatic transitions, and other deviations from the ideal scenario [ 23 , 45 , 14 ] . The goal of these studies is to describe the quantum state and its dynamics as accurately as possible, to ultimately characterize quantum annealing and identify its differences from classical optimization methods. To this purpose, a variety of techniques have been adopted, mostly relying either on Path Integral Monte Carlo (PIMC) [ 52 , 53 , 42 ] , or on Variational Monte Carlo (VMC) dynamics. In the latter case, several advanced variational Ansätze have been used to capture the many-body quantum correlations arising along the evolution [ 31 , 13 ] . While these studies are crucial for understanding the mechanisms of quantum annealing, they are not suitable for use as efficient optimization heuristics due to their high computational demands and unfavorable scaling with problem size. Additionally, many of these methods rely on Monte Carlo sampling, which further increases computational overhead. In contrast, a classical optimization algorithm inspired by quantum annealing might forgo some physical accuracy in favor of greater efficiency. Recent studies in this direction proposed using a product-state Ansatz to describe the state of the system [ 10 , 59 ] . This method, referred to as Local Quantum Annealing (LQA), allows simulating the state’s evolution analytically, avoiding the need for Monte Carlo sampling. However, the simplicity of the Ansatz severely limits the range of states it can represent, resulting in a fast but less accurate heuristic. In particular, it cannot capture any of the entangled states that arise during quantum annealing. In this work, we propose a quantum-inspired heuristic for solving QUBO problems. Drawing inspiration from the quantum annealing process, we develop an efficient variational procedure that emulates its dynamics in a fully analytical way. The variational Ansatz we employ is based on Generalized Group-Theoretic Coherent States (GCS) [ 26 , 55 ] , which allow for the efficient evaluation of the energy and its gradient. At the same time, it captures to some extent the entanglement structure that emerges during the quantum annealing process, thus leveraging the advantage it provides. Without the need for Monte Carlo sampling, our algorithm is highly scalable and allows for the efficient optimization of problems with thousands of variables. We benchmark our algorithm on random instances of the three-dimensional Edwards-Anderson model [ 7 ] , comparing its performance to that of standard heuristics such as Simulated Annealing (SA) [ 36 ] , Local Quantum Annealing (LQA) [ 10 ] , and Parallel Tempering with Iso-energetic Cluster Moves (PT-ICM) [ 48 ] . We identify parameter regimes where our algorithm holds an advantage over the other methods tested, proving that it could serve as a viable alternative to other state-of-the-art classical heuristics. II Results A QUBO problem is fully specified by a real-valued and symmetric matrix J and a real-valued bias vector \mathbf{b} through the relation \mathbf{z}^{\star}=\argmin_{\mathbf{z}\in\quantity{0,\;1}^{N}}\left[\sum_{i,j=1}^{N}J_{ij}z_{i}z_{j}+\sum_{i=1}^{N}b_{i}z_{i}\right]\text{,} (1) which also defines its solution \mathbf{z}^{\star} . Up to a linear transformation of its variables, the binary optimization problem in Eq. ( 1 ) can be mapped onto \mathbf{s}^{\star}=\argmin_{\mathbf{s}\in\quantity{\pm 1}^{N}}\left[\sum_{i,j=1}^{N}W_{ij}s_{i}s_{j}+\sum_{i=1}^{N}c_{i}s_{i}\right]\text{,} (2) where W_{ij}=J_{ij}/4 and c_{i}=(b_{i}+\sum_{j}J_{ij})/2 . In the following, we will consider QUBO problems expressed as in Eq. ( 2 ). Without loss of generality, we will from now on omit the bias term \mathbf{c}