{"id":"87597ddc-1ef6-48b2-9d02-1ef876fcd6d2","arxiv_id":"2410.15822","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Improved O(2^k log n / ε²) learning for k-junta distributions matching lower bounds, O(12^k log n / ε²) for quantum junta states with matching lower bounds, and better QAC0 circuit learning from Choi state copies.","lead":"This paper gives improved sample-efficient algorithms for learning classical junta distributions and introduces quantum junta states, plus applies the idea to learning QAC0 circuits via their Choi states. A smart generalist might care because these bounds could make verifying or simulating certain quantum systems more practical.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly flags the access model and distance as the operative premises; those premises are standard and explicitly stated in the abstract. No additional load-bearing gap is apparent in the headline results themselves.","tokens_in":2029,"tokens_out":266,"duration_ms":21135,"concrete_test":"Re-derive the classical junta learner from the full proof (Section 3 or equivalent) and confirm that the variable-identification step uses at most O(2^k log n / ε²) samples total while achieving TV error ε; if an extra log(1/ε) or poly(k) factor appears, the quadratic improvement claim weakens.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on standard sample-complexity arguments for learning low-support distributions (after support identification) and low-junta quantum states (via shadow tomography or direct estimation on the relevant subsystem). The classical upper bound matches the known lower bound in all parameters, the quantum upper/lower bounds differ only by a constant factor in the 2^k term, and the QAC^0 claim is a direct corollary of the cited Pauli-spectrum concentration implying junta closeness of the Choi state. No internal inconsistency or hidden assumption is visible from the stated results.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript studies three related learning problems. For classical k-junta distributions over {-1,1}^n it claims an upper bound of O(2^k log n / ε²) samples to achieve total-variation error ε, quadratically improving Aliakbarpour et al. (COLT'16) and matching their lower bound in every parameter. For the newly defined k-junta quantum states (tensor product of a k-qubit state and an (n-k)-qubit maximally mixed state) it gives an upper bound of O(12^k log n / ε²) copies for trace-distance error ε together with a lower bound of Ω((4^k + log n)/ε²); for constant k it also gives a tight Θ̃(2^n / ε²) bound for testing k-junta states. Finally, it observes that the Choi states of QAC^0 circuits (size s, depth d, a ancillas) are close to juntas by the Pauli-spectrum concentration of Nadimpalli et al. (STOC'24), yielding a learning algorithm that uses only 2^{O(log(s² 2^a)^d)} log n copies of the Choi state, improving the prior n^{O(log(s² 2^a)^d)} bound.","tokens_in":2129,"tokens_out":580,"duration_ms":22079,"significance":"If the stated bounds hold, the work supplies nearly tight sample complexities for learning low-junta objects in both classical and quantum settings and supplies a useful reduction from QAC^0 learning to junta-state learning. The classical result closes the quadratic gap left by prior work while matching the information-theoretic lower bound in all parameters; the quantum results introduce a natural definition and obtain upper and lower bounds that differ only by a small constant factor in the 2^k term. The QAC^0 corollary is a direct and clean consequence of existing spectrum concentration. These contributions are of clear interest to the quantum learning-theory community.","major_comments":[],"minor_comments":[{"comment":"Abstract, item (3): the exponent notation 2^{O(log(s^22^a)^d)} is ambiguous; explicitly parenthesize to clarify whether the logarithm is raised to the d power or the entire expression is inside the logarithm.","section":null},{"comment":"The definition of a quantum junta state (tensor product of a k-qubit state and maximally mixed state on the remaining qubits) should be stated verbatim in the introduction or the first section that introduces the concept, rather than only by reference to the classical case.","section":null},{"comment":"The testing result for constant-k junta states is stated only in the abstract; a brief pointer to the relevant theorem or section would help readers locate the argument.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive summary, recognition of the significance of our results, and recommendation for minor revision. No specific major comments were raised in the report.","responses":[],"tokens_in":1685,"tokens_out":52,"duration_ms":9412,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main results are a sample bound of O(2^k log n / ε²) for learning k-junta distributions that matches the COLT'16 lower bound in every parameter, plus the first explicit bounds for learning quantum k-junta states (O(12^k log n / ε²) upper, Ω(4^k + log n / ε²) lower) and a corollary for learning QAC0 circuits via their Choi states being close to juntas. The classical improvement comes from a tighter analysis of support identification followed by estimation on the relevant coordinates. The quantum definition treats the state as a k-qubit piece tensored with maximally mixed on the rest, and the bounds follow from standard low-dimensional estimation plus information-theoretic arguments. The QAC0 claim is a direct remark that the prior Pauli-spectrum concentration already implies junta closeness for the Choi state, which upgrades the sample complexity from n to the exponential of log terms. The work is straightforward and extends the cited papers without circularity. The classical bound is a clean match to the lower bound. The quantum bounds leave a constant-factor gap in the 2^k term, which is typical and not a load-bearing issue. The testing result for constant k requiring Θ(2^n / ε²) copies is consistent with needing to probe the full space. Minor soft spots are that the 12^k constant could probably be improved with more care, and the QAC0 application inherits whatever looseness exists in the STOC'24 concentration result. Nothing here looks invented or overclaimed from the abstract and the stress-test note. This is for people in quantum property testing and learning theory who care about junta structure or low-depth circuits. It deserves a serious referee because the classical result is tight and the quantum direction is new with verifiable bounds. I would send it to peer review.","headline":"The paper closes the classical junta distribution learning gap with a tight quadratic improvement and opens quantum junta states with concrete bounds.","tokens_in":2620,"tokens_out":434,"would_cite":true,"duration_ms":18630,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AlexanderDuality.lean","rs_theorem":"alexander_duality_circle_linking","paper_passage":"We show that they can be learned with to error ε in total variation distance from O(2^k log(n)/ε²) samples... Pauli spectrum of QAC0 circuits is concentrated on low-degree... Choi states of those circuits are close to be juntas."},{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"Our techniques are based on Fourier and Pauli analysis, and our learning upper bounds are a refinement of the low degree algorithm by Linial, Mansour, and Nisan."}],"headline":"Junta learning via sparse low-degree Fourier/Pauli spectra lies outside RS scope","alignment":"orthogonal","rationale":"The paper's central machinery (refinement of LMN low-degree algorithm with sparsity rounding on at most 2^k/4^k terms, Classical Shadows for Pauli coefficients, concentration implying junta closeness for QAC0 Choi states) operates entirely in computational learning theory and quantum information. RS derives J-cost, φ, 8-tick periodicity, D=3 via Alexander duality, and spacetime from a single distinction (reality_from_one_distinction, AbsoluteFloorClosure, AlexanderDuality). No overlap or contradiction exists; RS has no theorems on sample complexity, juntas, or spectrum learning.","tokens_in":59947,"confidence":"high","tokens_out":358,"duration_ms":7357,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"k-junta distributions can be learned to total variation error ε with O(2^k log n / ε²) samples, matching the lower bound.","keywords":["junta distributions","quantum junta states","QAC0 circuits","sample complexity","trace distance","total variation distance","Pauli spectrum","learning theory"],"falsifier":"An algorithm that learns every k-junta distribution to error ε using o(2^k log n / ε²) samples, or a k-junta distribution family that requires ω(2^k log n / ε²) samples, would settle the claimed sample complexity.","tokens_in":2933,"feed_emoji":"📊","tokens_out":889,"duration_ms":23063,"temperature":0.7,"pith_summary":"The paper establishes that k-junta distributions over n bits, which depend on only k coordinates, can be learned to error ε in total variation distance from O(2^k log(n)/ε²) samples. This quadratically improves the prior upper bound and matches the known lower bound in every parameter. It extends the approach to quantum k-junta states, defined as tensor products of a k-qubit state and a maximally mixed state on the remaining qubits, which are learnable to trace distance ε with O(12^k log(n)/ε²) single copies and have a lower bound of Ω((4^k + log n)/ε²). The work also shows that the Choi states of QAC0 circuits are close to juntas, allowing learning of such circuits from 2^{O(log(s² 2^a)^d)} log n copies instead of the previous n to a power. A sympathetic reader would care because the bounds are nearly tight and reduce the resources needed for learning structured objects in high dimensions.","feed_headline":"Junta distributions learned with O(2^k log n / ε²) samples","feed_subtitle":"Result matches lower bound exactly and improves quadratically on prior work; similar gains hold for quantum states and QAC0 circuit learning","key_machinery":"The k-junta property (dependence on only k out of n bits or qubits) together with concentration of the Fourier spectrum for classical cases and the Pauli spectrum for quantum cases.","core_discovery":"The central claim is that k-junta distributions can be learned to error ε in total variation distance from O(2^k log(n)/ε²) samples, quadratically improving the upper bound of Aliakbarpour et al. and matching their lower bound in every parameter. Quantum k-junta states can be learned to trace distance ε with O(12^k log(n)/ε²) single copies, along with a lower bound of Ω((4^k + log n)/ε²) copies; for constant k, testing requires Θ̃(2^n/ε²) copies. QAC0 circuits with size s, depth d, and a auxiliary qubits have Choi states close to juntas and thus can be learned from 2^{O(log(s² 2^a)^d)} log n copies of the Choi state, improving the prior n^{O(log(s² 2^a)^d)} bound.","pith_inferences":["The quadratic classical improvement may indicate that refined estimators can tighten bounds in other distribution learning settings.","The Pauli-spectrum approach for QAC0 could extend to additional circuit families with low-degree concentration.","The testing lower bound for constant-k juntas suggests that structured quantum state learning can still require resources comparable to full tomography in the worst case."],"forward_implications":["Learning junta distributions now matches the information-theoretic lower bound in the dependence on k, n, and ε.","Quantum junta states admit learning with a number of copies exponential in k but only logarithmic in n.","For constant k, distinguishing k-junta states from those 7ε-far requires Θ(2^n / ε²) copies.","QAC0 circuits become learnable with a sample count that is polylogarithmic in n rather than polynomial."],"fun_headline_variants":["O(2^k log n / ε²) samples learn k-junta distributions","Quantum junta states learned with O(12^k log n / ε²) copies","QAC0 circuits learned from 2^{O(log(s²2^a)^d)} log n copies","Ω((4^k + log n)/ε²) lower bound for quantum junta states","tilde Θ(2^n/ε²) copies test constant k junta states"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Access consists of independent classical samples or single copies of the quantum state, and error is measured in total variation or trace distance.","fun_headline_variants_meta":{"raw":{"variants":["O(2^k log n / ε²) samples learn k-junta distributions","Quantum junta states learned with O(12^k log n / ε²) copies","QAC0 circuits learned from 2^{O(log(s²2^a)^d)} log n copies","Ω((4^k + log n)/ε²) lower bound for quantum junta states","tilde Θ(2^n/ε²) copies test constant k junta states"]},"model":"grok-4.3","cost_usd":0.006135,"raw_usage":{"total_tokens":3068,"prompt_tokens":1013,"num_sources_used":0,"completion_tokens":109,"cost_in_usd_ticks":61349500,"prompt_tokens_details":{"text_tokens":1013,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1946,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1013,"tokens_out":109,"duration_ms":14277,"temperature":1.0,"reasoning_tokens":1946,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-23T18:39:38.765143+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An algorithm that learns every k-junta distribution to error ε using o(2^k log n / ε²) samples, or a k-junta distribution family that requires ω(2^k log n / ε²) samples, would settle the claimed sample complexity.","supporting_citations":[],"review_version":1}