Quantum Query Complexity for List Search

1 Introduction

• Classically, the ambient universe is asymptotically irrelevant and complexity remains Θ(ℓ), while naive quantum search improves on traversal when N < ℓ^2.Traversal costs O(ℓ), whereas Grover search over [N] gives an alternative upper bound; the stated improvement follows from the comparison in the passage.Source: §1 · pp. 1, 3, 4
• The decision problem gives oracle access to a hidden simple path from public start symbol s and asks whether any list vertex is marked.The successor oracle traces pairwise distinct list vertices, and the marking function is zero off the list.Source: §1 · p. 2
• For N ≲ ℓ^3, quantum query complexity is Θ((Nℓ)^1/4); for N ≳ ℓ^3, it is Θ(ℓ), with upper and lower bounds establishing the threshold.The upper bound combines global search over addresses with local list exploration; the lower bound uses adversary constructions.Source: §1 · pp. 4, 6, 7
• The hidden-list model lies between unstructured search and explicit structured search: the path is structured but hidden inside [N], so algorithms must discover support and exploit its successor structure.The introduction contrasts this setting with ordered search, where quantum algorithms provide only constant-factor improvements over classical binary search.Source: §1 · pp. 4–5
• The single-list upper bound amplifies a superposition over the ℓ−1 nonterminal vertices, then searches for a start whose k-step walk reaches the mark.The fixed-point search and final walk give an optimized O((Nℓ)^1/4) bound for N ≤ ℓ^3; traversal suffices for larger N.Source: §1 · p. 6
• At ambient size Θ(L^3), a hidden single-list segment requires Ω(L) queries using layered paths and adversary weights that favor paths splitting near the end.With layer width L^2, the adversary weight is large while each successor or marking query accesses only a controlled part of it.Source: §1 · p. 6
• For double lists, a length-L unmarked buffer before the public exit prevents a predecessor query there from revealing the possible marked vertex; reversed buffer weights yield an Ω(L) boundary lower bound.The adversary weights increase toward the possible mark on the X-part but are reversed across the Y-buffer.Source: §1 · p. 7

1.1 Organization

• Section 4 gives bounds for the Double Linked List problem, with the upper bound in Section 4.1 and the lower bound in Section 4.2.Section 3.2 proves the lower bound.Source: §1.1 · p. 8

Amplitude amplification

• Exact amplitude amplification prepares a uniform superposition over a known-size good set using O(√(N/t)) queries when t of N inputs are good.The known good count permits certainty in the preparation procedure.Source: §2 · p. 8
• Fixed-point search uses O(1/√ε) calls when the good-state weight is at least ε, avoiding ordinary Grover search's overshooting issue.A final direct verification distinguishes the no-case.Source: §2 · p. 8

Query model and adversary bound

• The two-oracle input can be represented as one finite-alphabet string with disjoint successor and marking query coordinates, so the adversary framework applies directly.The double-list model similarly has three disjoint coordinate families for next, previous, and marking queries.Source: §2 · pp. 8–9
• The negative-weight adversary bound characterizes bounded-error quantum query complexity up to constant factors and composes across disjoint input blocks.The paper uses the general bound for partial finite-alphabet inputs, although its explicit adversary matrices are entrywise nonnegative.Source: §2 · pp. 9–10

3.1 Upper Bound

• The nonterminal list vertices are exactly the live set, whose size is ℓ−1; exact amplitude amplification prepares their uniform superposition using O(√(N/ℓ)) queries to f.A vertex is live when its successor is not ⊥.Source: §3.1 · p. 10

The algorithm

• The algorithm scans the first k list vertices, then searches the live set for a start point whose forward walk of at most k steps reaches a mark, and finally recovers it by walking forward.Checking the predicate costs O(k) queries; if the walk reaches ⊥ early, it continues in a dummy sink state before uncomputing its workspace.Source: The algorithm · pp. 10–11

Correctness

