Optimized QUBO formulation methods for quantum computing
arXiv:2406.07681 · doi:10.1088/2058-9565/ae3b70
Abstract
Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement. We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and Advantage2 quantum annealers.
Minor changes
References in corpus (20)
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Annealing and Analog Quantum Computation
- Quantum computing for finance: overview and prospects
- Perspectives of quantum annealing: Methods and implementations
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Quantum Computing for Finance: State of the Art and Future Prospects
- Anderson localization casts clouds over adiabatic quantum optimization
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Challenges and Opportunities in Quantum Optimization
- Quantum Annealing: An Overview
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Towards large-scale quantum optimization solvers with few qubits
- The Power of Connection: Leveraging Network Analysis to Advance Receivable Financing
- Posiform Planting: Generating QUBO Instances for Benchmarking