Pith. sign in

REVIEW 2 major objections 1 minor 16 references

Quantum Advantage in Tolerant Junta Testing

T0 review · 2 major / 1 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Tolerant k-junta testing admits poly(k) quantum queries but requires k^Ω(log k) classical queries near distance 1/2.

desk verdict This paper claims the first super-polynomial quantum advantage for tolerant junta testing but the new classical lower bound distribution may not satisfy both closeness and hardness at once. read the letter →

arxiv 2606.23194 v1 pith:LAXYUFWH submitted 2026-06-22 cs.CC quant-ph

Avishay Tal , Weiqiang Yuan This is my paper · ORCID
classification cs.CCquant-ph
keywords tolerantjuntatestingquantumquerycomplexityclassicallowerboundspropertyerror-correctingcodesBooleanfunctionsadaptivealgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a superpolynomial quantum advantage for tolerant k-junta testing in the adaptive query model. For parameters such as ε1 = 1/2 - 1/k and ε2 = 1/2 - 1/(2k²), a quantum algorithm distinguishes whether a Boolean function is ε1-close to some k-junta or ε2-far from all k-juntas using only polynomially many queries in k. Any classical algorithm needs at least k raised to Ω(log k) queries. The quantum side adapts an existing tester; the classical lower bound uses a new distribution of yes-instances that plants an approximate junta via an error-correcting code inside random subcubes.

What carries the argument

The planted approximate-junta distribution on random k coordinates, where an error-correcting code inside each subcube forces identical random bits on codewords.

What would settle it

Exhibiting a classical algorithm that distinguishes the planted yes-distribution from the no-distribution using o(k^Ω(log k)) queries would falsify the lower bound.

Watch

Extended reading notes

Core claim

Within a parameter regime close to 1/2, tolerant k-junta testing can be solved using poly(k) quantum queries, whereas any classical algorithm requires at least k^Ω(log k) queries. The quantum tester is adapted from prior non-adaptive work. The classical lower bound is shown by introducing a distribution over yes-instances: k random coordinates are chosen, and inside each of the 2^{n-k} subcubes the function values are random except on an error-correcting code where they are set to the same random bit; this distribution lies at most ε1 from a k-junta yet remains indistinguishable from no-instances by classical algorithms with k^{o(log k)} queries.

Load-bearing premise

The new planted distribution is both ε1-close to some k-junta and indistinguishable from far-from-junta functions by any classical algorithm using only k^{o(log k)} queries.

Editorial extensions

If this is right

  • Quantum query algorithms achieve polynomial dependence on k for tolerant junta testing near distance 1/2.
  • Classical query algorithms require superpolynomial dependence on k for the same task.
  • The separation holds in the adaptive setting.
  • The result applies for a range of parameters close to 1/2, including the stated ε1 and ε2 values.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The planting technique using error-correcting codes may extend to lower bounds for other tolerant property testing problems.
  • Similar quantum-classical gaps could appear in tolerant versions of other junta-related or dictatorship testing tasks.
  • Non-adaptive quantum testers might achieve the same poly(k) bound under the same parameters.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 1 minor

Summary. The paper claims the first super-polynomial quantum advantage for tolerant k-junta testing in the adaptive setting. For parameters such as ε₁ = 1/2 − 1/k and ε₂ = 1/2 − 1/(2k²), a poly(k)-query quantum algorithm (adapted from Bao et al., SOSA 2026) distinguishes ε₁-close k-juntas from ε₂-far functions, while any classical algorithm requires k^Ω(log k) queries. The classical lower bound is proved via a new hard distribution of yes-instances obtained by randomly selecting k coordinates and, within each subcube, planting identical random bits on the positions of an error-correcting code while leaving the remaining positions random.

Significance. If the separation holds, the result would establish the first super-polynomial quantum-classical gap for tolerant junta testing, a natural extension of prior work on junta testing and quantum property testing. The new planted distribution for the classical lower bound is a technical contribution that may be of independent interest.

major comments (2)
  1. [Abstract (hard distribution paragraph)] Abstract (description of the hard distribution): the yes-instance distribution plants an ECC inside each of the 2^k subcubes to achieve distance at most ε₁ = 1/2 − 1/k to some k-junta. This requires the planted set to have size Ω(2^{n−k}/k) per subcube. The same construction is asserted to remain indistinguishable from no-instances under k^{o(log k)} classical queries, which the text indicates relies on the code having positive minimum distance. By the Singleton bound, any code of that cardinality has minimum distance O(log k); it is unclear whether this suffices for the indistinguishability argument or whether the two requirements are simultaneously satisfiable for the stated parameter regime.
  2. [Abstract (quantum tester paragraph)] Abstract and quantum-tester paragraph: the claim that the non-adaptive quantum tester of Bao et al. works for ε₁ = 1/2 − 1/k and ε₂ = 1/2 − 1/(2k²) is supported only by the statement that the analysis is “slightly adapted.” No explicit error-probability calculation or verification that the tester’s acceptance/rejection thresholds remain separated under these parameters is provided in the manuscript.
