Alleviating the quantum Big- problem
arXiv:2307.10379 · doi:10.1038/s41534-025-01067-0
Abstract
A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight of the penalty terms. Classically known as the "Big-" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big- problem, revealing NP-hardness in finding the optimal and establishing bounds on the Hamiltonian spectral gap , inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.
13 pages, 4 figures
References in corpus (20)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Efficient Z-Gates for Quantum Computing
- Variational ansatz-based quantum simulation of imaginary time evolution
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Finding Exponential Product Formulas of Higher Orders
- Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Qibo: a framework for quantum simulation with hardware acceleration
- Scalable Semidefinite Programming
- Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Penalty Weights in QUBO Formulations: Permutation Problems
- Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
- The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
- Practical Integer-to-Binary Mapping for Quantum Annealers
- Variational quantum iterative power algorithms for global optimization
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization