Optimum-Preserving QUBO Parameter Compression

Quadratic unconstrained binary optimization (QUBO) problems are well-studied, not least because they can be approached using contemporary quantum annealing or classical hardware acceleration. However, due to limited precision and hardware noise, the effective set of feasible parameter values is severely restricted. As a result, otherwise solvable problems become harder or even intractable. In this work, we study the implications of solving QUBO problems under limited precision. Specifically, it is shown that the problem’s dynamic range has a crucial impact on the problem’s robustness against distortions. We show this by formalizing the notion of preserving optima between QUBO instances and explore to which extend parameters can be modified without changing the set of minimizing solutions. Based on these insights, we introduce techniques to reduce the dynamic range of a given QUBO instance based on theoretical bounds of the minimal energy value. An experimental evaluation on random QUBO instances as well as QUBO-encoded Binary Clustering and Subset Sum problems show that our theoretical findings manifest in practice. Results on quantum annealing hardware show that the performance can be improved drastically when following our methodology.

  • Published in:
  • Type:
  • Authors:
    Mücke, Sascha; Gerlach, Thore; Piatkowski, Nico
  • Year:

Citation information

Mücke, Sascha; Gerlach, Thore; Piatkowski, Nico: Optimum-Preserving QUBO Parameter Compression, arXiv, 2023, https://arxiv.org/abs/2307.02195, Muecke.etal.2023b,

Associated Lamarr Researchers

lamarr institute person Mucke Sascha - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Sascha Mücke

Author to the profile
Thore Gerlach - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Thore Gerlach

Scientist to the profile
lamarr institute person Piatkowski Nico - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Dr. Nico Piatkowski

Autor to the profile