{"id":"770829b0-d0e5-46cf-a5d8-fa017c95e6ee","arxiv_id":"2606.23194","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum algorithms achieve poly(k) query complexity for tolerant k-junta testing with ε1 = 1/2-1/k and ε2 = 1/2-1/(2k²), while classical algorithms require k^Ω(log k) queries.","lead":"The paper shows a super-polynomial quantum advantage for tolerant k-junta testing: quantum algorithms solve it with poly(k) queries while classical algorithms require k to the power of Omega(log k) queries, for parameters near distance 1/2. A smart generalist might read it to see a concrete case where quantum query access yields exponential savings over classical methods in testing function properties.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"ECC size needed for ε1-closeness conflicts with min-distance needed for classical hardness","rationale":"The reader's weakest assumption correctly flags the new yes-distribution, but the concrete incompatibility between code cardinality and minimum distance is the sharpest technical risk; the quantum side is only an adaptation of prior work and therefore less load-bearing.","tokens_in":1941,"tokens_out":351,"duration_ms":66123,"concrete_test":"From the distance formula, compute the minimal |C| required to obtain reduction 1/k; then apply the Plotkin bound to the smallest δ that the indistinguishability proof (in the style of Chen-Patel) appears to need. If the resulting upper bound on |C| is smaller than the required size, the distribution cannot simultaneously be ε1-close and classically hard.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"To reach distance ≤ ε1 = 1/2 − 1/k, each subcube planting must set a constant on a fraction Ω(1/k) of the 2^{n−k} points (since distance to best constant then drops by exactly that fraction / 2). The construction calls this set an error-correcting code, implying the lower-bound argument uses positive minimum distance δ to establish k^{o(log k)} classical indistinguishability. Any code with δ = Ω(1/poly(k)) has size at most 2^{O((n−k)(1−cδ))} by Plotkin/Singleton, which is exponentially smaller than the required Ω(2^{n−k}/k) when n ≫ k. This tension is the least secure step in the central quantum-vs-classical separation.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.3","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.","tokens_in":2142,"tokens_out":567,"duration_ms":29445,"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":[{"comment":"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.","section":"Abstract (hard distribution paragraph)"},{"comment":"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.","section":"Abstract (quantum tester paragraph)"}],"minor_comments":[{"comment":"The abstract is dense; expanding the one-sentence description of the planted distribution into a short paragraph would improve readability.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."}],"tokens_in":1745,"tokens_out":713,"duration_ms":25074,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is a claimed separation: quantum algorithms solve tolerant k-junta testing with poly(k) queries in a regime near distance 1/2, while any classical algorithm needs k^Ω(log k) queries. They adapt the quantum tester from Bao et al. (SOSA 2026) and introduce a new hard distribution for the classical lower bound by randomly selecting k coordinates and planting an error-correcting code inside each subcube to set matching bits on those positions.\n\nThis extends the Chen-Patel (FOCS 2023) technique with a fresh distribution that aims to make yes-instances closer to juntas than uniform random functions while remaining hard for classical query algorithms. The quantum side is largely borrowed, so the novelty sits in the lower bound construction.\n\nThe soft spot is the tension in the planted distribution. To reach distance at most ε1 = 1/2 - 1/k to some k-junta, the construction must fix the same value on a fraction Ω(1/k) of each subcube. Yet the lower bound argument relies on the planted set having positive minimum distance to ensure indistinguishability under k^{o(log k)} classical queries. Standard coding bounds (Plotkin or Singleton) limit the size of any such code with δ = Ω(1/poly(k)) to far fewer than the required Ω(2^{n-k}/k) points when n ≫ k. The abstract states both properties hold but gives no error analysis or parameter choices that resolve this. If the full paper shows a concrete code family that meets both conditions simultaneously, the separation stands; otherwise the lower bound does not go through.\n\nThis is for researchers working on quantum versus classical query complexity in property testing. A reader focused on junta problems or quantum advantages would find the distribution idea useful even if the separation requires fixes.\n\nIt deserves peer review so the construction details can be checked directly.","headline":"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.","tokens_in":2590,"tokens_out":463,"would_cite":false,"duration_ms":23297,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Tolerant k-junta testing admits poly(k) quantum queries but requires k^Ω(log k) classical queries near distance 1/2.","keywords":["tolerant junta testing","quantum query complexity","classical lower bounds","property testing","error-correcting codes","Boolean functions","adaptive algorithms"],"falsifier":"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.","tokens_in":2848,"feed_emoji":"⚛️","tokens_out":719,"duration_ms":19419,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum solves tolerant junta test in poly(k) queries","feed_subtitle":"Classical algorithms need k to the power Omega(log k) near distance 1/2","key_machinery":"The planted approximate-junta distribution on random k coordinates, where an error-correcting code inside each subcube forces identical random bits on codewords.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Quantum poly(k) queries for tolerant junta testing","Tolerant junta test uses poly(k) quantum queries","Classical k^Omega(log k) bound on tolerant junta testing","Poly(k) quantum near 1/2 for tolerant k-junta test","Quantum poly(k) vs classical lower bound on junta testing"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum poly(k) queries for tolerant junta testing","Tolerant junta test uses poly(k) quantum queries","Classical k^Omega(log k) bound on tolerant junta testing","Poly(k) quantum near 1/2 for tolerant k-junta test","Quantum poly(k) vs classical lower bound on junta testing"]},"model":"grok-4.3","cost_usd":0.009807,"raw_usage":{"total_tokens":4499,"prompt_tokens":937,"num_sources_used":0,"completion_tokens":73,"cost_in_usd_ticks":98074500,"prompt_tokens_details":{"text_tokens":937,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3489,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":937,"tokens_out":73,"duration_ms":26684,"temperature":1.0,"reasoning_tokens":3489,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T06:11:14.329767+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}