Quantum Sketches, Hashing, and Approximate Nearest Neighbors

Abstract

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 $\ddot{I}{}_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $\ddot{I}{}_P$. For every approximation factor $c\ge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $\{0,1{\}}^d$ with $d=\hat{I}˜(\log n)$ for which any such sketch requires $m=\hat{I}\text{c◯}(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.

8 pages, 1 figure, submitted to journal of Information and Computation