Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 44 min ago
PreprintarXiv licencearXiv

Optimal compression with quantum retrieval

  • Shyam Dhamapurkar
  • Mohit Garg
  • Manaswi Paraashar
  • Jaikumar Radhakrishnan
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Optimal low-rank compression of quantum dynamics
    Hugo Mackay, Donghoon Kim, Tan Van Vu +1
    arXivPreprintCC BY 4.0Full textMathematical physicsCondensed matterarXiv
  2. An exact compression-and-lifting procedure and D-optimal designs of orders 198 and 170
    Stelios D. Georgiou, Stella Stylianou
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Positive Cubature Compression and Optimal Hyperinterpolation Stability on a Conic Surface
    Congpei An, Yan Ge
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Quantum Private Information Retrieval on Forests
    Mohamed Nomeir, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  5. Classical Communication Helps Single-Shot Quantum Compression
    Omri Farber, Gilad Gour
    arXivPreprintarXiv licenceFull textMathematical physicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{dhamapurkar2026optimal,
  title = {{Optimal compression with quantum retrieval}},
  author = {Shyam Dhamapurkar and Mohit Garg and Manaswi Paraashar and Jaikumar Radhakrishnan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06702},
  eprint = {2610.06702},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06702},
}
RIS
TY  - UNPB
TI  - Optimal compression with quantum retrieval
AU  - Shyam Dhamapurkar
AU  - Mohit Garg
AU  - Manaswi Paraashar
AU  - Jaikumar Radhakrishnan
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06702
UR  - https://arxiv.org/abs/2610.06702
AB  - 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 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.
ER  -