Quantum Query Complexity for List Search
This paper gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search, and extends the results and gives the same tight asymptotic bounds for the natural double linked-list version as well.