Quantum Sketches, Hashing, and Approximate Nearest Neighbors

• URL: http://arxiv.org/abs/2602.19259v1
• Date: Sun, 22 Feb 2026 16:18:36 GMT
• Title: Quantum Sketches, Hashing, and Approximate Nearest Neighbors
• Authors: Sajjad Hashemian,
• Abstract summary: 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$.<n>For every approximation factor $cge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $0,1d$ with $d=(log n)$ for which any such sketch requires $m=(n)$ qubits.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $ρ_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 $\{0,1\}^d$ with $d=Θ(\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.

Related papers

• Nearly Optimal Circuit Size for Sparse Quantum State Preparation [0.0]
  A quantum state is said to be $d$-sparse if it has only $d$ non-zero amplitudes.<n>We prove for the first time a trade-off between the number of ancillary qubits and the circuit size.
  arXiv  Detail & Related papers  (2024-06-23T15:28:20Z)
• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  Unitarity estimation is a basic and important problem in quantum device certification and benchmarking. We provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms. We show that both the $d$-dependence and $epsilon$-dependence of our algorithms are optimal.
  arXiv  Detail & Related papers  (2022-12-19T09:36:33Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.