Experimental demonstration of improved quantum optimization with linear Ising penalties

Mirkarimi, Puya; Hoyle, David C; Williams, Ross; Chancellor, Nicholas

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.

Citation

Mirkarimi, P., Hoyle, D. C., Williams, R., & Chancellor, N. (2024). Experimental demonstration of improved quantum optimization with linear Ising penalties. New Journal of Physics, 26(10), Article 103005. https://doi.org/10.1088/1367-2630/ad7e4a

• Journal Article Type: Article
• Acceptance Date: Sep 23, 2024
• Online Publication Date: Oct 8, 2024
• Publication Date: Oct 1, 2024
• Deposit Date: Oct 25, 2024
• Publicly Available Date: Oct 25, 2024
• Journal: New Journal of Physics
• Electronic ISSN: 1367-2630
• Publisher: IOP Publishing
• Peer Reviewed: Peer Reviewed
• Volume: 26
• Issue: 10
• Article Number: 103005
• DOI: https://doi.org/10.1088/1367-2630/ad7e4a
• Keywords: quantum optimization, quantum annealing, constrained optimization
• Public URL: https://durham-repository.worktribe.com/output/2954855