• If the first k vertices are unmarked and the mark lies later, k or k+1 live vertices are good starting points, while no marked vertex makes every live vertex fail the predicate.A successful candidate's recovery walk encounters the mark, and the procedure also solves the decision version with bounded error.Source: Correctness · pp. 11–12

Query complexity

• The query analysis includes the O(k) prefix scan, O(√(N/ℓ)) state preparation, O(k)-query predicate checks during fixed-point search, and an O(k) recovery walk.When N > ℓ^3, directly traversing the list uses O(ℓ) queries.Source: Query complexity · p. 12

Critical segment

• At the critical ambient size L^3, an explicit adversary matrix proves that a quantum algorithm needs Ω(L) queries for one anchored segment.This is the boundary lower bound on which the full reduction rests.Source: §3.2 · pp. 12–13

Packing and composition

• With at most one positive segment, concatenating anchored segments reduces the whole-list decision problem to a unique-solution OR of the segment answers.Public entrances and exits let the segments be joined by fixed unmarked bridge vertices.Source: §3.2 · p. 13
• Packing m critical segments gives a lower bound Ω(√m L0); choosing their size and count to fit N and ℓ yields Ω((Nℓ)^1/4) when N ≤ ℓ^3.For N ≥ ℓ^3, one critical segment of length Θ(ℓ) gives the linear lower bound Ω(ℓ).Source: §3.2 · p. 13

3.2.1 Anchored segments

• An anchored segment has public entry and exit points, with the exit serving as a bridge to the next segment in a concatenation.Its hidden vertices form a path from the entry through L distinct vertices to the exit; the decision output is 1 exactly when a segment vertex is marked.Source: §3.2.1 · p. 13
• The lower bound for anchored segments at the cubic threshold is the section's core technical statement.The boundary lower bound is used to derive the full lower bound.Source: §3.2.1 · p. 14

3.2.3 Two standard adversary facts

• A restriction isomorphic to G gives a lower-bound route for F because any adversary matrix for G extends to F by zero-filling other rows and columns.The bound is monotone under restrictions.Source: §3.2.2 · p. 14
• Repeated-block composition applies a partial outer function F to the outputs of m disjoint copies of a partial Boolean inner function G.The section uses this theorem only when F is unique-OR.Source: §3.2.2 · p. 14
• Θ(√m) queries are required for UOR_m, which computes OR under the promise that at most one input bit is 1.This follows from Grover’s algorithm [Gro97], the standard unstructured-search lower bound, and the tight adversary characterization.Source: §3.2.2 · p. 14

3.2.3 Serial packing

• Serial packing restricts HLLDEC(mN0 + m, mL0 + m) to m anchored segments of parameters (N0, L0) placed in series.Under the promise that at most one segment is positive, the restricted problem is exactly the blockwise composition of the local decision problems.Source: §3.2.3 · p. 14
• The construction assigns disjoint address sets to the segments and places a bridge vertex between consecutive segments.Each segment uses its preceding bridge as entry and its following bridge as exit; unused addresses are made dead.Source: §3.2.3 · p. 15
• Only local segment inputs vary, while bridge data are fixed; the global list is positive exactly when at least one local segment is positive.The promise that at most one local segment is positive makes the global decision problem the corresponding unique-OR composition.Source: §3.2.3 · p. 15

3.2.4 From the boundary lower bound to all parameters

• In the regime N ≥ ℓ^3, the lower bound is linear in ℓ; for N ≤ ℓ^3, serial packing yields Ω((Nℓ)^1/4).The theorem states a lower bound for hidden linked-list decision for all N ≥ ℓ ≥ 1, and the search lower bound follows from decision hardness.Source: §3.2.4 · pp. 16, 20
• For the large-universe case, the proof embeds one anchored segment of length ℓ−1 and uses a bridge vertex to terminate it.The remaining addresses are padded with dead vertices to obtain a restriction of HLLDEC(N, ℓ).Source: §3.2.4 · p. 16
• For N < ℓ^3, the proof serially packs smaller cubic-threshold anchored segments, appending a fixed unmarked tail when needed to reach list length ℓ.The construction must fit within both the ℓ-vertex list budget and the N-address universe; the proof verifies the tail also fits.Source: §3.2.4 · pp. 16–17
• Monotonicity under restriction and adversary composition transfer the packed-segment lower bound to the full hidden linked-list problem.The proof establishes feasibility of the packed restriction before applying these adversary facts.Source: §3.2.4 · p. 19

