{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:36:48Z","timestamp":1772120208388,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s42484-024-00202-y","type":"journal-article","created":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T06:06:14Z","timestamp":1730095574000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions"],"prefix":"10.1007","volume":"6","author":[{"given":"Mauro","family":"Mezzini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"Cuartero Gomez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose Javier Paulet","family":"Gonzalez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hernan Indibil","family":"de la Cruz Calvo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vicente","family":"Pascual","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"L. Pelayo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,28]]},"reference":[{"issue":"1\u20132","key":"202_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10107-016-1032-4","volume":"162","author":"M Anthony","year":"2017","unstructured":"Anthony M, Boros E, Crama Y, Gruber A (2017) Quadratic reformulations of nonlinear binary optimization problems. Math Program 162(1\u20132):115\u2013144. https:\/\/doi.org\/10.1007\/s10107-016-1032-4","journal-title":"Math Program"},{"key":"202_CR2","doi-asserted-by":"publisher","unstructured":"Boixo S, R\u00f8nnow TF, Isakov S, Wang Z, Wecker D, Lidar D, Martinis J, Troyer M (2013) Quantum annealing with more than one hundred qubits. Nat Phys 10. https:\/\/doi.org\/10.1038\/nphys2900","DOI":"10.1038\/nphys2900"},{"issue":"6","key":"202_CR3","doi-asserted-by":"publisher","first-page":"2036","DOI":"10.1137\/S0097539700370072","volume":"30","author":"E Boros","year":"2001","unstructured":"Boros E, Gurvich V, Khachiyan L, Makino K (2001) Dual-bounded generating problems: partial and multiple transversals of a hypergraph. SIAM J Comput 30(6):2036\u20132050. https:\/\/doi.org\/10.1137\/S0097539700370072","journal-title":"SIAM J Comput"},{"key":"202_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/3-540-45841-7_10","volume-title":"STACS 2002","author":"E Boros","year":"2002","unstructured":"Boros E, Gurvich V, Khachiyan L, Makino K (2002) On the complexity of generating maximal frequent and minimal infrequent sets. In: Alt H, Ferreira A (eds) STACS 2002. Springer, Berlin, Heidelberg, pp 133\u2013141"},{"key":"202_CR5","doi-asserted-by":"crossref","unstructured":"Crama Y, Hammer PL (2011) Boolean functions - theory, algorithms, and applications. Encyclopedia of mathematics and its applications, Cambridge University Press, Cambridge, England, vol 142. http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item6222210\/?site_locale=en_GB","DOI":"10.1017\/CBO9780511852008"},{"key":"202_CR6","doi-asserted-by":"crossref","unstructured":"Deutsch D, Jozsa R (1992) Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553\u2013558","DOI":"10.1098\/rspa.1992.0167"},{"issue":"1","key":"202_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/A:1007627028578","volume":"37","author":"C Domingo","year":"1999","unstructured":"Domingo C, Mishra N, Pitt L (1999) Efficient read-restricted monotone CNF\/DNF dualization by learning with membership queries. Mach Learn 37(1):89\u2013110. https:\/\/doi.org\/10.1023\/A:1007627028578","journal-title":"Mach Learn"},{"issue":"6","key":"202_CR8","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T Eiter","year":"1995","unstructured":"Eiter T, Gottlob G (1995) Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput 24(6):1278\u20131304. https:\/\/doi.org\/10.1137\/S0097539793250299","journal-title":"SIAM J Comput"},{"issue":"2","key":"202_CR9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/S009753970240639X","volume":"32","author":"T Eiter","year":"2003","unstructured":"Eiter T, Gottlob G, Makino K (2003) New results on monotone dualization and generating hypergraph transversals. SIAM J Comput 32(2):514\u2013537. https:\/\/doi.org\/10.1137\/S009753970240639X","journal-title":"SIAM J Comput"},{"issue":"11","key":"202_CR10","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T Eiter","year":"2008","unstructured":"Eiter T, Makino K, Gottlob G (2008) Computational aspects of monotone dualization: a brief survey. Discrete Appl Math 156(11):2035\u20132049. https:\/\/doi.org\/10.1016\/j.dam.2007.04.017","journal-title":"Discrete Appl Math"},{"key":"202_CR11","doi-asserted-by":"publisher","unstructured":"Fix A, Gruber A, Boros E, Zabih R (2011) A graph cut algorithm for higher-order Markov random fields, pp 1020\u20131027. https:\/\/doi.org\/10.1109\/ICCV.2011.6126347. Cited by: 65; All Open Access, Green Open Access. https:\/\/www.scopus.com\/inward\/record.uri?eid=2-s2.0-84856631976&doi=10.1109%2fICCV.2011.6126347 &partnerID=40 &md5=34134f2f47480b628ee5e0daf2568de1","DOI":"10.1109\/ICCV.2011.6126347"},{"issue":"3","key":"202_CR12","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"ML Fredman","year":"1996","unstructured":"Fredman ML, Khachiyan L (1996) On the complexity of dualization of monotone disjunctive normal forms. J Algorithms 21(3):618\u2013628","journal-title":"J Algorithms"},{"key":"202_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1613\/jair.380","volume":"8","author":"G Gogic","year":"1998","unstructured":"Gogic G, Papadimitriou C, Sideri M (1998) Incremental recompilation of knowledge. J Artif Intell Res 8:23\u201337","journal-title":"J Artif Intell Res"},{"issue":"2","key":"202_CR14","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/15M1027267","volume":"47","author":"G Gottlob","year":"2018","unstructured":"Gottlob G, Malizia E (2018) Achieving new upper bounds for the hypergraph duality problem through logic. SIAM J Comput 47(2):456\u2013492. https:\/\/doi.org\/10.1137\/15M1027267","journal-title":"SIAM J Comput"},{"key":"202_CR15","doi-asserted-by":"publisher","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing. STOC \u201996, pp 212\u2013219. Association for Computing Machinery, New York, USA. https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"key":"202_CR16","doi-asserted-by":"crossref","unstructured":"Gunopulos D, Khardon R, Mannila H, Toivonen H (1997) Data mining, hypergraph transversals, and machine learning. In: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database and knowledgebase systems (PODS\u201997), ACM, United States, pp 209\u2013216","DOI":"10.1145\/263661.263684"},{"issue":"1","key":"202_CR17","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0166-218X(99)00099-2","volume":"96\u201397","author":"V Gurvich","year":"1999","unstructured":"Gurvich V, Khachiyan L (1999) On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions. Discrete Appl Math 96\u201397(1):363\u2013373. https:\/\/doi.org\/10.1016\/S0166-218X(99)00099-2","journal-title":"Discrete Appl Math"},{"issue":"6231","key":"202_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1126\/science.aaa4170","volume":"348","author":"B Heim","year":"2015","unstructured":"Heim B, R\u00f8nnow TF, Isakov SV, Troyer M (2015) Quantum versus classical annealing of Ising spin glasses. Science 348(6231):215\u2013217. https:\/\/doi.org\/10.1126\/science.aaa4170","journal-title":"Science"},{"issue":"6","key":"202_CR19","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","volume":"33","author":"H Ishikawa","year":"2011","unstructured":"Ishikawa H (2011) Transformation of general binary MRF minimization to the first-order case. IEEE Trans Pattern Anal Mach Intell 33(6):1234\u20131249. https:\/\/doi.org\/10.1109\/TPAMI.2010.91","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"202_CR20","doi-asserted-by":"publisher","unstructured":"Johnson MW, Amin MHS, Gildert S, Lanting T, Hamze F, Dickson N, Harris R, Berkley AJ, Johansson J, Bunyk P, Chapple EM, Enderud C, Hilton JP, Karimi K, Ladizinsky E, Ladizinsky N, Oh T, Perminov I, Rich C, Thom MC, Tolkacheva E, Truncik CJS, Uchaikin S, Wang J, Wilson B, Rose G (2011) Quantum annealing with manufactured spins. Nature 473(7346):194\u2013198. https:\/\/doi.org\/10.1038\/nature10012","DOI":"10.1038\/nature10012"},{"key":"202_CR21","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1613\/jair.183","volume":"3","author":"R Khardon","year":"1995","unstructured":"Khardon R (1995) Translating between horn representations and their characteristic models. J Artif Intell Res 3:349\u2013372","journal-title":"J Artif Intell Res"},{"key":"202_CR22","unstructured":"Mezzini M, Gomez FC, Lopez Pelayo F, Paulet Gonzalez JJ, Cruz Calvo HI, Pascual V (2023) A polynomial quantum computing algorithm for solving the dualization problem for positive Boolean functions, vol 3586, pp 1\u20138. https:\/\/www.scopus.com\/inward\/record.uri?eid=2-s2.0-85180761653&partnerID=40 &md5=8e64e85c297ff032d3530bb3c1ccc27e"},{"key":"202_CR23","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2000","unstructured":"Nielsen MA, Chuang IL (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge, England"},{"key":"202_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R Reiter","year":"1987","unstructured":"Reiter R (1987) A theory of diagnosis from first principles. Artif Intell 32:57\u201395","journal-title":"Artif Intell"},{"key":"202_CR25","first-page":"71","volume":"17","author":"IG Rosenberg","year":"1975","unstructured":"Rosenberg IG (1975) Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d\u2019Etudes de Recherche Op\u00e9rationnelle 17:71\u201374","journal-title":"Cahiers du Centre d\u2019Etudes de Recherche Op\u00e9rationnelle"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00202-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00202-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00202-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T11:11:31Z","timestamp":1734952291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00202-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,28]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["202"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00202-y","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3960721\/v1","asserted-by":"object"}]},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,28]]},"assertion":[{"value":"16 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 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":"Competing Interests"}}],"article-number":"71"}}