2000/06/30 by Mark Heiligman, Heiligman, Mark
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0006136
arxiv created 2000/06/30 · arxiv updated 2009/12/01
Given 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(N3/4log N) (measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is O(N1/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.