The adversary matrix

• The adversary matrix gives greater weight to yes/no path pairs that agree for a longer prefix, because such pairs are harder for a query to distinguish.Pairs that split early can be distinguished near the beginning, while late-splitting pairs require learning deeper path information.Source: §3.2.5 · p. 20

The layered hard family

• The hard family forces the hidden path to choose one vertex from each of r layers, with yes- and no-inputs sharing a path and differing only in whether its tail is marked.The path is specified by a tuple of layer labels; only the final-layer vertex can be marked.Source: §3.2.5 · p. 21, Figure 2 · p. 21

The adversary matrix

• The matrix is organized by the coordinate of the first disagreement, with equality required before that coordinate and suffix coordinates averaged uniformly.This coordinate-wise structure is used to analyze the filtered matrices formed by queries.Source: §3.2.5 · p. 22

The denominator of the adversary bound

• Query filtering preserves the tensor-product structure by refining local factors; internal successor queries can affect two coordinates, unlike one-coordinate query restrictions.The proof states separate local norm estimates for one-coordinate matrices and for the two-coordinate matrix arising from internal successor queries.Source: §3.2.5 · p. 24
• Lemma 3.13 states an absolute-constant bound for every r and M on the filtered adversary matrices.The supplied passage omits the bound's formula, so its magnitude is not specified here.Source: §3.2.5 · p. 25

3.2.5 The boundary lower bound

• For internal successor queries, filtering retains only disagreements in which the query answers differ, replacing local tensor factors while leaving all other factors unchanged.The analysis combines four cases for the internal successor query.Source: §3.2.5 · pp. 27–28
• For last-layer successor queries, the filter replaces the final B-coordinate or P-factor with a factor retaining pairs where exactly one value equals a.Source: §3.2.5 · pp. 28–29
• The four query types yield bounds r, M + 2r, and r, respectively, with the resulting estimate holding for an absolute constant C > 0.Source: §3.2.5 · p. 29

• The projector E_a and rank-one projection P each have norm 1.Source: Proof of Lemma 3.11 · p. 29
• J − I has eigenvalue M − 1 on the uniform vector and eigenvalue −1 on vectors orthogonal to it.Source: Proof of Lemma 3.11 · p. 29
• T_a has one nonzero row, while S_a is expressed in a reordered basis as a block matrix involving an all-ones vector.Source: Proof of Lemma 3.11 · pp. 29–30

• Inactive states have ϕ_a-value ⊥, whereas an active state (a, y) has ϕ_a-value y.Source: Proof of Lemma 3.12 · p. 30
• In the I, A basis, H_a has a block form whose all-ones block J has dimensions M(M − 1) × M.Source: Proof of Lemma 3.12 · p. 30
• An all-ones p × q matrix has norm √pq, which supplies the norm used in the block-matrix bound.Source: Proof of Lemma 3.12 · p. 30

Conclusion of the boundary lower bound

• For L = 1, deciding whether the unique segment vertex is marked requires Ω(1) queries, establishing the boundary case.Source: Conclusion of the boundary lower bound · p. 31
• For r ≥ 2, the restricted layered adversary gives an Ω(r) lower bound, yielding the boundary lower bound for segment length L.The layered family is a restriction of ASEGDEC(L³, L), and adversary-bound monotonicity transfers the lower bound to that problem.Source: Conclusion of the boundary lower bound · p. 31
• The layered construction reaches a linear-in-r lower bound at ambient size rM ≳ r³; below that threshold it no longer yields Ω(r).Source: Conclusion of the boundary lower bound · p. 31
• When N ≤ ℓ³, packing m ≈ ℓ/L0 segments of length L0 ≈ (N/ℓ)^(1/3) gives Ω(√m L0) = Ω((Nℓ)^(1/4)).Each segment contributes Ω(L0), and the outer unique-OR contributes Ω(√m).Source: Conclusion of the boundary lower bound · p. 32

