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:2610.06702

Optimal compression with quantum retrieval

Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan

quant-phcs.DScs.IRcs.ITSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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$.

AI Summary

The paper studies static membership for sparse bit strings with classical storage and exact quantum retrieval: encode $x\in\{0,1\}^m$, of Hamming weight at most $n\leq m/2$, into $s$ bits so that any requested bit can be recovered using at most $t$ quantum queries to the stored string. It considers both sequential, adaptive queries and parallel, non-adaptive queries. For adaptive retrieval, it establishes $s_Q(m,n,t)=O\!\left(n^{1-1/t}m^{1/t}\log^{1-1/t}(m/n)\right)$. This approaches the existing lower bound $\Omega\!\left(tn^{1-1/t}m^{1/t}\right)$, valid for $t\leq\log(m/n)$, within a logarithmic factor. With $t=\Omega(\log(m/n))$, storage is $O(n\log(m/n))$, matching the information-theoretic minimum. For non-adaptive retrieval, the bound is $O\!\left(tn^{2(1-1/t)}m^{1/t}\log^{1-1/t}(m/n)\right)$: the dependence on $m$ is optimal up to logarithmic factors, while the dependence on $n$ remains at most quadratically worse than optimal. For constant $n$, both schemes achieve $O(tm^{1/t})$ storage. The constructions begin with two-query schemes. Adaptive retrieval combines expander-based routing of nonzero blocks with Bernstein–Vazirani decoding of routing labels. Non-adaptive retrieval combines a block-occupancy bit with a Deutsch–Jozsa test supported by private graph neighborhoods. Recursively compressing the memory accessed classically extends these schemes to general $t$. The constructions use fixed graphs hardwired into the retrieval circuit, without charging their description to storage. The model measures query count and stored bits, rather than total computational or circuit cost; logarithmic gaps and the non-adaptive dependence on $n$ remain unresolved.

No sign of AI-generated textAI use disclosed
The manuscript was written by the authors, with AI-assisted copy editing

Error found: The non-adaptive graph construction does not satisfy its asserted private-neighborhood property for arbitrary sets of size at most (m/m1)n, although it does satisfy the weaker property needed for the sets arising in the compression scheme. The two-probe lemmas incorrectly use log(m1/n) throughout a parameter range including m1<=n, producing zero or negative storage bounds where a truncated logarithm is required.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
13 pages, 3 figures

Related papers

Quantum oracle interrogation: getting all information for almost half the price

W. van Dam

Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.

arXiv:quant-ph/9805006•Annual Symposium on Foundations of Computer Science•Nov 27, 2002•62 citations

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2 more

In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $x \in \{-1,1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound. We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{Q}$) standard deviation of $f$ on a subcube whose free variables are exactly $T$.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.

quant-pharXiv:2511.04669•Leibniz international proceedings in informatics•Nov 7, 2025•1 citation

An optimal quantum algorithm for the oracle identification problem

Robin Kothari

In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered $γ_2$-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

arXiv:1311.7685•Leibniz international proceedings in informatics•Nov 29, 2013•35 citations

Quantum Query Advantage Requires Space

Minbo Gao, Zhengfeng Ji, Ziyi Xie

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

quant-pharXiv:2609.29497•Sep 7, 2026•1 citation

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

Hao Wang, Zhang, Chenyi, Tongyang Li

