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/2), we exhibit (n)-point instances in Hamming space (\{0,1\}^d) with (d=\Theta(log n)) for which any such sketch requires (m=Ω(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.