minor comments (1)
  1. [Abstract] The abstract is dense; expanding the one-sentence description of the planted distribution into a short paragraph would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments on our manuscript. The points raised highlight areas where additional clarification will strengthen the presentation. We address each major comment below and commit to revisions that provide the requested details without altering the core claims.

read point-by-point responses

  1. Referee: [Abstract (hard distribution paragraph)] Abstract (description of the hard distribution): the yes-instance distribution plants an ECC inside each of the 2^k subcubes to achieve distance at most ε₁ = 1/2 − 1/k to some k-junta. This requires the planted set to have size Ω(2^{n−k}/k) per subcube. The same construction is asserted to remain indistinguishable from no-instances under k^{o(log k)} classical queries, which the text indicates relies on the code having positive minimum distance. By the Singleton bound, any code of that cardinality has minimum distance O(log k); it is unclear whether this suffices for the indistinguishability argument or whether the two requirements are simultaneously satisfiable for the stated parameter regime.

    Authors: The construction selects an error-correcting code of cardinality Ω(2^{n-k}/k) on the (n-k)-bit subcubes, which by the Singleton bound admits minimum distance O(log k). This distance is positive (in fact, growing with k) and is the only property used in the indistinguishability argument: the planted bits are constant on each codeword but independent across distinct codewords, ensuring the distribution remains statistically close to a k-junta while any classical algorithm with k^{o(log k)} queries cannot detect the planted structure. Because the argument requires only d ≥ 1 and the Singleton bound permits d = Θ(log k) > 0 for the stated cardinality, the two requirements are simultaneously satisfiable. In the revision we will add an explicit paragraph stating the code parameters, confirming compatibility with the Singleton bound, and reiterating that the lower-bound proof invokes only positivity of the minimum distance. revision: yes

  2. Referee: [Abstract (quantum tester paragraph)] Abstract and quantum-tester paragraph: the claim that the non-adaptive quantum tester of Bao et al. works for ε₁ = 1/2 − 1/k and ε₂ = 1/2 − 1/(2k²) is supported only by the statement that the analysis is “slightly adapted.” No explicit error-probability calculation or verification that the tester’s acceptance/rejection thresholds remain separated under these parameters is provided in the manuscript.

    Authors: We agree that the adaptation of Bao et al.’s analysis should be made fully explicit. The quantum tester’s acceptance probability for ε₁-close functions and rejection probability for ε₂-far functions remain separated under the chosen parameters because the gap between 1/2 − 1/k and 1/2 − 1/(2k²) is still large enough relative to the tester’s concentration bounds; the thresholds can be set at the midpoint of the two regimes with error probability exponentially small in the number of queries. In the revised manuscript we will insert a short subsection (or appendix paragraph) that reproduces the relevant error-probability calculation from Bao et al., substitutes the new (ε₁, ε₂) values, and verifies that the acceptance/rejection thresholds stay separated by a constant margin. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation relies on independent external tester and novel distribution

full rationale

The paper's quantum upper bound adapts an analysis from the independent Bao et al. (SOSA 2026) work, while the classical lower bound is built from a newly introduced hard distribution of yes-instances using random coordinate selection plus error-correcting code planting inside subcubes. No equations reduce any claimed prediction or separation to a quantity defined by fitting, self-definition, or a load-bearing self-citation chain. The cited prior works (Bao et al., Chen and Patel) are external and do not create a self-referential loop within this manuscript. The construction is presented as a direct argument rather than a renaming or ansatz imported via self-citation.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The result rests on standard definitions of the black-box query model, Boolean function distance, and junta property; no free parameters, ad-hoc constants, or new postulated entities are introduced.

assumptions (1)
  • standard math The standard black-box query model for Boolean functions and the definition of distance to the class of k-juntas are taken as given.
    The entire separation is stated inside this model; the abstract invokes no non-standard axioms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Advantage in Tolerant Junta Testing." pith.science (2026). https://pith.science/paper/LAXYUFWH