The problem of minimizing the maximum of $N$ convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring $O(Nε^{-2/3} + ε^{-8/3})$ queries to a first-order oracle to compute an $ε$-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of $\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tildeΩ(\sqrt{N}ε^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors.

arXiv:2402.12745•Feb 20, 2024•1 citation

Optimal Success Bounds for Single Query Quantum Algorithms Computing the General SUM Problem

Alexander Valtchev

In this thesis the problem of computing the sum of a string of arbitrary finite length drawn from an arbitrary finite alphabet is treated. The resource considered is the number of queries to some oracle which hides the string and gives access to each of its digits. The sum of a string is defined as adding all of the string's digits together modulo the alphabet size. \n \nClassically, this problem is straightforward as any less than a number of queries equal to the string length reveals no useful information about the sum of the string. In the quantum information setting however, things are not so clear. When the alphabet size is equal to two, the problem becomes finding the parity of a bit string. This is a seminal result in quantum computation that allows a correct answer with certainty by making only half the queries that are classically needed. As the alphabet size increases beyond two however, less is known. There is an algorithm by Meyer and Pommersheim which computes the sum in this general setting with probability of success: $\\min\\left\\lbrace\\frac{\\floor{\\frac{n}{n-q}}}{k}, 1\\right\\rbrace$ where $n$ is the string length, $k$ is the alphabet size, and $q$ is the number of queries made. This algorithm has probability of success slightly above guessing when the number of queries are half the string length, and perfect probability of success when $n-1$ queries are made. The question dealt with in this thesis is whether this algorithm is optimal for the general sum case. \n \nThe problem is expressed as a semidefinite program, given for all instances. The instance for strings of length two and algorithms making a single query is solved and a proof is given. Significant insight into the multi-query case is also provided.

•May 27, 2015•0 citations
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.
The paper studies static membership for sparse bit strings with classical storage and exact quantum retrieval: encode x∈{0,1}mx\in\{0,1\}^mx∈{0,1}m, of Hamming weight at most n≤m/2n\leq m/2n≤m/2, into sss bits so that any requested bit can be recovered using at most ttt quantum queries to the stored string. It considers both sequential, adaptive queries and parallel, non-adaptive queries.
For adaptive retrieval, it establishes sQ(m,n,t)=O ⁣(n1−1/tm1/tlog⁡1−1/t(m/n))s_Q(m,n,t)=O\!\left(n^{1-1/t}m^{1/t}\log^{1-1/t}(m/n)\right)sQ​(m,n,t)=O(n1−1/tm1/tlog1−1/t(m/n)). This approaches the existing lower bound Ω ⁣(tn1−1/tm1/t)\Omega\!\left(tn^{1-1/t}m^{1/t}\right)Ω(tn1−1/tm1/t), valid for t≤log⁡(m/n)t\leq\log(m/n)t≤log(m/n), within a logarithmic factor. With t=Ω(log⁡(m/n))t=\Omega(\log(m/n))t=Ω(log(m/n)), storage is O(nlog⁡(m/n))O(n\log(m/n))O(nlog(m/n)), matching the information-theoretic minimum. For non-adaptive retrieval, the bound is O ⁣(tn2(1−1/t)m1/tlog⁡1−1/t(m/n))O\!\left(tn^{2(1-1/t)}m^{1/t}\log^{1-1/t}(m/n)\right)O(tn2(1−1/t)m1/tlog1−1/t(m/n)): the dependence on mmm is optimal up to logarithmic factors, while the dependence on nnn remains at most quadratically worse than optimal. For constant nnn, both schemes achieve O(tm1/t)O(tm^{1/t})O(tm1/t) storage.
The constructions begin with two-query schemes. Adaptive retrieval combines expander-based routing of nonzero blocks with Bernstein–Vazirani decoding of routing labels. Non-adaptive retrieval combines a block-occupancy bit with a Deutsch–Jozsa test supported by private graph neighborhoods. Recursively compressing the memory accessed classically extends these schemes to general ttt. The constructions use fixed graphs hardwired into the retrieval circuit, without charging their description to storage. The model measures query count and stored bits, rather than total computational or circuit cost; logarithmic gaps and the non-adaptive dependence on nnn remain unresolved.
Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}nx \in \{-1,1\}^nx∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning xxx is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered γ2γ_2γ2​-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.
Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity Q=Θ~(M)Q=\widetildeΘ(M)Q=Θ(M), and randomized query complexity R=Θ(M21/20)R=Θ(M^{21/20})R=Θ(M21/20), whereas, for every fixed 0<η<1/1000<η<1/1000<η<1/100 and S≤O(M1/100−η)S\le O(M^{1/100-η})S≤O(M1/100−η), its SSS-space quantum query complexity satisfies QS=ω(M21/20)Q_S=ω(M^{21/20})QS​=ω(M21/20). Consequently, Q<R<QS, Q<R<Q_S, Q<R<QS​, so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.
The problem of minimizing the maximum of NNN convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3)O(Nε^{-2/3} + ε^{-8/3})O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an εεε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of NNN convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3)\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})O~(N​ε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3)\tildeΩ(\sqrt{N}ε^{-2/3})Ω~(N​ε−2/3) queries to a first order quantum oracle, showing that our dependence on NNN is optimal up to poly-logarithmic factors.
In this thesis the problem of computing the sum of a string of arbitrary finite length drawn from an arbitrary finite alphabet is treated. The resource considered is the number of queries to some oracle which hides the string and gives access to each of its digits. The sum of a string is defined as adding all of the string's digits together modulo the alphabet size. \n \nClassically, this problem is straightforward as any less than a number of queries equal to the string length reveals no useful information about the sum of the string. In the quantum information setting however, things are not so clear. When the alphabet size is equal to two, the problem becomes finding the parity of a bit string. This is a seminal result in quantum computation that allows a correct answer with certainty by making only half the queries that are classically needed. As the alphabet size increases beyond two however, less is known. There is an algorithm by Meyer and Pommersheim which computes the sum in this general setting with probability of success: minleftlbracefracfloorfracnn−qk,1rightrbrace\\min\\left\\lbrace\\frac{\\floor{\\frac{n}{n-q}}}{k}, 1\\right\\rbraceminleftlbracefracfloorfracnn−qk,1rightrbrace where nnn is the string length, kkk is the alphabet size, and qqq is the number of queries made. This algorithm has probability of success slightly above guessing when the number of queries are half the string length, and perfect probability of success when n−1n-1n−1 queries are made. The question dealt with in this thesis is whether this algorithm is optimal for the general sum case. \n \nThe problem is expressed as a semidefinite program, given for all instances. The instance for strings of length two and algorithms making a single query is solved and a proof is given. Significant insight into the multi-query case is also provided.