Quantum algorithm for finding minimum values in a Quantum Random Access Memory

Quantum algorithm for finding minimum values in a Quantum Random Access Memory | 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 Quantum algorithm for finding minimum values in a Quantum Random Access Memory Anton S. Albino, Lucas Q. Galvão, Mauro Q. Nooblath Neto, Ethan Hansen, and 1 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4687790/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and performs an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Quantum RAM Minimum search Grover’s Algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-4687790","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":332742295,"identity":"d24de7b8-88ed-49b3-afc7-bd0c02644159","order_by":0,"name":"Anton S. Albino","email":"","orcid":"","institution":"Latin American Quantum Computing Center, SENAI CIMATEC","correspondingAuthor":false,"prefix":"","firstName":"Anton","middleName":"S.","lastName":"Albino","suffix":""},{"id":332742297,"identity":"99d693dd-2cc9-46c5-9800-c83fa006f72d","order_by":1,"name":"Lucas Q. Galvão","email":"","orcid":"","institution":"Federal University of Western Bahia","correspondingAuthor":false,"prefix":"","firstName":"Lucas","middleName":"Q.","lastName":"Galvão","suffix":""},{"id":332742299,"identity":"642953c2-3027-4284-bd65-755b8c37856a","order_by":2,"name":"Mauro Q. Nooblath Neto","email":"","orcid":"","institution":"Latin American Quantum Computing Center, SENAI CIMATEC","correspondingAuthor":false,"prefix":"","firstName":"Mauro","middleName":"Q. Nooblath","lastName":"Neto","suffix":""},{"id":332742302,"identity":"03a5b9a5-547f-4124-a12f-2f7ec089c0f2","order_by":3,"name":"Ethan Hansen","email":"","orcid":"","institution":"Zapata (United States)","correspondingAuthor":false,"prefix":"","firstName":"Ethan","middleName":"","lastName":"Hansen","suffix":""},{"id":332742303,"identity":"5028a4ae-c4bb-41a9-8fbc-2a2a33168c96","order_by":4,"name":"Clebson Cruz","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA9klEQVRIiWNgGAWjYDACdgY2BOcDgxyDAZCWYGA4gFsLM5IWxhkMxiRqYeYhRgt/M/Oxhz8q7jDwzz5j/Nm2zUDOnIH54G0ehjv5uLRIHGZLN+Y584xB4lyOgXFum4GxZQNbsjUPwzPLBhxaDJh5zKQZ2w4zGPDwGCTntv1J3HAAKMLDcNgAly0GzPzfJH9CtRy2bDMAauH/RkALD5sEL0SLYTMjWAsPG14tQL+YA/1ymEfiDFsxY885oF+a2Ywt5xg8w6mFv735GTDEDsvx9zBv/vCjDBhi7M0Pb7ypuINTCwzwIJjMYAcT0jAKRsEoGAWjAB8AAIbJSVeqdLKCAAAAAElFTkSuQmCC","orcid":"","institution":"Federal University of Western Bahia","correspondingAuthor":true,"prefix":"","firstName":"Clebson","middleName":"","lastName":"Cruz","suffix":""}],"badges":[],"createdAt":"2024-07-04 16:23:47","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4687790/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4687790/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":65276209,"identity":"fef1d30e-51a1-468c-a9e7-80966f1972d5","added_by":"auto","created_at":"2024-09-25 14:02:08","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":395682,"visible":true,"origin":"","legend":"","description":"","filename":"QRAMQIP.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4687790/v1_covered_15fe1500-b4c2-4a3c-88a7-0a0c2293721d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Quantum algorithm for finding minimum values in a Quantum Random Access Memory","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Quantum RAM, Minimum search, Grover’s Algorithm","lastPublishedDoi":"10.21203/rs.3.rs-4687790/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4687790/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and performs an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts.","manuscriptTitle":"Quantum algorithm for finding minimum values in a Quantum Random Access Memory","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-30 01:38:10","doi":"10.21203/rs.3.rs-4687790/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"5bc1b7e7-b61a-4671-a44c-03f74c2fc421","owner":[],"postedDate":"July 30th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-09-25T13:53:53+00:00","versionOfRecord":[],"versionCreatedAt":"2024-07-30 01:38:10","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4687790","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4687790","identity":"rs-4687790","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}