@misc{pith2026260623194,
  author       = {Pith},
  title        = {Pith review of: Quantum Advantage in Tolerant Junta Testing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAXYUFWH}},
  note         = {Machine review of arXiv:2606.23194}
}
abstract

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{\Omega(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, \epsilon_1, \epsilon_2)$, with $0\le \epsilon_1<\epsilon_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $\epsilon_1$-close to some $k$-junta or $\epsilon_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $\epsilon_1 = 1/2-1/k$ and $\epsilon_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $\epsilon_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [1]

    doi:10.1137/1.9781611974331.CH65

    Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974331.CH65. [AS07] Alp Atıcı and Rocco A Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6(5):323–348, 2007.doi:10.1007/s11128-007-0061-6. [BCE+19] Eric Blais, Cl´ ement L. Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing...

    work page doi:10.1137/1.9781611974331.ch65 2007

  2. [2]

    [CSUU08] R

    [BHKT24] Guy Blanc, Alexandre Hayderi, Caleb Koch, and Li-Yang Tan. The sample complexity of smooth boosting and the tightness of the hardcore theorem. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1431–1450, 2024.doi:10.1109/FOCS61266.2024.00092. 15 [BKT20] Mark Bun, Robin Kothari, and Justin Thaler. The polynomial me...

    work page doi:10.1109/focs61266.2024.00092 2024

  3. [3]

    Springer Berlin Heidelberg.doi:10.1007/978-3-540-85363-3

    work page doi:10.1007/978-3-540-85363-3

  4. [4]

    [BLY+26] Zongbo Bao, Yuxuan Liu, Penghui Yao, Zekun Ye, and Jialin Zhang

    Association for Computing Machinery.doi:10.1145/1536414.1536437. [BLY+26] Zongbo Bao, Yuxuan Liu, Penghui Yao, Zekun Ye, and Jialin Zhang. Efficient non- adaptive quantum algorithms for tolerant junta testing. In2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 100–126. Society for Industrial and Applied Mathematics, 2026.doi:10.1137/1.9781611...

    work page doi:10.1145/1536414.1536437 2026

  5. [5]

    [BV97] Ethan Bernstein and Umesh Vazirani

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi: 10.4230/LIPIcs.CCC.2019.2. [BV97] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory.SIAM Journal on Computing, 26(5):1411–1473, 1997.doi:10.1137/S0097539796300921. [Cal09] Chris Calabro.The Exponential Complexity of Satisfiability Problems. PhD thesis, University of California at San Diego,

    work page doi:10.4230/lipics.ccc.2019.2 2019

  6. [6]

    Servedio

    [CDL+24] Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio. Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4321–4337. Society for Industrial and Applied Mathematics,

    2024

  7. [7]

    [CG04] Hana Chockler and Dan Gutfreund

    doi:10.1137/1.9781611977912.151. [CG04] Hana Chockler and Dan Gutfreund. A lower bound for testing juntas.Inf. Process. Lett., 90(6):301–305, 2004.doi:10.1016/J.IPL.2004.01.023. [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen. Testing and learning quantum juntas nearly optimally. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the...

    work page doi:10.1137/1.9781611977912.151 2004

  8. [8]

    Association for Computing Machinery.doi:10.1145/3798129. 3800730. [CST+18] Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing.J. ACM, 65(6), November

    work page doi:10.1145/3798129

Show all 16 references
  1. [9]

    [DMN19] Anindya De, Elchanan Mossel, and Joe Neeman

    doi:10.1145/3213772. [DMN19] Anindya De, Elchanan Mossel, and Joe Neeman. Junta Correlation is Testable . In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1549–1563, Los Alamitos, CA, USA, November

    2019 doi

  2. [10]

    doi:10.1109/FOCS.2019.00090

    IEEE Computer Society. doi:10.1109/FOCS.2019.00090. [FGKP06] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pag...

    2019 doi

  3. [11]

    [FKR+04] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky

    doi:10.1109/FOCS.2006.51. [FKR+04] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas.Journal of Computer and System Sciences, 68(4):753–787,

    2006 doi

  4. [12]

    [Gil52] E

    Special Issue on FOCS 2002.doi:10.1016/j.jcss.2003.11.004. [Gil52] E. N. Gilbert. A comparison of signalling alphabets.The Bell System Technical Journal, 31(3):504–522, 1952.doi:10.1002/j.1538-7305.1952.tb01393.x. [Haa81] Uffe Haagerup. The best constants in the khintchine ine...

    2002 doi

  5. [13]

    [Kum26] Vinayak M

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi:10.4230/LIPIcs.CCC.2021.24. [Kum26] Vinayak M. Kumar. Most juntas saturate the hardcore lemma. In2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 142–150. Society for Industrial and Applied Mathematics, 2026....

    2021 doi

  6. [14]

    [NP24] Shivam Nadimpalli and Shyamal Patel

    Association for Computing Machinery.doi:10.1145/780542.780574. [NP24] Shivam Nadimpalli and Shyamal Patel. Optimal non-adaptive tolerant junta testing via local estimators. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1039–1050, New Yo...

    2024 doi

  7. [15]

    [PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld

    Association for Computing Machinery.doi:10.1145/3618260.3649687. [PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation.Journal of Computer and System Sciences, 72(6):1012–1042, 2006.doi:10.1016/j.jcss.2006.03.002. [PRW22] R...

    2006 doi

  8. [16]

    [Val15] Gregory Valiant

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi:10.4230/LIPIcs.CCC.2015.264. [Val15] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem.J. ACM, 62(2), May 2015.doi: 10.1145/2728167. [Var57] Re...

    2015 doi

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.