{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:25:48Z","timestamp":1757618748962,"version":"3.44.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T00:00:00Z","timestamp":1752192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T00:00:00Z","timestamp":1752192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008902","name":"Los Alamos National Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008902","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.\n<\/jats:p>","DOI":"10.1007\/s11128-025-04839-x","type":"journal-article","created":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T14:11:27Z","timestamp":1752243087000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Toward computing bounds for Ramsey numbers using quantum annealing"],"prefix":"10.1007","volume":"24","author":[{"given":"Joel E.","family":"Pion","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susan M.","family":"Mniszewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,11]]},"reference":[{"key":"4839_CR1","doi-asserted-by":"publisher","unstructured":"Ushijima-Mwesigwa, H., Negre, C.F.A., Mniszewski, S.M.: Graph partitioning using quantum annealing on the D-Wave system. In: Proceedings of Second International Workshop on Post Moore\u2019s Era Supercomputing, pp. 1\u20138 (2017). https:\/\/doi.org\/10.1145\/3149526.3149531","DOI":"10.1145\/3149526.3149531"},{"issue":"2","key":"4839_CR2","doi-asserted-by":"publisher","first-page":"0227538","DOI":"10.1371\/journal.pone.0227538","volume":"15","author":"CFA Negre","year":"2020","unstructured":"Negre, C.F.A., Ushijima-Mwesigwa, H., Mniszewski, S.M.: Detecting multiple communities using quantum annealing on the D-Wave system. PloS ONE 15(2), 0227538 (2020). https:\/\/doi.org\/10.1371\/journal.pone.0227538","journal-title":"PloS ONE"},{"issue":"7","key":"4839_CR3","doi-asserted-by":"publisher","first-page":"0271292","DOI":"10.1371\/journal.pone.0271292","volume":"17","author":"PD Akrobotu","year":"2022","unstructured":"Akrobotu, P.D., James, T.E., Negre, C.F.A., Mniszewski, S.M.: A QUBO formulation for top-$$\\tau $$ eigencentrality nodes. PloS ONE 17(7), 0271292 (2022). https:\/\/doi.org\/10.1371\/journal.pone.0271292","journal-title":"PloS ONE"},{"key":"4839_CR4","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2208.08397","author":"JE Pion","year":"2023","unstructured":"Pion, J.E., Negre, C.F.A., Mniszewski, S.M.: Quantum computing for a profusion of postman problem variants. Quantum Mach. Intell. (2023). https:\/\/doi.org\/10.48550\/arXiv.2208.08397","journal-title":"Quantum Mach. Intell."},{"issue":"3","key":"4839_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90025-8","volume":"9","author":"FS Roberts","year":"1984","unstructured":"Roberts, F.S.: Applications of Ramsey theory. Discret. Appl. Math. 9(3), 251\u2013261 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"11","key":"4839_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113336","volume":"346","author":"W Gasarch","year":"2023","unstructured":"Gasarch, W.: Fermat\u2019s last theorem, Schur\u2019s theorem (in Ramsey theory), and the infinitude of the primes. Discret. Math. 346(11), 113336 (2023). https:\/\/doi.org\/10.1016\/j.disc.2023.113336","journal-title":"Discret. Math."},{"key":"4839_CR7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.130505","volume":"111","author":"Z Bian","year":"2013","unstructured":"Bian, Z., Chudak, F., Macready, W.G., Clark, L., Gaitan, F.: Experimental determination of ramsey numbers. Phys. Rev. Lett. 111, 130505 (2013). https:\/\/doi.org\/10.1103\/PhysRevLett.111.130505","journal-title":"Phys. Rev. Lett."},{"key":"4839_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.108.010501","author":"F Gaitan","year":"2012","unstructured":"Gaitan, F., Clark, L.: Ramsey numbers and adiabatic quantum computing. Phys. Rev. Lett. (2012). https:\/\/doi.org\/10.1103\/physrevlett.108.010501","journal-title":"Phys. Rev. Lett."},{"key":"4839_CR9","doi-asserted-by":"publisher","DOI":"10.1002\/net.21751","author":"M Lewis","year":"2017","unstructured":"Lewis, M., Glover, F.: Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. Networks (2017). https:\/\/doi.org\/10.1002\/net.21751","journal-title":"Networks"},{"key":"4839_CR10","unstructured":"McGeoch, C, Farr\u00e9, P: The Advantage system: Performance update. D-Wave Technical Report Series (2021)"},{"key":"4839_CR11","unstructured":"D-Wave: Hybrid solvers. Documentation (2023). https:\/\/docs.ocean.dwavesys.com\/en\/stable\/overview\/hybrid.html"},{"key":"4839_CR12","unstructured":"D-Wave: D-Wave hybrid solver service: An overview. D-Wave Whitepaper Series (2020)"},{"key":"4839_CR13","unstructured":"D-Wave: Hybrid solvers for quadratic optimization. D-Wave Whitepaper Series (2022)"},{"key":"4839_CR14","unstructured":"D-Wave: minorminer. Documentation (2023). https:\/\/docs.ocean.dwavesys.com\/en\/stable\/docs_minorminer\/source\/sdk_index.html"},{"key":"4839_CR15","doi-asserted-by":"publisher","unstructured":"Avradip\u00a0Mandal, S.U. Arnab\u00a0Roy, Ushijima-Mwesigwa, H.: Compressed quadratization of higher order binary optimization problems. arXiv (2020). https:\/\/doi.org\/10.48550\/arXiv.2001.00658","DOI":"10.48550\/arXiv.2001.00658"},{"key":"4839_CR16","unstructured":"Ahmed, S.: Applications of graph coloring in modern computer science. Int. J. Comput. Inf. Technol. 03 (2012)"},{"key":"4839_CR17","unstructured":"Garey, M.: Computers and intractability : a guide to the theory of NP-completeness. Kahle\/Austin Foundation (1979)"},{"key":"4839_CR18","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264","author":"F Ramsey","year":"1930","unstructured":"Ramsey, F.: On a problem of formal logic. Proc. Lond. Math. Soc. (1930). https:\/\/doi.org\/10.1112\/plms\/s2-30.1.264","journal-title":"Proc. Lond. Math. Soc."},{"key":"4839_CR19","unstructured":"Perry, M.: simanneal. GitHub repository (2020). https:\/\/github.com\/perrygeo\/simanneal"},{"key":"4839_CR20","unstructured":"OEIS: Multiplicity of $$K_3$$ in $$K_n$$ a014557. OEIS Foundation Inc (2023). https:\/\/oeis.org\/A014557"},{"key":"4839_CR21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.130505","author":"Z Bian","year":"2013","unstructured":"Bian, Z., Chudak, F., Macready, W.G., Clark, L., Gaitan, F.: Experimental determination of Ramsey numbers. Phys. Rev. Lett. (2013). https:\/\/doi.org\/10.1103\/PhysRevLett.111.130505","journal-title":"Phys. Rev. Lett."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-025-04839-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-025-04839-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-025-04839-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T05:42:56Z","timestamp":1757223776000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-025-04839-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,11]]},"references-count":21,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,7]]}},"alternative-id":["4839"],"URL":"https:\/\/doi.org\/10.1007\/s11128-025-04839-x","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2025,7,11]]},"assertion":[{"value":"7 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"221"}}