Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
arXiv:2410.12636 · doi:10.1088/2632-2153/addb97
Abstract
Quadratic Unconstrained Binary Optimization (QUBO) sits at the heart of many industries and academic fields such as logistics, supply chain, finance, pharmaceutical science, chemistry, IT, and energy sectors, among others. These problems typically involve optimizing a large number of binary variables, which makes finding exact solutions exponentially more difficult. Consequently, most QUBO problems are classified as NP-hard. To address this challenge, we developed a powerful feedforward neural network (FNN) optimizer for arbitrary QUBO problems. In this work, we demonstrate that the FNN optimizer can provide high-quality approximate solutions for large problems, including dense 80-variable weighted MaxCut and random QUBOs, achieving an average accuracy of over 99% in less than 1.1 seconds on an 8-core CPU. Additionally, the FNN optimizer outperformed the Gurobi optimizer by 72% on 200-variable random QUBO problems within a 100-second computation time limit, exhibiting strong potential for real-time optimization tasks. Building on this model, we explored the novel approach of integrating FNNs with a quantum annealer-based activation function to create a quantum-classical encoder-decoder (QCED) optimizer, aiming to further enhance the performance of FNNs in QUBO optimization.
References in corpus (31)
- A variational eigenvalue solver on a quantum processor
- Machine learning and the physical sciences
- QuTiP: An open-source Python framework for the dynamics of open quantum systems
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Evaluating analytic gradients on quantum hardware
- Observation of Rydberg blockade between two atoms
- Quantum walks: a comprehensive review
- Hands-on Bayesian Neural Networks -- a Tutorial for Deep Learning Users
- Observation of collective excitation of two individual atoms in the Rydberg blockade regime
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Controlling many-body dynamics with driven quantum scars in Rydberg atom arrays
- Many-body interferometry of a Rydberg-dressed spin lattice
- Combinatorial Optimization with Physics-Inspired Graph Neural Networks
- Collective many-body interaction in Rydberg dressed atoms
- Interactions Between Rydberg-Dressed Atoms
- Tutorial: Calculation of Rydberg interaction potentials
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Many-body theory of excitation dynamics in an ultracold Rydberg gas
- Measuring Analytic Gradients of General Quantum Evolution with the Stochastic Parameter Shift Rule
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- Rydberg blockade based parity quantum optimization
- Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
- Real-time Trading System based on Selections of Potentially Profitable, Uncorrelated, and Balanced Stocks by NP-hard Combinatorial Optimization
- Preparation of ordered states in ultra-cold gases using Bayesian optimization
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
- Rydberg-atom graphs for quadratic unconstrained binary optimization problems
- Analog quantum variational embedding classifier
- On the hardness of quadratic unconstrained binary optimization problems
- Integer Programming Using A Single Atom