PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, Erik Waingarten

arXiv:1608.03580v2cs.DScs.CCcs.CGcs.IR

TL;DR

The paper studies preprocessing point sets for near-neighbor queries and notes unresolved questions in the near-linear-space regime. It gives a data structure spanning time–space trade-offs, with a stated Euclidean ANN structure using the following space and query time.

  • Problem

    The paper studies preprocessing point sets for near-neighbor queries and notes unresolved questions in the near-linear-space regime.

    Source: §1.1 · p. 3, §1.3 · p. 4

  • Method

    The paper gives an algorithm for the entire range of time–space trade-offs, including sublinear query time.

    Source: §1.5 · p. 5

  • Results

    The stated (c, r)-ANN structure in R^d uses space n^(1+rho_u+o(1)) + O(dn) and query time n^(rho_q+o(1)) + d n^o(1).

    Source: §1.5 · p. 5

  • Takeaways & Limitations

    The reported construction covers the full time–space trade-off range and includes sublinear query time.

    Source: §1.5 · p. 5

    For decision ANN on random instances, the argument supports words of size o(log n), but does not handle words of size Ω(log n), owing to weak known lower bounds for two-query LDCs over large alphabets.

    Source: §1.6.2 · p. 9

Abstract

from arXiv · show

[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the $c$-Approximate Near Neighbor Search problem. For the $d$-dimensional Euclidean space and $n$-point datasets, we develop a data structure with space $n^{1 + \rho_u + o(1)} + O(dn)$ and query time $n^{\rho_q + o(1)} + d n^{o(1)}$ for every $\rho_u, \rho_q \geq 0$ such that: \begin{equation} c^2 \sqrt{\rho_q} + (c^2 - 1) \sqrt{\rho_u} = \sqrt{2c^2 - 1}. \end{equation} This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor $c > 1$, improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for $\rho_q = 0$, improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.

1 Introduction

The introduction motivates approximate near-neighbor search as a way to avoid exact-search dimensionality costs and presents time–space trade-offs for Euclidean ANN. It outlines hashing-based techniques, including a data-independent procedure and data-dependent partitions, and describes extending a sphere-based bound to all of R^d.

1.1 Approximate Near Neighbor problem (ANN)

  • ANN promises a point within cr when a dataset point lies within r, relaxing exact near-neighbor search to address its dimensionality costs.The problem is defined on a dataset in a metric space with a query point and threshold r.Source: §1.1 · p. 3

1.2 Locality-Sensitive Hashing (LSH) and beyond

1.3 Time–space trade-offs

  • No known algorithm in the introduction achieves near-linear space and sublinear query time for every c > 1; the best cited bound is due to [Kap15].That bound has query time roughly n^(4/(c²+1)).Source: §1.3 · p. 4

1.4 Lower bounds

  • Because strong cell-probe lower bounds are difficult to prove, ANN research also studies restricted models that capture existing approaches, including LSH and data-dependent LSH.The introduction notes a lack of viable techniques for proving ω(log n) query-time lower bounds for ANN.Source: §1.4 · pp. 4–5

1.5 Our results: upper bounds

  • Theorem 1.1 gives Euclidean (c, r)-ANN space n^(1+ρu+o(1)) + O(dn) and query time n^(ρq+o(1)) + d n^o(1), for every c > 1 and stated ρq, ρu.The paper states that the algorithm has optimal exponents for hashing-based algorithms and one- and two-probe data structures.Source: §1.5 · p. 5
  • For near-linear space, setting ρu = 0 yields query time n^(1/(2c²−1)+o(1)); setting ρq = 0 yields query time n^o(1).The introduction also states that equal exponents recover the best data-dependent LSH bound [AR15].Source: §1.5 · p. 6
  • The upper bounds extend to ℓp spaces for 1 ≤ p < 2 by replacing c² with c^p, and support insertions and deletions with logarithmic loss.The update time is d n^(ρu+o(1)).Source: §1.5 · p. 6

1.5.1 Techniques

  • The proof first handles random Euclidean instances, then combines that approach with data-dependent LSH [AINR14] [AR15] for worst-case instances.The data-independent stage modifies spherical locality-sensitive filtering and, by itself, gives a significantly worse bound.Source: §1.5.1 · p. 6
  • The Gaussian decision-tree procedure achieves desired trade-off (2) for 2c, but gives an inferior worst-case trade-off (3) on the unit sphere.The parameters T, K, ηu, and ηq depend on r, c, ρu, and ρq; ηu = ηq is the LSH regime, while ηu < ηq and ηu > ηq correspond to fast queries and low memory, respectively.Source: §1.5.1 · p. 7
  • Theorem 1.2 gives a whole-R^d (c, r)-ANN structure for every c > 1 and nonnegative ρq, ρu satisfying trade-off (3), with space n^(1+ρu+o(1)) + O(dn).Its query time is n^(ρq+o(1)) + d n^o(1), as stated in the paper context.Source: §1.5.1 · p. 7
  • Data-dependent partitions extract dense, low-diameter clusters for recursive re-centering and apply Gaussian sampling to the remainder, making both parts amenable to the data-independent procedure.Repeated re-centering makes clusters more isotropic; the absence of dense clusters lets the data-independent step work for one tree level.Source: §1.5.1 · p. 7
  • For worst-case instances, data-dependent partitions improve Theorem 1.2 to the final Theorem 1.1, building on data-dependent LSH [AINR14] [AR15].The construction uses the reduction to assume data points and queries lie on the unit sphere.Source: §1.5.1 · p. 7
  • The analysis avoids the Gaussian-partition behavior on triples of points required by [AR15], simplifying the overall argument, though many moving parts still require fine-tuning.The authors note that they hope the algorithm will be further simplified.Source: §1.5.1 · p. 8

1.6 Our results: lower bounds

The paper gives cell-probe lower bounds and a restricted-model lower bound for ANN, matching its upper bounds in the stated settings. The two-probe argument connects ANN data structures to locally-decodable codes, while the broader trade-off bound applies to a hashing-based model.

1.6 Our results: lower bounds

  • The lower bounds use a canonical hard distribution for Hamming space, with similar hardness results transferred to ℓ_p for 1 < p ≤ 2 by a standard reduction.The reduction replaces c with c_p.Source: §1.6 · p. 8

1.6.1 One cell probe

  • The one-probe result gives a tight space lower bound for random-instance ANN, matching the space of the corresponding single-probe upper bound.The theorem concerns Hamming random instances and single-cell queries.Source: §1.6.1 · p. 8

1.6.2 Two cell probes

  • With two probes, the second probe cannot improve the space bound by more than a subpolynomial factor, closing the previous polynomial gap from.The result is described as the first static-data-structure space lower bound without a polynomial gap between one and at least two probes.Source: §1.6.2 · p. 9
  • The two-probe proof turns a data structure violating the bound into an implausibly efficient two-query locally-decodable code, contradicting known code lower bounds.The theorem allows words of size o(log n); the argument is limited by known lower bounds for large-alphabet codes.Source: §1.6.2 · p. 9

1.6.3 The general time–space trade-off

  • The conditional lower bound matches the time-space trade-off in a list-of-points model for random Hamming instances with space n^(1+ρu) and query time n^(ρq−o(1)).The theorem assumes success probability 2/3 and d = ω(log n).Source: §1.6.3 · p. 10
  • The list-of-points model captures basic hashing algorithms, including Locality-Sensitive Filters, but excludes the cited data-dependent schemes.The authors conjecture that extending the model to data-dependent settings would yield the same lower bound.Source: §1.6.3 · p. 10

1.7 Related work: past and concurrent

  • The concurrent work gives a similar but suboptimal upper bound and an independent conditional lower bound.The passage situates relative to this paper and the merged preprints.Source: §1.7 · p. 11

1.8 Open problems

  • The worst-case algorithms are described as impractical, with the clustering step inherited from [AR15] a bottleneck; the authors ask whether simpler optimal algorithms are possible.They also ask whether locally-decodable codes can help avoid the barrier posed by hashing-based approaches.Source: §1.8 · pp. 11–12

2 Random instances

The paper defines random ANN instances in Hamming and Euclidean spaces. These distributions are used in both upper- and lower-bound arguments.

Role of the instances

  • These random instances are central to the paper’s upper- and lower-bound arguments.Source: §2 · p. 12

Hamming distance

  • In the Hamming setting, a query is generated by choosing a dataset point uniformly and independently flipping each coordinate with probability 1/(2c).The resulting dataset-query pairs define the random Hamming instances.Source: §2 · p. 12

Euclidean distance

  • In the Euclidean setting, the dataset consists of independent uniform random unit vectors, and the query is drawn near a uniformly chosen dataset point.The dimension assumption is d = ω(log n), so pairwise distances concentrate around a specified value.Source: §2 · pp. 12–13

3 Upper bounds: data-independent partitions

This section develops Gaussian-based data-independent partitions for approximate near neighbors and analyzes the tree data structure they enable, establishing upper bounds for worst-case and random instances. It controls query work through far-point collisions and parameter choices to obtain the trade-off, and also presents an alternative spherical filtering construction based on blockwise codewords and joint decoding.

3.1 Setup

  • The setup defines Gaussian tail and joint-threshold probabilities, with the latter depending on the distance between sphere points and non-increasing in that distance.It also states bounds on these probabilities and assumes dimension reduction via the Johnson–Lindenstrauss lemma.Source: §3.1 · p. 13

3.2 Results

  • For every c > 1, Theorem 3.3 gives a spherical (c, r)-ANN data structure with a space-query trade-off; Corollary 3.4 extends the result to R^d.The section also notes that its worst-case bound is later improved in Section 4.Source: §3.2 · p. 14
  • For random instances, Corollary 3.5 achieves the trade-off promised in Theorem 1.1; at c = 2 and ρ_q = 0, space improves from n^2.77... to n^1.77....The section says the random-instance trade-off is significantly better than the general bound and that Section 4 obtains it for worst-case instances.Source: §3.2 · p. 15

3.3.1 Description

  • The construction is a K-level tree of Gaussian-vector spherical caps: preprocessing branches on dataset points passing thresholds, and queries descend through qualifying children before scanning leaves.Each node stores a subset of points; the leaves store their subsets explicitly.Source: §3.3.1 · p. 16

3.3.2 Analysis

  • With a near neighbor present, the query returns a point within distance cr with probability at least 0.9 under the lemma's stated condition.Expected query time is bounded by n^o(1)·T·(T·F(η_q))^K + n^1+o(1)·(T·G(cr, η_u, η_q))^K; the analysis also bounds expected space using leaf-set sizes.Source: §3.3.2 · pp. 16–18
  • For each far point and leaf, the probability that both it and the query reach that leaf is at most G(cr, ηu, ηq)^K, yielding the second query-time term.There are at most n − 1 far points, and processing each corresponding point takes n^o(1) time.Source: §3.3.2 · p. 18

3.3.3 Setting parameters

  • The chosen parameters yield the desired space–query trade-off, with the endpoint corresponding to ρ_q = 0.The analysis balances query-time terms and selects parameters to satisfy the relation leading to trade-off (5).Source: §3.3.3 · pp. 18–19

3.3.4 An algorithm based on Locality-Sensitive Filtering (LSF)

  • Spherical LSF partitions Rd into K blocks and retains a point p when the sum of its K blockwise inner products with the selected vectors is at least K · ηu.Source: §3.3.4 · p. 20

4 Upper bounds: data-dependent partitions

This section presents a worst-case Euclidean approximate-neighbor data structure based on a single decision tree that combines recursive handling of dense clusters with pseudo-random partitioning. It describes the parameter settings and analysis that yield success probability at least 0.9, expected space n^(1+rho_u+o(1)), and expected query time n^(rho_q+o(1)).

4 Upper bounds: data-dependent partitions

  • For every c > 1 and admissible ρq, ρu, the data structure supports (c, r)-ANN over all of R^d using space n^(1+ρu+o(1)) + O(dn) and query time n^(ρq+o(1)) + d n^o(1).It achieves the trade-off for worst-case datasets and improves the time-space trade-off previously obtained for worst-case instances to that for random instances.Source: §4 · p. 20
  • Unlike [AR15], the construction uses a single decision tree and needs no three-point property; one tree succeeds with constant probability rather than polynomially small probability.The improvement combines the result of Section 3 with techniques from [AR15].Source: §4 · pp. 20, 22

4.1 Overview

  • The overview partitions the dataset into dense clusters and a pseudo-random remainder, recursively shrinking cluster-enclosing spheres and applying projection-based partitioning to the remainder.Dense clusters are processed recursively; the remainder is treated like a random instance, where the Section 3 data structure performs well.Source: §4.1 · pp. 22–23

4.2 Description

  • The formal construction handles dense components with recursive ball processing and converts balls to spherical instances by discretizing them into thin annuli.For each annulus, it rounds point-to-center distances and recursively builds a spherical data structure for relevant query annuli.Source: §4.2 · p. 25
  • Queries traverse a decision tree, recursively searching cluster structures and spherical caps, while ball nodes reject distant queries or enumerate candidate neighbor distances.Preprocessing creates a tree whose root runs Process and whose later nodes correspond to ProcessSphere and ProcessBall.Source: §4.2 · pp. 25–26

4.3 Setting parameters

  • The parameters ηu, ηq, and T are chosen to replicate the random-instance settings, using r* as an effective r2 and keeping τ much smaller than n^-1/K.When r2 ≥ 2R, r* is set to r2; otherwise the parameter choice is adjusted to achieve constant success probability.Source: §4.3 · p. 26

4.4 Analysis

  • Each recursive iteration increases the potential by 1 + Ω(ε^2), while the analysis bounds key invariants and the number of ProcessBall calls on the recursion stack.The invariants include r2/r1 ≥ c·(1 − o(1)), r2 ≤ c·(1 + o(1)), and at most e^O(log log n) ProcessBall calls on the stack.Source: §4.4 · pp. 27, 31
  • The number of ProcessBall calls along a path is eO(log log n).This bounds a source of tree overhead in the space analysis.Source: §4.4 · pp. 32–33
  • The algorithm can always choose settings for eta_u and eta_q.The analysis considers the two cases for the selected radius r* when establishing these parameter choices.Source: §4.4 · pp. 32–33
  • The data structure succeeds with probability at least 0.9.The analysis treats the pseudo-random remainder separately; the other cases are deterministic.Source: §4.4 · p. 33
  • The data structure occupies at most n^(1+rho_u+o(1)) space in expectation.The analysis bounds point duplication, with duplication from other nodes contributing only n^o(1).Source: §4.4 · p. 33
  • The expected query time is at most n^(rho_q+o(1)).The analysis bounds both the expected number of visited nodes and the points tested at the final level.Source: §4.4 · p. 34

5 Lower bounds: preliminaries

The lower-bound preliminaries define approximate nearest neighbor search and introduce Graphical Neighbor Search and robust expansion as tools for lower bounds. They also present locally-decodable codes, which the paper uses for its two-query lower bound.

5 Lower bounds: preliminaries

  • The (c, r)-ANN definition uses points in {−1, 1}^d and requires returning a point within distance cr with probability at least 1−δ when a point lies within distance r.The stated distances are L1 distances.Source: §5 · p. 36

5.1 Graphical Neighbor Search and robust expansion

  • In Graphical Neighbor Search, dataset points come from U, queries from V, and a query with a unique neighboring dataset point must return its associated bit.The paper reduces ANN lower bounds to GNS by connecting cube points whose Hamming distance is at most r and ensuring other points are not within cr.Source: §5.1 · p. 36
  • Robust expansion Φr(δ, γ) is introduced for a GNS graph under an edge distribution and its marginals on U and V.The cited prior work relates ANN lower bounds to a quantity of a metric space.Source: §5.1 · p. 36

5.2 Locally-decodable codes (LDC)

  • A locally-decodable code encodes n-bit strings into m-bit codewords and recovers a requested bit with probability 1/2+ε using t queries, even after arbitrary corruption.The paper says it uses a weaker LDC definition for its two-query lower bound and invokes a lower bound on LDC size.Source: §5.2 · pp. 36–37

6 Lower bounds: one-probe data structures

This section bounds robust expansion in the Hamming space and uses those bounds to prove lower bounds for one-probe data structures.

6.1 Robust expansion of the Hamming space

  • The section computes tight robust-expansion bounds in Hamming space for use in lower bounds in subsequent sections.The proof applies the Bonami-Beckner and Hölder inequalities, giving flexibility in the parameters.Source: §6.1 · pp. 37–38
  • The query model samples a dataset point uniformly and generates its query from the point’s neighborhood distribution Nσ.Nσ independently keeps each coordinate with probability σ and otherwise samples it uniformly.Source: §6.1 · p. 37
  • For the random query model, a sampled dataset point is within distance d/(2c)(1+o(1)), while every other point is at least d/2(1−o(1)) away.These distances differ by a factor of c−o(1).Source: §6.1 · p. 37

6.2 Lower bounds for one-probe data structures

  • The section derives one-probe cell-probe lower bounds for c-approximate nearest neighbor structures by applying its robust-expansion bound.The result is stated for structures with subpolynomial cell size.Source: §6.2 · p. 40

7 Lower bounds: list-of-points data structures

This section proves a lower bound for list-of-points data structures in Hamming space, relating their space and query-time exponents.

7 Lower bounds: list-of-points data structures

  • For list-of-points structures, the lower bound requires the space and query-time exponents ρu and ρq to satisfy Equation 4.The section states this as a tight lower bound.Source: §7 · pp. 40, 42
  • The theorem treats c-approximate nearest neighbor search on d-dimensional Hamming space when d=ω(log n).It analyzes expected space s=n^(1+ρu) and expected query time n^(ρq−o(1)).Source: §7 · p. 40
  • The proof studies a random Hamming-space instance, with uniform dataset points and queries drawn from a random dataset point’s neighborhood.It models each list by the dataset points it contains and the queries that scan it.Source: §7 · pp. 40–41

8 Lower bounds: two-probe data structures

This section establishes a two-probe cell-probe lower bound and connects two-probe data structures to locally-decodable codes. The connection supports lower bounds for the two-probe setting.

8 Lower bounds: two-probe data structures

  • The section proves a cell-probe lower bound for data structures using two probes, as stated in Theorem 1.4.Theorem 8.1 addresses non-adaptive GNS data structures; the proof also extends to adaptive algorithms with sub-polynomial space loss when w=o(log n).Source: §8 · pp. 43–44
  • A two-probe GNS data structure that is too efficient would imply a weaker two-query locally-decodable code with small noise using the same space.The authors adapt lower-bound tools for two-query locally-decodable codes from.Source: §8 · pp. 44–45
  • The proof proceeds from deterministic non-adaptive structures through low-contention structures and recovery under cell corruption to a weaker locally-decodable code.It uses quantum-information-theoretic arguments for the code lower bound.Source: §8 · pp. 44–45

8.1 Deterministic data structures

The section defines non-adaptive randomized two-probe algorithms and the distributions used to evaluate them. It then uses Yao’s principle to obtain a deterministic algorithm with at least the assumed success probability.

8.1 Deterministic data structures

  • A non-adaptive randomized two-probe algorithm preprocesses a dataset and bit-string into memory, then selects two cell indices and an output function for each query.The algorithm’s query procedure does not depend on the dataset or bit-string.Source: §8.1 · p. 45, We require the data structure D and… · p. 45

We require the data structure D and the algorithm R satisfy

  • The analysis draws datasets and bit-strings uniformly and generates a query by choosing a dataset point uniformly, then sampling from its neighborhood.By Yao’s principle, the assumed success probability yields a deterministic non-adaptive algorithm achieving at least that probability over these distributions.Source: We require the data structure D and… · p. 45

8.2 Making low-contention data structures

The section defines low contention to limit reliance on any one cell and shows that a two-probe data structure can be transformed to satisfy this condition with only a constant-factor increase in cells, preserving its success probability.

8.2 Making low-contention data structures

  • Low contention limits how much the algorithm relies on any one cell by requiring that no probe-query set A_t,j is too large.The algorithm's two probe-index collections independently partition the query space, and each query outputs the indices of its two corresponding cells.Source: §8.2 · p. 46
  • A deterministic two-probe GNS algorithm using m cells can be replaced by one using at most 3m cells, with low contention and the same success probability.The transformation partitions large query sets that probe a cell and creates duplicate cells with the same contents for the resulting sets.Source: §8.2 · p. 46

8.3 Datasets which shatter

The section uses weak shattering to identify dataset points whose near-neighbor queries probe disjoint cells, then shows that most points in a random dataset satisfy the relevant shattering conditions.

8.3 Datasets which shatter

  • Weak shattering captures points whose near-neighbor queries probe various disjoint cells, so the corresponding bit is stored in many cells.The section defines shattering for partitions and invokes the shattering lemma of [PTW10].Source: §8.3 · p. 47
  • For a point weakly shattered by both probe partitions, the sets β1 and β2 can be chosen with measure at most γ each, leaving slack β(p) of measure at most 2γ.The slack is removed when considering correctly answered queries near that point.Source: §8.3 · p. 47
  • For a collection A, a point satisfies S(A,p) with probability at least 1−γ when sampled from μ.The section also relates the average recovery probability over datasets that are good to a lower bound of 2/3−o(1).Source: §8.3 · pp. 47–48
  • With high probability, at most 4γn dataset points fail the weak-shattering conditions for both probe partitions.The expected number of such points is at most 2γn, and a Chernoff bound yields the stated high-probability limit.Source: §8.3 · p. 47

8.4 Corrupting some cell contents of shattered points

The section studies whether a two-probe algorithm can recover dataset bits after some cell contents are corrupted. It establishes robust recovery for a linear-size set of points under a bounded number of corruptions.

8.4 Corrupting some cell contents of shattered points

  • The section's goal is to obtain constant recovery probability, averaged over inputs, for Ω(n) coordinates despite cell corruption.A corrupted data structure differs from the original in at most k cells.Source: §8.4 · pp. 48–49
  • The robust-recovery argument applies to points weakly shattered by both probe partitions, with their slack set aside before accounting for corrupted cells.Queries that avoid the corrupted cells return the same bit as before corruption; the resulting probability bound subtracts 2γ for slack and 2ε for corruption.Source: §8.4 · pp. 49–50
  • A two-probe algorithm recovers bits for a set S of size Ω(n) with probability at least 1/2 + ν − 2γ − 2ε, even when εK cells are corrupted.The recovery probability is averaged over the input bit strings and queries near the associated dataset point.Source: §8.4 · p. 50

8.5 Decreasing the word size

The section reduces the word size of the two-probe recovery algorithm to one bit by storing all parities of each original cell. This increases space and lowers the stated recovery advantage.

8.5 Decreasing the word size

  • The reduction supports applying lower bounds for two-query locally decodable codes by converting each w-bit cell's decoder into a decoder over parity bits.For a query, the construction evaluates a parity or its negation using cells containing the parities of the original probed words.Source: §8.5 · p. 51
  • A one-bit-cell algorithm uses m·2^w cells to simulate the original m-cell, w-bit data structure, storing all parities of each cell's bits.The construction increases the space by a factor of 2^w.Source: §8.5 · p. 51
  • After the word-size reduction, the two-probe decoder's recovery probability is stated as 1/2 + η/2^(2w), including under corruption of εK cells.The conversion applies to coordinates i in S; the passage gives the reduced probability as 1/2 + η/2^(2w).Source: §8.5 · p. 51

8.6 Connection to locally-decodable codes

This section connects two-probe recovery in GNS data structures to locally decodable codes and weak quantum random-access codes. It adapts quantum-algorithm and random-access-code arguments to extend two-query lower bounds to adaptive probes and derive tight Hamming-space bounds when w=o(log n).

8.6 Connection to locally-decodable codes

  • Lemma 8.19 considers deterministic, non-adaptive algorithms using two probes to recover coordinates even when εK data-structure cells are corrupted.The guarantee applies to a fixed set S of size Ω(n); the supplied passage does not show the full recovery-probability bound.Source: §8.6 · p. 52

8.6.1 Crash course in quantum computing

  • The proof uses quantum states and queries in superposition as tools for analyzing recovery from the data structure.A multi-qubit state is represented over bit-string basis states, and quantum queries may be made in superposition.Source: §8.6.1 · p. 52

8.6.2 Weak quantum random access codes from GNS algorithms

  • The GNS algorithm has weaker-than-LDC guarantees: it recovers only coordinates in S, with success 1/2 + η averaged over random x and i ∈ S.It tolerates εK corruptions, and the proof adapts to these weaker guarantees, using quantum random-access-code reasoning.Source: §8.6.2 · p. 53
  • A one-query quantum algorithm can simulate the GNS algorithm’s two classical probes, enabling the proof’s quantum-code analysis.The passage describes this simulation as a step toward Lemma 8.23 and the proof of Lemma 8.19.Source: §8.6.2 · pp. 54–55
  • The proof of Lemma 8.23 follows to construct a weak quantum random access code from GNS algorithms using measurements on r copies of |U(x)>.It repeats the measurement until observing the designated outcome, then uses Lemma 8.26; otherwise it outputs a uniformly random bit.Source: §8.6.2 · p. 57

8.6.3 On adaptivity

  • Lemma 8.27 converts a deterministic two-query adaptive structure into a non-adaptive one by guessing the first probe’s contents, with reduced success advantage.When the guess is wrong, the simulation outputs a random value; when correct, it uses the non-adaptive algorithm’s output.Source: §8.6.3 · p. 57
  • For w=o(log n), the resulting inequality yields tight Hamming-space lower bounds up to sub-polynomial factors.The passage states this bound for the Hamming space when w=o(log n).Source: §8.6.3 · p. 57
Loading 1608.03580v2…