Experimental demonstration of improved quantum optimization with linear Ising penalties
Open Access
- 1 October 2024
- journal article
- research article
- Published by IOP Publishing in New Journal of Physics
- Vol. 26 (10) , 103005
Abstract
The standard approach to encoding constraints in quantum optimization is the quadratic penalty method. Quadratic penalties introduce additional couplings and energy scales, which can be detrimental to the performance of a quantum optimizer. In quantum annealing experiments performed on a D-Wave Advantage, we explore an alternative penalty method that only involves linear Ising terms and apply it to a customer data science problem. Our findings support our hypothesis that the linear Ising penalty method should improve the performance of quantum optimization compared to using the quadratic penalty method due to its more efficient use of physical resources. Although the linear Ising penalty method is not guaranteed to exactly implement the desired constraint in all cases, it is able to do so for the majority of problem instances we consider. For problems with many constraints, where making all penalties linear is unlikely to be feasible, we investigate strategies for combining linear Ising penalties with quadratic penalties to satisfy constraints for which the linear method is not well-suited. We find that this strategy is most effective when the penalties that contribute most to limiting the dynamic range are removed.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/T026715/2)
- dunnhumby
This publication has 42 references indexed in Scilit:
- A new class of hard problem instances for the 0–1 knapsack problemEuropean Journal of Operational Research, 2022
- Array programming with NumPyNature, 2020
- Support vector machines on the D-Wave quantum annealerComputer Physics Communications, 2020
- Quantum computing for finance: Overview and prospectsReviews in Physics, 2019
- Reverse quantum annealing approach to portfolio optimization problemsQuantum Machine Intelligence, 2019
- Embedding Inequality Constraints for Quantum Annealing Optimization2019
- Quantum annealing with manufactured spinsNature, 2011
- Minor-embedding in adiabatic quantum computation: I. The parameter setting problemQuantum Information Processing, 2008
- Random knapsack in expected polynomial timeJournal of Computer and System Sciences, 2004
- Penalty Functions1983