Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.19259

Quantum Sketches, Hashing, and Approximate Nearest Neighbors

Sajjad Hashemian

quant-phcs.DSSubmitted Feb 22, 2026• Announced Feb 24, 2026• 0 citations
arXivHTMLPDF

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.

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

Related papers

Quantum kkk-nearest neighbors algorithm

Afrad Basheer, A. Afham, Sandeep K. Goyal

One of the simplest and most effective classical machine learning algorithms is the $k$-nearest neighbors algorithm ($k$NN) which classifies an unknown test state by finding the $k$ nearest neighbors from a set of $M$ train states. Here we present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. We show that Q$k$NN algorithm can be reduced to an instance of the quantum $k$-maxima algorithm, hence the query complexity of Q$k$NN is $O(\sqrt{kM})$. The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.

arXiv:2003.09187•Mar 20, 2020•24 citations

Optimal compression with quantum retrieval

Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar +1 more

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

quant-pharXiv:2610.06702•Oct 6, 2026•0 citations

Memory Compression with Quantum Random-Access Gates

Harry Buhrman, Bruno Loff, Subhasree Patro +1 more

In the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may "compress" it into another algorithm which uses only m log M memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m log M) memory, and runs in time Õ(T). We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.

arXiv:2203.05599•Leibniz international proceedings in informatics•Jan 1, 2022•6 citations

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

Paul Beame, Blake Holman, Niels Kornerup

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

cs.CCCross-listedarXiv:2609.40334•Oct 1, 2026•0 citations

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai, Satoshi Yoshida, Mio Murao

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.

quant-pharXiv:2609.38403•Oct 1, 2026•0 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations
Motivated by Johnson--Lindenstrauss dimension reduction, amplitude encoding, and the view of measurements as hash-like primitives, one might hope to compress an nnn-point approximate nearest neighbor (ANN) data structure into O(log⁡n)O(\log n)O(logn) qubits. We rule out this possibility in a broad quantum sketch model, the dataset PPP is encoded as an mmm-qubit state ρPρ_PρP​, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of ρPρ_PρP​. For every approximation factor c≥1c\ge 1c≥1 and constant success probability p>1/2p>1/2p>1/2, we exhibit nnn-point instances in Hamming space {0,1}d\{0,1\}^d{0,1}d with d=Θ(log⁡n)d=Θ(\log n)d=Θ(logn) for which any such sketch requires m=Ω(n)m=Ω(n)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.
One of the simplest and most effective classical machine learning algorithms is the kkk-nearest neighbors algorithm (kkkNN) which classifies an unknown test state by finding the kkk nearest neighbors from a set of MMM train states. Here we present a quantum analog of classical kkkNN −-− quantum kkkNN (QkkkNN) −-− based on fidelity as the similarity measure. We show that QkkkNN algorithm can be reduced to an instance of the quantum kkk-maxima algorithm, hence the query complexity of QkkkNN is O(kM)O(\sqrt{kM})O(kM​). The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical kkkNN and existing quantum kkkNN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.
We consider the following data compression problem. Given a string x∈{0,1}mx \in \{0,1\}^mx∈{0,1}m of Hamming weight at most nnn, compress it into a shorter string y∈{0,1}sy \in \{0,1\}^sy∈{0,1}s so that any bit xix_ixi​ of xxx can be retrieved without any error using at most ttt quantum queries to the standard oracle encoding of yyy. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on mmm except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on nnn.
In the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may "compress" it into another algorithm which uses only m log M memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m log M) memory, and runs in time Õ(T). We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))Ω(n4/3(loglogn)/(S1/3logn)) lower bound on the number of queries that a fully general quantum algorithm with at most SSS qubits of memory requires to sort nnn numbers from [n2][n^2][n2]. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family HHH from nnn bits to mmm bits, almost all hash functions in HHH require any algorithm with at most SSS qubits of memory to make Ω(nm/S)Ω(nm/S)Ω(nm/S) quantum queries to input xxx in order to compute h(x)h(x)h(x), even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing h(x)h(x)h(x) with both hhh and xxx as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.