Quantum Query Complexity for List Search
Abstract
Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an address universe [N], a public start symbol s, a successor oracle f whose non-⊥ values trace a hidden simple path s → a1 → a2 → ⋯ → aℓ → ⊥, and a marking oracle g that marks at most one list vertex. The task is to decide whether the list contains a marked vertex. We prove that both the decision and search versions of this problem for all N ≥ ℓ ≥ 1 have quantum query complexity Θ (min{ℓ,(Nℓ)1/4}). Thus, quite surprisingly, when N < ℓ3 the optimal quantum complexity is (Nℓ)1/4, which is strictly smaller than the Θ(ℓ) cost of ordinary linked-list traversal. This gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search. We extend our results and give the same tight asymptotic bounds for the natural double linked-list version as well.
Related
- Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
BibTeX
@misc{banerjee2026quantum,
title = {{Quantum Query Complexity for List Search}},
author = {Niranka Banerjee and Akinori Kawachi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38736},
eprint = {2609.38736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38736},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Query Complexity for List Search
AU - Niranka Banerjee
AU - Akinori Kawachi
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38736
UR - https://arxiv.org/abs/2609.38736
AB - Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an address universe [N], a public start symbol s, a successor oracle f whose non-⊥ values trace a hidden simple path s → a_1 → a_2 → ⋯ → a_ℓ → ⊥, and a marking oracle g that marks at most one list vertex. The task is to decide whether the list contains a marked vertex. We prove that both the decision and search versions of this problem for all N ≥ ℓ ≥ 1 have quantum query complexity Θ (min{ℓ,(Nℓ)^1/4}). Thus, quite surprisingly, when N < ℓ^3 the optimal quantum complexity is (Nℓ)^1/4, which is strictly smaller than the Θ(ℓ) cost of ordinary linked-list traversal. This gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search. We extend our results and give the same tight asymptotic bounds for the natural double linked-list version as well.
ER -