4.2 Lower bound

• A predecessor query at the public exit can reveal the preceding segment’s last hidden vertex, so the lower bound uses buffered segments and a different adversary-weighting strategy.The mark lies at the end of the core path, followed by an unmarked buffer; the public exit sees only the buffer’s end.Source: §4 · p. 32, §4.2 · pp. 34–35

4.1 Upper bound

• O((Nℓ)^1/4) queries suffice when N ≤ ℓ^3, while traversing the list uses O(ℓ) queries when N > ℓ^3.The algorithm searches for a vertex within distance k of a mark, verifies a candidate by walking in both directions, and also solves decision by searching.Source: §4.1 · p. 33

4.2.1 Buffered anchored segment

• The buffered anchored segment places a possibly marked core path before an unmarked buffer, and the section establishes a boundary lower bound for this problem.Only the core’s last vertex can be marked; the public exit is after the buffer.Source: §4.2.1 · pp. 35–36

4.2.2 Serial packing of buffered segments

• Serial packing places independent buffered segments in disjoint query blocks, making the global list positive exactly when one segment is positive.The reduction uses unique-OR on the segment instances and composes their negative adversary bounds.Source: §4.2.2 · p. 36

4.2.3 From the boundary lower bound to all parameters

• For N ≥ ℓ^3, the lower-bound construction yields Ω(ℓ) queries for double linked-list decision.It embeds one buffered segment, pads the list to length ℓ, and fits the construction within the address universe.Source: §4.2.3 · p. 37
• The passage concludes HDDLSearch(N, ℓ) has the same lower bound, since any search algorithm decides whether a marked vertex exists.Source: §4.2.3 · p. 39

4.2.4 Proof of the buffered boundary lower bound

• An asymmetric adversary concentrates its largest weights at the private middle interface, increasing toward xr on the X-core and y1 from the exit side on the buffer.The buffer prevents prev(q) from directly revealing the marked endpoint; middle-concentrated weights avoid making a mark query at xr capture the whole adversary mass.Source: §4.2.4 · pp. 40, 43
• Reversing Y-buffer coordinates maps internal successor queries to X-core predecessor filters and vice versa, transferring the Lemma 4.6 estimates.Source: §4.2.4 · pp. 49–50
• The buffered-bound argument obtains an adversary ratio of Ω(r), establishing its key lower-bound estimate.Source: §4.2.4 · p. 50
• Restriction monotonicity and r=L yield an absolute c_buf for every L≥1, completing Theorem 4.4.Source: §4.2.4 · p. 50

5.1 Proof of Proposition 1.3

• Θ(ℓ) classical queries suffice and are necessary for linked-list decision: traversal gives the upper bound, while deterministic and randomized lower bounds are Ω(ℓ).The randomized argument requires at least ℓ/3 queries for success probability at least 2/3.Source: §5.1 · pp. 52–53
• Fixing the path makes linked-list decision exactly unique-OR on ℓ bits, under the promise that at most one bit is 1.This restriction makes the ambient embedding public and irrelevant to the input.Source: §5.1 · p. 52

5.2 Model and Proof of Hidden Ordered Search

• Hidden ordered search uses a hidden support set in [N], arranged as a balanced binary search tree, with monotone comparison bits; the task is to output the first support vertex whose bit is 1.The support vertices are considered in in-order sequence.Source: §5.2 · p. 53
• Θ(log n) quantum queries solve hidden ordered search: tree traversal gives an O(log n) upper bound, and restricting the tree and pointers to public values yields the ordinary ordered-search lower bound.The lower bound is Ω(log n).Source: §5.2 · p. 53
• For ordered search, the ambient universe is asymptotically irrelevant because comparisons still funnel the algorithm along a logarithmic decision tree.Merely embedding a structured search problem in a larger universe does not by itself produce a new asymptotic quantum speedup.Source: §5.2 · p. 53