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-$\perp$ values trace a hidden simple path $s \to a_1 \to a_2 \to \cdots \to a_\ell \to \perp$, 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 \ge \ell \ge 1$ have quantum query complexity $Θ\!\bigl(\min\{\ell,(N\ell)^{1/4}\}\bigr)$. Thus, quite surprisingly, when $N < \ell^3$ the optimal quantum complexity is $(N\ell)^{1/4}$, which is strictly smaller than the $Θ(\ell)$ 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.
AI Summary
The paper studies quantum search on a linked list whose vertices occupy unknown addresses in an ambient universe $[N]$. The input provides coherent successor and marking oracles, a public start symbol, and a promised simple path of known length $\ell$. At most one list vertex is marked, and off-list addresses are unmarked and have null successors. The question is whether global access to addresses can improve on following pointers sequentially.
For all $N\ge\ell\ge1$, both deciding whether a mark exists and finding it have bounded-error quantum query complexity $\Theta(\min\{\ell,(N\ell)^{1/4}\})$. The same bound holds with predecessor access for doubly linked lists. Classical deterministic and randomized query complexities remain $\Theta(\ell)$. The quantum bound improves on the elementary combination of traversal and Grover search, $O(\min\{\ell,\sqrt N\})$, with traversal becoming optimal at $N\gtrsim\ell^3$.
The upper bound combines amplitude amplification to prepare a uniform superposition over recognizable list vertices with amplified search for starting points whose short pointer walks encounter the mark. The lower bound constructs explicit nonnegative adversary matrices for layered segments at the cubic address-space scale, then serially packs segments and applies adversary composition with unique-OR. Doubly linked lists require an unmarked buffer and oppositely oriented weights to control predecessor queries.
The characterization concerns oracle query complexity under these promises. A list-tag variant permits arbitrary off-list pointers; extensions to other hidden pointer-based structures are left as future directions.
Little sign of AI-generated text
Error found: The abstract incorrectly describes all N < ℓ³ as yielding an asymptotic speedup over linear traversal; its tight complexity formula yields sublinear complexity only when N = o(ℓ³).
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies quantum search on a linked list whose vertices occupy unknown addresses in an ambient universe [N]. The input provides coherent successor and marking oracles, a public start symbol, and a promised simple path of known length ℓ. At most one list vertex is marked, and off-list addresses are unmarked and have null successors. The question is whether global access to addresses can improve on following pointers sequentially.
For all N≥ℓ≥1, both deciding whether a mark exists and finding it have bounded-error quantum query complexity Θ(min{ℓ,(Nℓ)1/4}). The same bound holds with predecessor access for doubly linked lists. Classical deterministic and randomized query complexities remain Θ(ℓ). The quantum bound improves on the elementary combination of traversal and Grover search, O(min{ℓ,N}), with traversal becoming optimal at N≳ℓ3.
The upper bound combines amplitude amplification to prepare a uniform superposition over recognizable list vertices with amplified search for starting points whose short pointer walks encounter the mark. The lower bound constructs explicit nonnegative adversary matrices for layered segments at the cubic address-space scale, then serially packs segments and applies adversary composition with unique-OR. Doubly linked lists require an unmarked buffer and oppositely oriented weights to control predecessor queries.
The characterization concerns oracle query complexity under these promises. A list-tag variant permits arbitrary off-list pointers; extensions to other hidden pointer-based structures are left as future directions.
We consider the quantum complexities of searching an ordered list and sorting an un-ordered list. For searching an ordered list of N elements, we prove a lower bound of \\frac{1}{\\pi}(\\ln(N)-1) on the number of oracle queries that access the list elements. This improves the previously best lower bound of ({1/12}\\log_2(N) - O(1)) due to Ambainis. For sorting N numbers, we prove a lower bound of \\frac{N}{2\\pi}(\\ln(N)-1) on the number of binary comparisons. The previously best lower bound is \\Omega(N). Our proofs are based on a weighted all-pairs inner product argument, and our results generalize to bounded error quantum algorithms. Both results are proven in the so-called quantum black box model, a quantum analogue of classical decision trees. In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using (\\log_3(N) + O(1)) queries, which is roughly 0.631 \\log_2(N). Although our algorithm is worse than that of Farhi, Goldstone, Gutmann and Sipser, which makes 0.526 \\log_2(N) queries, its philosophy is completely different. Our algorithm is a quantum version of the classical binary search algorithm, and it uses a quantum routine for traversing through a binary search tree faster than classically.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.