{"id":"arxiv/2610.06702","url":"https://arxiv.org/abs/2610.06702","tags":["quant-ph","cs.DS","cs.IR","cs.IT"],"score":0,"title":"Optimal compression with quantum retrieval","domain":"quant-ph","source":"arxiv","authors":["Shyam Dhamapurkar","Mohit Garg","Manaswi Paraashar","Jaikumar Radhakrishnan"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}