REVIEW 3 major objections 5 minor 33 references
The Compressed Oracle is a Worthy (Multiplicative) Adversary
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The compressed oracle is a multiplicative adversary, within a factor of six.
desk verdict Solid, honest structural paper: compressed oracle is indeed a special case of a useful new restricted multiplicative adversary method, and the main theorem is sound despite a few presentation hiccups. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrier of the argument is the multiplicative ladder adversary (MLA) matrix: a positive-definite adversary matrix of the form $\Gamma = \sum_{i=0}^{\ell} \kappa^i \Lambda_i$ whose eigenspaces commute with the projectors $\Pi_{\le t}$ onto the reachable subspaces $\mathrm{Space}_t(\delta)$ and satisfy the ladder condition $\|\Lambda_{i'} O_{x,y} \Lambda_i\| = 0$ whenever $|i'-i| > 1$, so one query moves the state at most one rung. The matching is made possible by Lemma 4.1, which identifies $\mathrm{Space}_t(\delta)$—the span of normalized superpositions over functions matching $t$ specified input-output pairs—with the support reachable by any $t$-query algorithm, so that compressed-oracle database projections become eigenspace projections of an MLA matrix. This identity converts the compressed oracle’s database-size progress into the multiplicative adversary’s eigenvalue progress and drives the factor-6 reduction.
What would settle it
Take a non-product distribution over functions, such as a distribution with a global parity constraint, run a two-query algorithm that reads two function values in superposition, and compute the reduced input state; if any component of that state is not a linear combination of states each supported on functions agreeing with two fixed input-output pairs, then Lemma 4.1 is false and the reduction collapses.
Extended reading notes
Core claim
The central claim, Theorem 5.1, is that for any property $P$ of $k$ input-output pairs, the compressed-oracle lower bound satisfies $\mathrm{COMP}_{\epsilon}^{\mathrm{Uniform}}(F) \le 6\cdot \mathrm{MLADV}_{\epsilon,2k/M}^{\mathrm{Uniform}}(F)$: every adversary that the compressed oracle rules out is also ruled out by an MLA adversary whose bad eigenspace is the projection onto databases satisfying $P$. The same restricted method is shown to dominate the polynomial method, with $\mathrm{gdeg}_{\epsilon}(F) \le 4\cdot \mathrm{MLADV}_{\epsilon}(F)$, and to contain the permutation-inversion bounds of Section 8 as a special case; moreover, MLA matrices are closed under tensor powers, which yields a strong direct product theorem. In the paper’s telling, a generalized compressed oracle for arbitrary input distributions must therefore live somewhere between the compressed oracle and the full MLADV method.
Load-bearing premise
The argument rests on Lemma 4.1, the claim that for every input distribution the states reachable with $t$ queries are exactly spanned by normalized superpositions over functions matching $t$ specified input-output pairs; if correlated distributions break this equality, the ladder projector identities and the main reduction fail.
Editorial extensions
If this is right
- If Theorem 5.1 is right, no compressed-oracle lower bound can exceed the corresponding multiplicative adversary bound by more than a constant factor, so the compressed oracle introduces no fundamentally new lower-bound power in the uniform, product case.
- The polynomial-method containment of Theorem 7.6 means MLADV is at least as strong as approximate-degree lower bounds, so the ladder restriction does not buy simplicity at the cost of the polynomial method.
- Because MLA matrices are closed under tensor powers, the method inherits a strong direct product theorem, so hardness of $k$ independent instances degrades exponentially without extra work.
- Since the permutation-inversion bounds of Section 8 assemble into an MLA matrix, any extension of the compressed oracle to non-product distributions must produce bounds that fit the MLA template, giving a concrete target for that search.
Reading between the lines
- The factor 6 is an artifact of the reduction’s constants, and a tighter reduction might show the true gap is close to 1; comparing the two bounds on a family such as collision or multi-collision search would test this empirically.
- If every MLA matrix can be realized as a compressed-oracle projection for some input distribution, then MLADV is not merely an upper bound on COMP but its exact closure, making “extend the compressed oracle” equivalent to “solve the MLA matrix construction problem.”
- The ladder condition suggests a design rule for new lower bounds: choose an adversary matrix whose eigenspaces are indexed by a query-counting statistic; problems with one such statistic are natural compressed-oracle targets, while problems needing several interlocking statistics may require the full multiplicative adversary.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the multiplicative ladder adversary (MLADV) method, a restricted form of the multiplicative adversary method, and proves that the compressed oracle technique is a special case of MLADV up to a factor of 6. The main reduction is formalized in Theorem 5.1, where an explicit MLA matrix is constructed from the compressed oracle projections and the constants are tracked through Claims 5.2 and 5.3 and Lemma 5.4. The paper also shows that MLADV satisfies a strong direct product theorem (Section 6), contains the polynomial method up to a factor of 4 (Section 7), and captures the Rosmanis permutation inversion bounds (Section 8). The central claim is that every compressed oracle lower bound is, up to a factor 6, an MLADV lower bound of a restricted ladder type, thereby situating the compressed oracle technique in the existing landscape of quantum query lower bound methods.
Significance. If the main reduction is correct, it provides the first explicit structural relationship between the compressed oracle technique and the multiplicative adversary method, with an explicit factor and an explicit adversary matrix. This is a useful conceptual contribution: it suggests a route toward extending compressed oracle arguments beyond product distributions, and it shows that the MLADV restriction retains enough power to capture both the polynomial method and a strong direct product theorem. The proof of Theorem 5.1 is largely explicit and tracks constants, and the paper is honest about the regimes where its bounds apply. The main caveat is that several proof passages are presented in a garbled or incomplete form, and these passages are used in the central argument.
major comments (3)
- [Section 4.2, Fact 4.5] The displayed proof of Fact 4.5 is not comprehensible as written: the equality "Π≤t+1Ox,yΠt = Ox,yΠt⊥Ox,yΠ≤t−1 = Π≤tOx,yΠ≤t−1" around Eq. (24) does not form a valid derivation, and the claimed orthogonality of images and coimages is not justified. This fact is load-bearing, since Theorem 5.1 uses monotonicity of the ladder norms to replace the sum over T by the sum over 6T, and Section 6 uses it again. The statement is true and a clean proof is available: using (23) one can write a_t = ||Λ_i O Π≤t−1 Λ_{i−1}||, then use the commutation of the MLA spectral projectors with Π≤t−1 to obtain ||Λ_i O Λ_{i−1} Π≤t−1||, which is nondecreasing as Π≤t−1 expands. Please replace the current proof with this or an equally explicit argument.
- [Section 4.1, Lemma 4.1] The proof of the first bullet of Lemma 4.1 does not establish the statement as written. The proof constructs, for each fixed tuple (x1,...,xt) and (y1,...,yt), a separate t-query algorithm A whose reduced state contains the corresponding vector |v_y1...yt_x1...xt>. This only shows that each basis vector of Space_t(δ) is reachable by some algorithm, not that there exists a single t-query algorithm A with Space_t(δ) ⊆ span(supp ρ_t(A,δ)). Since Eq. (12) is stated as a consequence of Lemma 4.1 and is later used in Claim 5.2, please either provide a correct construction of one algorithm that reaches all of Space_t(δ) (for example, by querying all tuples in superposition with a sufficiently large workspace), or restate the lemma so that the first bullet is not needed for Eq. (12) and prove Eq. (12) directly from the definition of Space_t(Uniform) and Comp.
- [Section 6, Eqs. (37)-(40)] The notation and derivation in the strong direct product theorem need clarification. The projection Π'≤t is first displayed as a sum involving Π≤t1⊗...⊗Π≤tk with t1+...+tk=t, but in Eq. (35) it is used as if the factors are the increment projections Π_{t_i} = Π≤t_i − Π≤t_i−1, and the two conventions are not the same. In addition, the symbol "√ck" in Eqs. (37) and (40) is ambiguous: if it is read as c^{k/2}, the step from (39) to (40) does not follow, because from c^{k/2} − η^{k/5} ≥ A^{k/10} one only obtains a square lower bound of A^{k/5}, not A^{k/10}. If it is intended to mean √(1−c^k), the notation should be corrected and the derivation should be written out. Please disambiguate the projections and give a complete derivation of (40).
minor comments (5)
- [Section 5, Lemma 5.4] The proof of Lemma 5.4 uses the set D{z} without formally defining whether entries outside the k specified pairs are arbitrary or restricted to ⊥; since the compressed database distinguishes ⊥ from the value 0, this convention should be stated explicitly at the start of the proof.
- [Section 8, Eq. (49)] The operators bΠ1,t and bΠ0,t are introduced through the spaces B_i and A_i, but the direct-sum decomposition behind them is only implicit; a sentence defining the projectors explicitly, or pointing to the exact equations in [Ros21], would improve readability.
- [Section 7, proof of Theorem 7.6] The displayed quantity "1 + κ−1√κ" appears several times; it should be written as 1 + (κ−1)/√κ to avoid confusion with κ^{-1}√κ, which would make the subsequent logarithm inequalities impossible to follow.
- [References] The reference [ACMT25] lists arXiv numbers 2504.16887 and 2505.168874; one of these appears to be a typo and should be corrected.
- [Section 6, Theorem 6.1] The theorem states k>361 while the proof says k≥361; please make the threshold consistent, and verify that the numerical inequality k(10e)^{k/10} ≤ 2^{k/2} holds at the stated threshold.
Circularity Check
No circularity: the compressed-oracle-to-MLADV reduction is explicit and self-contained; self-citations are background only.
full rationale
The paper's central claim is a reducibility theorem, not a prediction from fitted inputs. In Theorem 5.1, the MLA matrix is explicitly constructed from the compressed-oracle projections (Lambda_1 = Pi_{1,N}, Lambda_0 = I - Lambda_1 in Claim 5.2 and Claim 5.3), and the key norm identity is proved directly: ||Lambda_1 Pi_{<=t} O_{x,y} Pi_{<=t-1} Lambda_0|| = ||Pi_{1,t} O_{x,y} Pi_{0,t-1}||. This shows that every compressed-oracle progress term is, by construction, an admissible MLA progress term; that is exactly a reduction, not an equation of the target with its own input. The factor-6 conversion is justified by Fact 4.5, whose monotonicity statement is independent of the main inequality and is argued from the nested-space property (23). The polynomial-method reduction (Theorem 7.6) imports Lemma 16 of MR15 and the permutation-inversion section imports Claims 10-12 of Rosmanis; these are external results, not self-citations, and the paper supplies its own verification that the relevant matrices are MLA matrices. The only self-references (CMSZ19, DFMS22) are contextual applications of the compressed oracle and are not load-bearing for the reductions. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no quantity is defined in terms of the result it is used to prove. The derivation chain is therefore self-contained with respect to circularity concerns.
Assumptions & free parameters
free parameters (2)
- kappa (MLA eigenvalue spacing) =
1 + (e-1)/D^2 in Theorem 5.1; 2^{4(n-log eps)} in Theorem 7.6
- eta (bad-subspace threshold) =
2k/M in Theorem 5.1
assumptions (6)
- standard math Multiplicative adversary framework, Theorem 3.3 and Corollary 3.4, imported from Spalek 2008 and AMRR11 2011.
- domain assumption Compressed oracle support fact, Fact 3.6, and the CFHL21 lower bound, Theorem 3.7.
- domain assumption Exact reachable subspace characterization, Lemma 4.1, for arbitrary input distributions delta.
- standard math Output condition via Hadamard product fidelity, Fact 7.4, communicated by Roland and used as Corollary 7.5.
- standard math Lemma 16 of MR15, stated as Fact 7.7, giving the lower bound on the progress measure for the polynomial method matrix.
- domain assumption Claims 10 to 12 from Rosmanis 2021 bounding the permutation projector norms.
Cite this review
Pith. "Pith review of The Compressed Oracle is a Worthy (Multiplicative) Adversary." pith.science (2026). https://pith.science/paper/MDVZRTAV
@misc{pith2026250907876,
author = {Pith},
title = {Pith review of: The Compressed Oracle is a Worthy (Multiplicative) Adversary},
year = {2026},
howpublished = {\url{https://pith.science/paper/MDVZRTAV}},
note = {Machine review of arXiv:2509.07876}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In 48th , pages 863--876, 2016. arXiv:1511.01937
arXiv 2016
-
[2]
The Sponge is Quantum Indifferentiable
Gorjan Alagic, Joseph Carolan, Christian Majenz, and Saliha Tokat. The sponge is quantum indifferentiable. arXiv preprint arXiv:2504.16887 , 2025. arXiv:2505.16887
work page Pith review arXiv 2025
- [3]
-
[4]
Polynomial degree vs. quantum query complexity
Andris Ambainis. Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences , 72(2):220--238, 2006. arXiv:quant-ph/0305028
work page Pith review arXiv 2006
-
[5]
Andris Ambainis. A new quantum lower bound method, with an application to a strong direct product theorem for quantum search. Theory of Computing , 6(1):1--25, 2010. arXiv:quant-ph/0508200
work page Pith review arXiv 2010
-
[6]
Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Lo\"ick Magnin, Martin Roetteler, and J \'e r \'e mie Roland. Symmetry-assisted adversaries for quantum state generation. In 2011 IEEE 26th Annual Conference on Computational Complexity , pages 167--177. IEEE, 2011. arXiv:1012.2112
arXiv 2011
-
[7]
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. , 51(4):595--605, 2004. arXiv:quant-ph/0112086
arXiv 2004
-
[8]
Andris Ambainis, Robert S palek, and Ronald de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. In Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing , pages 618--633, 2006. arXiv:quant-ph/0511200
work page Pith review arXiv 2006
Show all 33 references
-
[9]
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald Wolf d e Wolf. Quantum lower bounds by polynomials. , 48(4):778--797, 2001. Earlier version in FOCS'98. arXiv:quant-ph/9802049
2001 arXiv
-
[10]
Sponge functions
Guido Bertoni, Joan Daemen, Micha \"e l Peeters, and Gilles Van Assche. Sponge functions. In ECRYPT hash workshop , number 9, 2007
2007
-
[11]
A direct reduction from the polynomial to the adversary method
Aleksandrs Belovs. A direct reduction from the polynomial to the adversary method. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography , 2024. arXiv:2301.10317
2024 arXiv
-
[12]
Adversary lower bounds for the collision and the set equality problems
Aleksandrs Belovs and Ansis Rosmanis. Adversary lower bounds for the collision and the set equality problems. Quantum Information and Computation , 2017. arXiv:1310.5185
2017 arXiv
-
[13]
A lower bound on the quantum query complexity of read-once functions
Howard Barnum and Michael Saks. A lower bound on the quantum query complexity of read-once functions. Journal of Computer and System Sciences , 69(2):244--258, 2004. arXiv:quant-ph/0201007
2004 arXiv
-
[14]
Quantum verification of matrix products
Harry Buhrman and Robert S palek. Quantum verification of matrix products. In 17th , pages 880--889, 2006. arXiv:quant-ph/0409035
2006 arXiv
-
[15]
On the compressed-oracle technique, and post-quantum security of proofs of sequential work
Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work. In Advances in Cryptology--EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptogra...
2021
-
[16]
Quantum lazy sampling and game-playing proofs for quantum indifferentiability
Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur. Quantum lazy sampling and game-playing proofs for quantum indifferentiability. arXiv preprint arXiv:1904.11477 , 2019. arXiv:1904.11477
1904 arXiv
-
[17]
Online-extractability in the quantum random-oracle model
Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Online-extractability in the quantum random-oracle model. In Advances in Cryptology--EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, No...
2022
-
[18]
Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter H yer, and Mehdi Mhalla. Quantum query complexity of some graph problems. , 35(6):1310--1328, 2006. Earlier version in ICALP'04. arXiv:quant-ph/0401091
2006 arXiv
-
[19]
The quantum query complexity of algebraic properties
Sebastian D \"o rn and Thomas Thierauf. The quantum query complexity of algebraic properties. In Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings 16 , pages 250--260. Springer, 2007. arXiv:0705.1446
2007 arXiv
-
[20]
o velmanns, Andreas H \
Alex B Grilo, Kathrin H \"o velmanns, Andreas H \"u lsing, and Christian Majenz. Tight adaptive reprogramming in the qrom. In Advances in Cryptology--ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, ...
2021 arXiv
-
[21]
Negative weights make adversaries stronger
Peter H yer, Troy Lee, and Robert S palek. Negative weights make adversaries stronger. In 39th , pages 526--535, 2007. arXiv:quant-ph/0611054
2007 arXiv
-
[22]
Quantum time--space tradeoff for finding multiple collision pairs
Yassine Hamoudi and Fr \'e d \'e ric Magniez. Quantum time--space tradeoff for finding multiple collision pairs. ACM Transactions on Computation Theory , 15(1-2):1--22, 2023. arXiv:2002.08944
2023 arXiv
-
[23]
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
Hartmut Klauck, Robert S palek, and Ronald De Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing , 36(5):1472--1493, 2007. arXiv:quant-ph/0402123
2007 arXiv
-
[24]
A strong direct product theorem for quantum query complexity
Troy Lee and J \'e r \'e mie Roland. A strong direct product theorem for quantum query complexity. computational complexity , 22:429--462, 2013. arXiv:1104.4468
2013 arXiv
-
[25]
On finding quantum multi-collisions
Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Advances in Cryptology--EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19--23, 2019, Proceedings, Part III 38 , pages ...
2019
-
[26]
Revisiting post-quantum fiat-shamir
Qipeng Liu and Mark Zhandry. Revisiting post-quantum fiat-shamir. In Advances in Cryptology--CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2019, Proceedings, Part II 39 , pages 326--355. Springer, 2019. 2019/262
2019
-
[27]
Explicit relation between all lower bound techniques for quantum query complexity
Lo \" ck Magnin and J \'e r \'e mie Roland. Explicit relation between all lower bound techniques for quantum query complexity. International Journal of Quantum Information , 13(04):1350059, 2015. arXiv:1209.2713
2015 arXiv
-
[28]
Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Ben W Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 544--551. IEEE, 2009. arXiv:0904.2759
2009 arXiv
-
[29]
Tight bounds for inverting permutations via compressed oracle arguments
Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv preprint arXiv:2103.08975 , 2021. arXiv:2103.08975
2021 arXiv
-
[30]
Strong direct product theorems for quantum communication and query complexity
Alexander A Sherstov. Strong direct product theorems for quantum communication and query complexity. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 41--50, 2011. arXiv:1011.4935
2011 arXiv
-
[31]
The multiplicative quantum adversary
Robert S palek. The multiplicative quantum adversary. In 2008 23rd Annual IEEE Conference on Computational Complexity , pages 237--248. IEEE, 2008. arXiv:quant-ph/0703237
2008 arXiv
-
[32]
On the power of ambainis lower bounds
Shengyu Zhang. On the power of ambainis lower bounds. Theoretical Computer Science , 339(2-3):241--256, 2005. arXiv:quant-ph/0311060
2005 arXiv
-
[33]
How to record quantum queries, and applications to quantum indifferentiability
Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Annual International Cryptology Conference , pages 239--268. Springer, 2019. 2018/276
2019
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.