{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T13:25:04Z","timestamp":1773840304642,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T00:00:00Z","timestamp":1734393600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T00:00:00Z","timestamp":1734393600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["LAMARR24B"],"award-info":[{"award-number":["LAMARR24B"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Quadratic unconstrained binary optimization (<jats:sc>QUBO<\/jats:sc>) 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 <jats:sc>QUBO<\/jats:sc> problems under limited precision. Specifically, it is shown that the problem\u2019s dynamic range has a crucial impact on the problem\u2019s robustness against distortions. We show this by formalizing the notion of preserving optima between <jats:sc>QUBO<\/jats:sc> 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 <jats:sc>QUBO<\/jats:sc> instance based on the theoretical bounds of the minimal energy value. An experimental evaluation on random <jats:sc>QUBO<\/jats:sc> instances as well as <jats:sc>QUBO<\/jats:sc>-encoded <jats:sc>BinClustering<\/jats:sc> and <jats:sc>SubsetSum<\/jats:sc> 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.<\/jats:p>","DOI":"10.1007\/s42484-024-00219-3","type":"journal-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T07:43:01Z","timestamp":1734421381000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Optimum-preserving QUBO parameter compression"],"prefix":"10.1007","volume":"7","author":[{"given":"Sascha","family":"M\u00fccke","sequence":"first","affiliation":[]},{"given":"Thore","family":"Gerlach","sequence":"additional","affiliation":[]},{"given":"Nico","family":"Piatkowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,17]]},"reference":[{"key":"219_CR1","unstructured":"Altshuler B, Krovi H, Roland J (2009) Adiabatic quantum optimization fails for random instances of NP-complete problems. arXiv:0908.2782. [quant-ph]"},{"key":"219_CR2","unstructured":"Bauckhage C, Ojeda C, Sifa R et\u00a0al (2018) Adiabatic quantum computing for kernel k = 2 means clustering. In: LWDA, pp 21\u201332"},{"key":"219_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"Biamonte J, Wittek P, Pancotti N et al (2017) Quantum machine learning. Nature 549:195\u2013202","journal-title":"Nature"},{"key":"219_CR4","doi-asserted-by":"crossref","unstructured":"Biesner D, Gerlach T, Bauckhage C et\u00a0al (2022) Solving subset sum problems using quantum inspired optimization algorithms with applications in auditing and financial data analysis. In: 2022 21st IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, pp 903\u2013908","DOI":"10.1109\/ICMLA55696.2022.00150"},{"key":"219_CR5","unstructured":"Boros E, Hammer PL, Tavares G (2006) Preprocessing of unconstrained quadratic binary optimization. Tech rep, RRR 10-2006, RUTCOR"},{"issue":"2","key":"219_CR6","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1016\/j.disopt.2007.02.001","volume":"5","author":"E Boros","year":"2008","unstructured":"Boros E, Hammer PL, Sun R et al (2008) A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discret Optim 5(2):501\u2013529. https:\/\/doi.org\/10.1016\/j.disopt.2007.02.001","journal-title":"Discret Optim"},{"key":"219_CR7","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1103\/RevModPhys.39.883","volume":"39","author":"SG Brush","year":"1967","unstructured":"Brush SG (1967) History of the Lenz-Ising model. Reviews of modern physics 39:883","journal-title":"Reviews of modern physics"},{"key":"219_CR8","unstructured":"D-Wave\u00a0Systems (2023) Error sources for problem representation. https:\/\/docs.dwavesys.com\/docs\/latest\/c_qpu_ice.html"},{"key":"219_CR9","unstructured":"D-wave systems (2021) Technical description of the D-wave quantum processing unit"},{"key":"219_CR10","doi-asserted-by":"crossref","unstructured":"Date P, Arthur D, Pusey-Nazzaro L (2020) QUBO formulations for training machine learning models. arXiv:2008.02369. [physics, stat]","DOI":"10.1038\/s41598-021-89461-4"},{"issue":"130","key":"219_CR11","first-page":"501","volume":"117","author":"V Dunjko","year":"2016","unstructured":"Dunjko V, Taylor JM, Briegel HJ (2016) Quantum-enhanced machine learning. Phys Rev Lett 117(130):501","journal-title":"Phys Rev Lett"},{"key":"219_CR12","unstructured":"Farhi E, Goldstone J, Gutmann S, et\u00a0al (2000) Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106"},{"key":"219_CR13","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028"},{"key":"219_CR14","doi-asserted-by":"publisher","DOI":"10.1109\/CEC55065.2022.9870269","author":"L Franken","year":"2022","unstructured":"Franken L, Georgiev B, M\u00fccke S, Wolter M, Heese R, Bauckhage C, Piatkowski N (2022) Quantum circuit evolution on NISQ devices. IEEE Congress on Evolutionary Computation (CEC). https:\/\/doi.org\/10.1109\/CEC55065.2022.9870269","journal-title":"IEEE Congress on Evolutionary Computation (CEC)"},{"key":"219_CR15","volume-title":"Tabu search","author":"F Glover","year":"1998","unstructured":"Glover F, Laguna M (1998) Tabu search. Springer"},{"key":"219_CR16","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/j.ejor.2017.08.025","volume":"265","author":"F Glover","year":"2018","unstructured":"Glover F, Lewis M, Kochenberger G (2018) Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems. Eur J Oper Res 265:829\u2013842. https:\/\/doi.org\/10.1016\/j.ejor.2017.08.025","journal-title":"Eur J Oper Res"},{"issue":"2","key":"219_CR17","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1061\/(ASCE)0887-3801(1987)1:2(128)","volume":"1","author":"DE Goldberg","year":"1987","unstructured":"Goldberg DE, Kuo CH (1987) Genetic algorithms in pipeline optimization. J Comput Civ Eng 1(2):128\u2013141","journal-title":"J Comput Civ Eng"},{"key":"219_CR18","doi-asserted-by":"publisher","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/9605043. quant-ph\/9605043","DOI":"10.48550\/arXiv.quant-ph\/9605043"},{"issue":"3","key":"219_CR19","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/BF00139572","volume":"1","author":"PL Hammer","year":"1971","unstructured":"Hammer PL, Shlifer E (1971) Applications of pseudo-Boolean methods to economic problems. Theor Decis 1(3):296\u2013308","journal-title":"Theor Decis"},{"key":"219_CR20","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"PL Hammer","year":"1984","unstructured":"Hammer PL, Hansen P, Simeone B (1984) Roof duality, complementation and persistency in quadratic 0\u20131 optimization. Math Program 28:121\u2013155","journal-title":"Math Program"},{"key":"219_CR21","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58:5355","journal-title":"Phys Rev E"},{"issue":"4598","key":"219_CR22","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671\u2013680","journal-title":"Science"},{"issue":"1\u20132","key":"219_CR23","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1504\/IJOR.2005.007435","volume":"1","author":"G Kochenberger","year":"2005","unstructured":"Kochenberger G, Glover F, Alidaee B et al (2005) Using the unconstrained quadratic program to model and solve Max 2-SAT problems. Int J Oper Res 1(1\u20132):89\u2013100","journal-title":"Int J Oper Res"},{"key":"219_CR24","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger G, Hao JK, Glover F et al (2014) The unconstrained binary quadratic programming problem: a survey. J Comb Optim 28:58\u201381","journal-title":"J Comb Optim"},{"issue":"3","key":"219_CR25","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1287\/opre.18.3.454","volume":"18","author":"D Laughhunn","year":"1970","unstructured":"Laughhunn D (1970) Quadratic binary programming with application to capital-budgeting problems. Oper Res 18(3):454\u2013461","journal-title":"Oper Res"},{"issue":"2","key":"219_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.21751","volume":"70","author":"M Lewis","year":"2017","unstructured":"Lewis M, Glover F (2017) Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. Networks 70(2):79\u201397","journal-title":"Networks"},{"key":"219_CR27","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2013) Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411"},{"key":"219_CR28","doi-asserted-by":"crossref","unstructured":"Matsubara S, Tamura H, Takatsu M, et\u00a0al (2017) Ising-model optimizer with parallel-trial bit-sieve engine. In: Conference on Complex, Intelligent, and Software Intensive Systems. Springer, pp 432\u2013438","DOI":"10.1007\/978-3-319-61566-0_39"},{"key":"219_CR29","doi-asserted-by":"publisher","unstructured":"M\u00fccke S, Piatkowski N, Morik K (2019) Hardware acceleration of machine learning beyond linear algebra. In: Cellier P, Driessens K (eds) Workshops of the ECML-PKDD, Communications in Computer and Information Science, vol 1167. Springer, pp 342\u2013347. https:\/\/doi.org\/10.1007\/978-3-030-43823-4_29","DOI":"10.1007\/978-3-030-43823-4_29"},{"key":"219_CR30","unstructured":"M\u00fccke S, Piatkowski N, Morik K (2019) Learning bit by bit: extracting the essence of machine learning. In: Proceedings of the Conference on \"Lernen, Wissen, Daten, Analysen\" (LWDA), pp 144\u2013155"},{"key":"219_CR31","doi-asserted-by":"publisher","unstructured":"M\u00fccke S, Heese R, M\u00fcller S et al (2023) Feature selection on quantum computers. Quant Mach Intell 5. https:\/\/doi.org\/10.1007\/s42484-023-00099-z","DOI":"10.1007\/s42484-023-00099-z"},{"issue":"9","key":"219_CR32","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1109\/TC.1977.1674939","volume":"26","author":"PM Narendra","year":"1977","unstructured":"Narendra PM, Fukunaga K (1977) A branch and bound algorithm for feature subset selection. IEEE Trans Computers 26(9):917\u2013922. https:\/\/doi.org\/10.1109\/TC.1977.1674939","journal-title":"IEEE Trans Computers"},{"key":"219_CR33","doi-asserted-by":"crossref","unstructured":"Neukart F, Compostella G, Seidel C et\u00a0al (2017) Traffic flow optimization using a quantum annealer. Frontiers in ICT 4","DOI":"10.3389\/fict.2017.00029"},{"issue":"2","key":"219_CR34","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(92)90043-3","volume":"11","author":"PM Pardalos","year":"1992","unstructured":"Pardalos PM, Jha S (1992) Complexity of uniqueness and local search in quadratic 0\u20131 programming. Oper Res Lett 11(2):119\u2013123","journal-title":"Oper Res Lett"},{"key":"219_CR35","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo A, McClean J, Shadbolt P et al (2014) A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5:4213. https:\/\/doi.org\/10.1038\/ncomms5213","journal-title":"Nat Commun"},{"key":"219_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-023-00236-6","author":"D Rehfeldt","year":"2023","unstructured":"Rehfeldt D, Koch T, Shinano Y (2023) Faster exact solution of sparse MaxCut and QUBO problems. Math Prog Comput. https:\/\/doi.org\/10.1007\/s12532-023-00236-6","journal-title":"Math Prog Comput"},{"issue":"6195","key":"219_CR37","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1126\/science.1252319","volume":"345","author":"TF R\u00f8nnow","year":"2014","unstructured":"R\u00f8nnow TF, Wang Z, Job J et al (2014) Defining and detecting quantum speedup. Science 345(6195):420\u2013424. https:\/\/doi.org\/10.1126\/science.1252319","journal-title":"Science"},{"key":"219_CR38","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1080\/00107514.2014.964942","volume":"56","author":"M Schuld","year":"2015","unstructured":"Schuld M, Sinayskiy I, Petruccione F (2015) An introduction to quantum machine learning. Contemp Phys 56:172\u2013185","journal-title":"Contemp Phys"},{"key":"219_CR39","doi-asserted-by":"publisher","unstructured":"Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26:1484\u20131509. https:\/\/doi.org\/10.1137\/S0097539795293172. https:\/\/arxiv.org\/abs\/quant-ph\/9508027","DOI":"10.1137\/S0097539795293172"},{"key":"219_CR40","unstructured":"International Organization\u00a0for Standardization (2020) ISO\/IEC JTC 1\/SC 25 60559:2020 pp 1\u201374. https:\/\/www.iso.org\/standard\/80985.html"},{"key":"219_CR41","doi-asserted-by":"publisher","unstructured":"Stollenwerk T, Lobe E, Jung M (2019) Flight gate assignment with a quantum annealer. In: Quantum Technology and Optimization Problems. Springer International Publishing, Lecture Notes in Computer Science, pp 99\u2013110. https:\/\/doi.org\/10.1007\/978-3-030-14082-3_9","DOI":"10.1007\/978-3-030-14082-3_9"},{"key":"219_CR42","doi-asserted-by":"publisher","unstructured":"van Dam W, Mosca M, Vazirani U (2001) How powerful is adiabatic quantum computation? In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp 279\u2013287.https:\/\/doi.org\/10.1109\/SFCS.2001.959902","DOI":"10.1109\/SFCS.2001.959902"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00219-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00219-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00219-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T14:40:16Z","timestamp":1750948816000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00219-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,17]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["219"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00219-3","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,17]]},"assertion":[{"value":"5 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"1"}}