{"id":"arxiv/2602.19259","url":"https://arxiv.org/abs/2602.19259","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum Sketches, Hashing, and Approximate Nearest Neighbors","domain":"quant-ph","source":"arxiv","authors":["Sajjad Hashemian"],"reviews":0,"subject":"quant-ph","summary":"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 $ρ_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $ρ_P$. For every approximation factor $c\\ge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-22","reactions":{}}