Quantum Sketches, Hashing, and Approximate Nearest Neighbors

Motivated by Johnson–Lindenstrauss dimension reduction, amplitude encoding, and the view of measurements as hash-like primitives, one might hope to compress an $n$-point approximate nearest neighbor (ANN) data structure into $O(\log n)$ qubits. We rule out this possibility in a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state ${\rho }_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of ${\rho }_P$. For every approximation factor $c\ge 1$ and constant success probability $p>1\mathrm{/}2$, we exhibit $n$-point instances in Hamming space $\{0,1{\}}^d$ with $d=\mathrm{\Theta }(\log n)$ for which any such sketch requires $m=\mathrm{\Omega }(n)$ qubits, via a reduction to quantum random access codes and Nayak’s lower bound. These memory lower bounds coexist with potential quantum query-time gains and in candidate-scanning abstractions of hashing-based ANN, amplitude amplification yields a quadratic reduction in candidate checks, which is essentially optimal by Grover/BBBV-type bounds.