Source-linked AI summary
Optimal compression with quantum retrieval
Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan
TL;DR
The paper studies exact recovery of bits from a shorter encoding of a string with Hamming weight at most n, using bounded quantum queries. It gives compression schemes, including a two-probe adaptive scheme, and establishes a matching upper and lower bound when t = Ω(log(m/n)).
Problem
How can a string of length m and Hamming weight at most n be compressed so that any bit can be recovered exactly using at most t quantum queries?
Source: §1 · p. 1Method
A two-probe adaptive scheme splits the encoding into M1 and M2, querying M1 quantumly and then M2 classically to recover a bit.
Source: §3.1 · pp. 7–8Results
For t = Ω(log(m/n)), the upper bound is O(n log(m/n)), matching the lower bound.
Source: §1 · p. 2Takeaways & Limitations
The presented shallow quantum circuits, which measure between queries, essentially match the lower bound.
Source: Prior work and the significance of our… · p. 3
Abstract
from arXiv · showhide
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$.
1 Introduction
The paper studies zero-error quantum-query compression of sparse strings, comparing adaptive and non-adaptive retrieval. Its bounds approach lower bounds in key regimes and indicate advantages over classical schemes.
1 Introduction
- The task is to encode an m-bit string of Hamming weight at most n so any bit can be recovered without error using at most t quantum queries.The paper distinguishes sequential, adaptive probes from probes fixed in advance.Source: §1 · pp. 1–2
- For t = Ω(log(m/n)), the adaptive upper bound reduces to O(n log(m/n)), matching the lower bound.For t ≤ log(m/n), the upper bound is instead worse than the lower bound by a factor log(m/n)/t.Source: §1 · pp. 1–2
Prior work and the significance of our bounds
- Classical two-probe schemes essentially offer no better than a characteristic vector when n ≥ log m, whereas quantum two-probe schemes achieve significant compression even when n = m^(1−ϵ).Source: Prior work and the significance of our… · p. 3
1 Introduction
- The non-adaptive two-probe scheme compresses to O(n√m log(m/n)) bits, saving space over a large range of n.The paper also reports that its upper bounds have the right dependence on m, up to a logarithmic factor, while dependence on n can be worse.Source: §1 · p. 2, Prior work and the significance of our… · p. 3
Prior work and the significance of our bounds
- The presented query algorithms measure between queries, yet the paper says this shallow-circuit restriction still essentially matches the lower bound.The comparison is notable because the lower bound allows registers to remain in superposition until the final measurement.Source: Prior work and the significance of our… · p. 3
AI statement
The authors report using AI systems for mathematical exploration, proof development, literature searches, and copy editing. They distinguish AI-assisted work from author-supplied ideas and retain responsibility for the manuscript.
AI statement
- The authors used ChatGPT and Claude for mathematical exploration, proof development, literature searches, and copy editing.Figures were generated by an AI agent from the authors’ handwritten drawings.Source: AI statement · p. 3
- The authors say they had obtained an O(n√m) two-probe adaptive scheme and a non-adaptive scheme with optimal m^(1/t) dependence before consulting AI systems.Source: AI statement · p. 3
- The authors state that they retain full responsibility for the manuscript’s correctness, originality, attribution, and integrity.Source: AI statement · p. 4
2 Preliminaries
The preliminaries define compression as storing sparse strings for exact quantum retrieval, with adaptive and non-adaptive query models. They also establish expander-graph properties used to obtain matchings for sparse vertex sets.
2 Preliminaries
- An (m, n, s, t)-compression scheme stores each input in B(m, n) as s bits and uses a quantum circuit with at most t oracle queries to retrieve an indexed bit exactly.The circuit includes an index register, index-controlled unitaries, and a final measurement; the paper describes proof algorithms informally rather than presenting circuits explicitly.Source: §2 · p. 4
- Non-adaptive retrieval applies the oracle queries in parallel, while adaptive retrieval may use an earlier oracle outcome to choose a later query.The query circuit measures at the end; the informal algorithm descriptions are stated to be representable as formal quantum circuits.Source: §2 · p. 4
2.1 Expander graphs
- The expander graphs used in query algorithms are hardwired into the circuit, independent of the input, and are not stored in the compressed string.The section also states existence of a graph family with range [10nd] and power-of-two degree d = O(n max{log(k/n), 1}).Source: §2.1 · pp. 5–6
- For every A ⊆ [k] of size at most n, a bipartite graph with d = O(max{log(k/n), 1}) can have |Γ_G(A)| ≥ |A|, yielding a matching that saturates A.The matching consequence is stated via Hall’s theorem.Source: §2.1 · p. 5
3 Two-probe schemes
The two-probe schemes use Bernstein–Vazirani for adaptive extraction and Deutsch–Jozsa for non-adaptive discrimination. The adaptive scheme stores nonzero blocks with a quantum-readable map; the non-adaptive scheme uses a block flag and a graph-based encoding.
3.1 The adaptive two-probe scheme
- For fixed m1, Lemma 5 uses 2m1(n+1) bits for M1 and (m/m1)n bits for M2, with one quantum probe followed by one classical probe.M1 records where each nonzero block is stored, and M2 holds the nonzero blocks.Source: §3.1 · p. 7
- Setting m1=√m yields an adaptive two-probe compression scheme using O(n√m) bits.The scheme first probes M1 quantumly, then reads the selected bit from M2 classically.Source: §3.1 · p. 7
- An expander matching routes nonzero blocks among 2n slots, giving |M1|=O(m1 log(m1/n)) and |M2|=2n(m/m1).The query uses one quantum probe into M1 followed by a classical probe into M2.Source: §3.1 · pp. 7–8
3.2 The non-adaptive two-probe scheme
- The non-adaptive scheme uses a classical block-presence flag in M1 and a graph-based encoding in M2, queried once each.The graph assigns disjoint neighbor sets to relevant indices; the Deutsch–Jozsa test distinguishes an all-zero neighborhood from one with half its labels zero.Source: §3.2 · pp. 8–9
- For fixed m1, the non-adaptive scheme uses |M1|=m1 and |M2|=O(n^2(m/m1) log(m1/n)).The query makes one classical probe into M1 followed by one quantum probe into M2.Source: §3.2 · p. 9
4 The general schemes via recursion
The general schemes extend the two-probe constructions recursively. For t>2, they replace the classical bit-reading probe with a recursive (t−1)-probe scheme, preserving whether the original scheme is adaptive or non-adaptive.
4 The general schemes via recursion
- For t>2, the schemes replace the classical bit-reading probe with a recursive (t−1)-probe scheme, retaining the original adaptive or non-adaptive query structure.The recursive construction lifts either two-probe scheme to every t≥2.Source: §4 · p. 10
- The adaptive construction recursively compresses M2, whose original two-probe scheme uses a quantum probe into M1 and a classical probe into M2.The proof applies the adaptive scheme from Theorem 6.Source: §4 · p. 10
- For the non-adaptive construction, the proof applies Theorem 7 and combines the recurrence with the upper bound sQN(m,n,t)≤m to obtain Theorem 2's bound.The stated upper bound also covers the base case t=1.Source: §4 · p. 11