DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.118

The Compressed Oracle Is A Worthy (Multiplicative) Adversary

Authors: Stacey Jeffery and Sebastian Zur

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The compressed oracle technique, introduced in the context of quantum cryptanalysis, is the latest method for proving quantum query lower bounds, and has had an impressive number of applications since its introduction, due in part to the ease of importing classical lower bound intuition into the quantum setting via this method. Previously, the main quantum query lower bound methods were the polynomial method, the adversary method, and the multiplicative adversary method, and their relative powers were well understood. In this work, we situate the compressed oracle technique within this established landscape, by showing that it is a special case of the multiplicative adversary method. To accomplish this, we introduce a simplified restriction of the multiplicative adversary method, the MLADV method, that remains powerful enough to capture the polynomial method and exhibit a strong direct product theorem, but is much simpler to reason about. We show that the compressed oracle technique is also captured by the MLADV method. This might make the MLADV method a promising direction in the current quest to extend the compressed oracle technique to non-product distributions.

Cite as

Stacey Jeffery and Sebastian Zur. The Compressed Oracle Is A Worthy (Multiplicative) Adversary. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 118:1-118:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.ICALP.2026.118,
  author =	{Jeffery, Stacey and Zur, Sebastian},
  title =	{{The Compressed Oracle Is A Worthy (Multiplicative) Adversary}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{118:1--118:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.118},
  URN =		{urn:nbn:de:0030-drops-265077},
  doi =		{10.4230/LIPIcs.ICALP.2026.118},
  annote =	{Keywords: Quantum query complexity, compressed oracle, adversary method}
}

Search Results

Documents authored by Zur, Sebastian

The Compressed Oracle Is A Worthy (Multiplicative) Adversary

Abstract

Cite as

Thanks for your feedback!

Could not send message