Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions

Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions Mauro Mezzini, Fernando Cuartero Gomez, Jose Javier Paulet Gonzalez, and 3 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3960721/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 28 Oct, 2024 Read the published version in Quantum Machine Intelligence → Version 1 posted 10 You are reading this latest preprint version Abstract In this paper, we present quantum computing algorithms for solving the dualization problem in polynomial time with respect to the asymptotic dimensions of the positive irredundant Disjunctive Normal Form. Furthermore, we give a quantum annealing algorithm for solving the dualization problem using a quantum annealer. Moreover, we reduce the dualization problem to the problem of counting all the hitting sets of a hypergraph Dualization problem Quantum Computing Computational complexity Hypergraph algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 28 Oct, 2024 Read the published version in Quantum Machine Intelligence → Version 1 posted Editorial decision: Revision requested 09 Sep, 2024 Reviews received at journal 04 Sep, 2024 Reviewers agreed at journal 26 Aug, 2024 Reviewers agreed at journal 12 Apr, 2024 Reviews received at journal 06 Apr, 2024 Reviewers agreed at journal 01 Mar, 2024 Reviewers invited by journal 28 Feb, 2024 Editor assigned by journal 18 Feb, 2024 Submission checks completed at journal 18 Feb, 2024 First submitted to journal 16 Feb, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3960721","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":273585396,"identity":"9a370a42-bdca-4231-9d7a-122cc2811827","order_by":0,"name":"Mauro Mezzini","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA90lEQVRIiWNgGAWjYHADxgaGhAoGBjYw5wcDD5FazkC1MPYw8BCjB6iyDcYCasSlRbf9jNmHDwzb5OT7D7c9eDjvcB6f9OGjG37wMMjY49BidibHeOYMhtvGjA0H2w0Stx0uZuNLS7vZY4HbYWYHcoyZeRhuJzYzNrZJALUktvHwmN0Aqset5fwbsJb6NmZGoJY5EC03/7Dh0XIDYksCDxtISwNEy20evFqeFTPOMLhtOIMHqCXhWDpQC1vabdkeCR6eA7gclryZ4UPFbXn5/uPPJH/UWCfO72E+dvPNDxt79gYc1oCBAaaQBD71o2AUjIJRMAoIAADCclFZ/FTWpgAAAABJRU5ErkJggg==","orcid":"","institution":"Roma Tre University","correspondingAuthor":true,"prefix":"","firstName":"Mauro","middleName":"","lastName":"Mezzini","suffix":""},{"id":273585397,"identity":"6b086d17-dc1e-40e0-a160-aeb0527337b3","order_by":1,"name":"Fernando Cuartero Gomez","email":"","orcid":"","institution":"University of Castilla-La Mancha","correspondingAuthor":false,"prefix":"","firstName":"Fernando","middleName":"Cuartero","lastName":"Gomez","suffix":""},{"id":273585398,"identity":"95be2eff-6257-4918-a402-9c9f20142ba5","order_by":2,"name":"Jose Javier Paulet Gonzalez","email":"","orcid":"","institution":"Qsimov Quantum Computing S.L","correspondingAuthor":false,"prefix":"","firstName":"Jose","middleName":"Javier Paulet","lastName":"Gonzalez","suffix":""},{"id":273585399,"identity":"9b606219-aecc-4685-b4f9-1d3d5905d533","order_by":3,"name":"Hernan Indibil de la Cruz Calvo","email":"","orcid":"","institution":"University of Castilla-La Mancha","correspondingAuthor":false,"prefix":"","firstName":"Hernan","middleName":"Indibil de la Cruz","lastName":"Calvo","suffix":""},{"id":273585400,"identity":"acd3272b-0fc0-49f3-a266-585c37e22ac4","order_by":4,"name":"Vicente Pascual","email":"","orcid":"","institution":"","correspondingAuthor":false,"prefix":"","firstName":"Vicente","middleName":"","lastName":"Pascual","suffix":""},{"id":273585401,"identity":"c1e98370-67db-42e8-9308-e60ab89fba96","order_by":5,"name":"Fernando L. Pelayo","email":"","orcid":"","institution":"University of Castilla-La Mancha","correspondingAuthor":false,"prefix":"","firstName":"Fernando","middleName":"L.","lastName":"Pelayo","suffix":""}],"badges":[],"createdAt":"2024-02-16 08:31:27","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3960721/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3960721/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s42484-024-00202-y","type":"published","date":"2024-10-28T16:20:10+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":68207054,"identity":"0c9e3635-8ab0-40fc-ab5b-2d292dc3cbc4","added_by":"auto","created_at":"2024-11-04 16:34:27","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":446075,"visible":true,"origin":"","legend":"","description":"","filename":"dual.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3960721/v1_covered_e217e24a-6d10-492d-afe0-4186e774569a.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"quantum-machine-intelligence","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"qumi","sideBox":"Learn more about [Quantum Machine Intelligence](http://link.springer.com/journal/42484)","snPcode":"42484","submissionUrl":"https://submission.nature.com/new-submission/42484/3","title":"Quantum Machine Intelligence","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Dualization problem, Quantum Computing, Computational complexity, Hypergraph algorithm","lastPublishedDoi":"10.21203/rs.3.rs-3960721/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3960721/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"In this paper, we present quantum computing algorithms for solving the dualization problem in polynomial time with respect to the asymptotic dimensions of the positive irredundant Disjunctive Normal Form. Furthermore, we give a quantum annealing algorithm for solving the dualization problem using a quantum annealer. Moreover, we reduce the dualization problem to the problem of counting all the hitting sets of a hypergraph","manuscriptTitle":"Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-02-20 04:39:15","doi":"10.21203/rs.3.rs-3960721/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-09-09T09:01:40+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-09-04T09:48:55+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"165232265357543900603350772393735512472","date":"2024-08-26T13:19:13+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"942a2c17-ff81-4382-8ec8-37a881623992","date":"2024-04-12T23:30:58+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-04-06T05:47:34+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"022fff8d-36a0-4164-a1e0-5d1c8bd526ed","date":"2024-03-01T19:54:20+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-02-28T09:57:02+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-02-19T02:52:58+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-02-18T22:16:22+00:00","index":"","fulltext":""},{"type":"submitted","content":"Quantum Machine Intelligence","date":"2024-02-16T08:14:37+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"quantum-machine-intelligence","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"qumi","sideBox":"Learn more about [Quantum Machine Intelligence](http://link.springer.com/journal/42484)","snPcode":"42484","submissionUrl":"https://submission.nature.com/new-submission/42484/3","title":"Quantum Machine Intelligence","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"6b9af6f3-5774-42b4-b2b0-a0a1e7da9e3e","owner":[],"postedDate":"February 20th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-11-04T16:25:54+00:00","versionOfRecord":{"articleIdentity":"rs-3960721","link":"https://doi.org/10.1007/s42484-024-00202-y","journal":{"identity":"quantum-machine-intelligence","isVorOnly":false,"title":"Quantum Machine Intelligence"},"publishedOn":"2024-10-28 16:20:10","publishedOnDateReadable":"October 28th, 2024"},"versionCreatedAt":"2024-02-20 04:39:15","video":"","vorDoi":"10.1007/s42484-024-00202-y","vorDoiUrl":"https://doi.org/10.1007/s42484-024-00202-y","workflowStages":[]},"version":"v1","identity":"rs-3960721","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3960721","identity":"rs-3960721","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}