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.
We consider the following data compression problem. Given a string x∈{0,1}m of Hamming weight at most n, compress it into a shorter string y∈{0,1}s so that any bit xi 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.
The paper studies static membership for sparse bit strings with classical storage and exact quantum retrieval: encode x∈{0,1}m, of Hamming weight at most n≤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 sQ(m,n,t)=O(n1−1/tm1/tlog1−1/t(m/n)). This approaches the existing lower bound Ω(tn1−1/tm1/t), valid for t≤log(m/n), within a logarithmic factor. With t=Ω(log(m/n)), storage is O(nlog(m/n)), matching the information-theoretic minimum. For non-adaptive retrieval, the bound is O(tn2(1−1/t)m1/tlog1−1/t(m/n)): 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(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 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.
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}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(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when 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→R the ratio of the maximum value of f to the maximum (over T∈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.
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.
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), and randomized query complexity R=Θ(M21/20), whereas, for every fixed 0<η<1/100 and S≤O(M1/100−η), its S-space quantum query complexity satisfies QS=ω(M21/20). Consequently, 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 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 O~(Nε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3) queries to a first order quantum oracle, showing that our dependence on N 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 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.