Finding Matches between Two Databases on a Quantum Computer

Simple item page
dc.creatorHeiligman, Mark
dc.date2000-06-30
dc.date.accessioned2026-07-07T06:00:20Z
dc.date.available2026-07-07T06:00:20Z
dc.descriptionGiven two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of $O(N^{3/4}\log N)$ (measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is $O(N^{1/2})$. The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.
dc.identifierhttps://arxiv.org/abs/quant-ph/0006136
dc.identifierhttp://arxiv.org/abs/quant-ph/0006136
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/88953
dc.subjectQuantum Physics
dc.titleFinding Matches between Two Databases on a Quantum Computer
dc.typetext

Files

Collections

arXiv