{"id":"d3b1560c-018e-449d-a56b-975c0ace9453","arxiv_id":"2604.13554","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum query complexity Q_LV(B_N) equals 2(N-1) for the hyperoctahedral group, twice the symmetric group value due to an ε-parity obstruction restricting the sign representation to even tensor powers.","lead":"The paper determines that the quantum query complexity for oracle identification on the hyperoctahedral group B_N is exactly 2(N-1) for N at least 2. This doubles the known value for the symmetric group and arises from a parity restriction on representations in tensor powers.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"Correctness of bipartition distance formula d_T(((N),∅),(α,β))=2(N-α_1)-|β| after ε-parity restriction","rationale":"The reader's weakest assumption already isolates the distance formula together with the ε-parity and Rademacher reduction; this is the precise point at which the doubling from N-1 to 2(N-1) is asserted. A direct small-N enumeration of the graph distances provides an independent, finite check that either confirms the formula holds under the restriction or exposes a mismatch, without requiring the full general proof.","tokens_in":1801,"tokens_out":407,"duration_ms":61923,"concrete_test":"For N=3 enumerate all bipartitions (α,β) with |α|+|β|=3, build the tensor-product graph on the B_3 irreps using the actual Kronecker rules, compute graph distances from ((3),∅) to each other bipartition, and check whether they equal 2(3-α_1)-|β|; also verify that the minimal distance under the even-tensor-power restriction produces adversary bound exactly 4. If any distance deviates, the formula or its application under the obstruction is incorrect.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The exact value Q_LV(B_N)=2(N-1) is obtained by combining the Rademacher moment polynomial reduction to S_N Kronecker products with the stated bipartition distance in the tensor product graph, then restricting the bottleneck sgn(σ) to even tensor powers via the ε-parity obstruction. If the distance formula fails to hold (or yields a different minimal value) once the even-power restriction and signed-permutation structure are imposed, the lower bound no longer matches 2(N-1) and the doubling claim does not follow. The closed-form multiplicity (2N-3)!! is derived from this distance, so any error propagates directly to the claimed complexity.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript determines the quantum query complexity of oracle identification on the hyperoctahedral group B_N = {±1}^N ⋊ S_N with respect to the natural representation, claiming the exact value Q_LV(B_N) = 2(N-1) for all N ≥ 2. This doubles the symmetric-group value Q_LV(S_N) = N-1, with the increase attributed to an ε-parity obstruction restricting the bottleneck representation sgn(σ) to even tensor powers. The proof reduces the problem to S_N Kronecker products via Rademacher moment polynomials, applies the bipartition distance formula d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| in the tensor product graph, and extracts the first-appearance multiplicity (2N-3)!! via a closed-form generating function. It also establishes Q_decomp(ϕ) ≤ 2 Q_signed(ϕ) with equality on B_2 and conjectures a connection between the adversary bound and graph eccentricity.","tokens_in":1942,"tokens_out":532,"duration_ms":63256,"significance":"If the central claims are correct, the result is a solid contribution to quantum query complexity, furnishing the first exact determination for the hyperoctahedral group and clarifying how the signed-permutation structure produces a precise doubling factor through representation-theoretic obstructions. The reduction technique via Rademacher polynomials and the explicit multiplicity formula are strengths that make the derivation falsifiable and potentially reproducible. The inequality between query models and the eccentricity conjecture add value by suggesting concrete follow-up directions.","major_comments":[{"comment":"The bipartition distance formula d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| after imposition of the ε-parity obstruction: the manuscript must explicitly verify that restricting sgn(σ) to even tensor powers (and incorporating the signed-permutation action) leaves the minimal distance unchanged at 2(N-1). This step is load-bearing for both the lower bound and the closed-form multiplicity (2N-3)!!; any shift in the minimal distance would invalidate the exact doubling claim.","section":"Proof of the main theorem (reduction and distance calculation)"}],"minor_comments":[{"comment":"The conjecture relating the adversary bound to graph eccentricity is stated only briefly; a precise mathematical formulation (including the relevant graph and bound definitions) would improve clarity for readers.","section":"Concluding remarks"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading and for recognizing the contribution of the exact determination of Q_LV(B_N). We address the single major comment below and will incorporate the requested verification into the revised manuscript.","responses":[{"response":"We agree that an explicit verification of the distance under the ε-parity restriction is necessary for rigor. The obstruction restricts sgn(σ) to even tensor powers, which in the tensor-product graph corresponds to even total degree. The shortest paths realizing d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| can always be chosen to consist of even-degree steps (by pairing transpositions or reflections), so the minimal distance to ((N),∅) remains exactly 2(N-1). The signed-permutation action is already encoded in the Rademacher moment polynomials used for the reduction; these polynomials preserve the parity filtration and do not alter the combinatorial distance. We will insert a short lemma (or expanded paragraph) immediately after the statement of the distance formula that (i) recalls the even-power restriction, (ii) exhibits an explicit even-parity path of length 2(N-1), and (iii) argues that no shorter even-parity path exists. This addition will also make the subsequent multiplicity extraction (2N-3)!! fully self-contained.","revision_made":"yes","referee_comment":"[Proof of the main theorem (reduction and distance calculation)] The bipartition distance formula d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| after imposition of the ε-parity obstruction: the manuscript must explicitly verify that restricting sgn(σ) to even tensor powers (and incorporating the signed-permutation action) leaves the minimal distance unchanged at 2(N-1). This step is load-bearing for both the lower bound and the closed-form multiplicity (2N-3)!!; any shift in the minimal distance would invalidate the exact doubling claim."}],"tokens_in":1478,"tokens_out":430,"duration_ms":24135,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper gives a precise value for the quantum query complexity of oracle identification on the hyperoctahedral group: Q_LV(B_N) = 2(N-1) for N ≥ 2. That is exactly twice the symmetric-group result, and the doubling comes from an ε-parity obstruction that forces the bottleneck representation to even tensor powers only. They also extract a closed-form multiplicity (2N-3)!! for the first appearance and prove Q_decomp(φ) ≤ 2 Q_signed(φ) with equality at N=2, plus a conjecture tying the adversary bound to graph eccentricity. The proof route reduces via Rademacher moment polynomials to S_N Kronecker products, then uses the stated bipartition distance in the tensor-product graph. That combination is new relative to the symmetric-group literature and produces explicit numbers rather than asymptotics. The reduction step and the generating-function extraction for the multiplicity look like the parts that work cleanly if the distance formula holds. The soft spot is the bipartition distance d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| once the even-power restriction and signed-permutation structure are imposed. The stress-test concern is real: if that formula was derived without the parity filter or does not give the same minimal value afterward, the lower bound no longer matches 2(N-1) and the doubling claim slips. The abstract presents the formula as applying directly, but the full derivation would need to show it survives the restriction without adjustment. The multiplicity expression inherits the same dependence, so any gap there affects the whole result. This is for readers already working on quantum query complexity for algebraic groups or representation-theoretic adversary bounds. Someone extending symmetric-group techniques to signed or hyperoctahedral cases would find the explicit formulas and the parity explanation useful. It deserves a serious referee because it delivers a concrete, falsifiable claim with a clear proof outline and no obvious circularity, even though the distance step after restriction is the part that needs verification.","headline":"The paper pins down Q_LV(B_N) exactly at 2(N-1) by doubling the symmetric-group case through an ε-parity restriction, with a clean closed-form multiplicity, though the key bipartition distance needs close checking after the restriction.","tokens_in":2452,"tokens_out":510,"would_cite":false,"duration_ms":23575,"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":"The quantum query complexity of oracle identification on the hyperoctahedral group equals 2(N-1) for every N at least 2.","keywords":["quantum query complexity","hyperoctahedral group","oracle identification","symmetric group","parity obstruction","Rademacher polynomials","tensor product graph","adversary bound"],"falsifier":"An explicit calculation of the query complexity for N=3 returning any number other than 4.","tokens_in":2678,"feed_emoji":"⚛","tokens_out":727,"duration_ms":58153,"temperature":0.7,"pith_summary":"The paper sets out to compute the exact number of quantum queries needed to identify an unknown oracle whose labels come from the hyperoctahedral group, the group of signed permutations. It establishes that this number is exactly 2(N-1), which is double the corresponding number for the ordinary group of permutations. The extra factor of two traces back to a parity restriction that blocks certain representations from appearing in odd tensor powers. A reader would care because the result gives a precise benchmark rather than an estimate, allowing direct comparison of quantum resources across different algebraic structures and clarifying how signs interact with permutations under quantum access.","feed_headline":"Hyperoctahedral group requires 2(N-1) quantum queries","feed_subtitle":"Exact value doubles the symmetric group figure because parity blocks odd powers of the sign representation.","key_machinery":"The ε-parity obstruction that forces the sign representation to appear only in even tensor powers, together with the bipartition distance formula that measures distances in the tensor-product graph.","core_discovery":"We determine the quantum query complexity of oracle identification on the hyperoctahedral group B_N = {±1}^N ⋊ S_N with respect to the natural representation: Q_LV(B_N) = 2(N-1) for all N ≥ 2. This is twice the symmetric-group value Q_LV(S_N) = N-1; the doubling arises from an ε-parity obstruction that restricts the bottleneck representation sgn(σ) to even tensor powers. The proof combines a reduction to S_N Kronecker products via Rademacher moment polynomials with the bipartition distance formula d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| in the tensor product graph. A closed-form generating function yields the first-appearance multiplicity (2N-3)!!.","pith_inferences":["The same doubling from sign flips may recur for other wreath-product groups under quantum oracles.","The reduction technique that maps the problem to symmetric-group Kronecker products could apply to query problems on similar semidirect products.","Numerical verification of the adversary-eccentricity conjecture for small N would test whether the graph-theoretic view fully captures the complexity."],"forward_implications":["The complexity is exactly double the value already known for the symmetric group.","A generating function exists that produces the multiplicity of the first time each irreducible appears.","Decomposition query complexity is at most twice the signed version, with equality at N=2.","The adversary bound is conjectured to equal the eccentricity of the underlying graph."],"fun_headline_variants":["Hyperoctahedral group sets quantum query complexity to 2(N-1)","Exact bound for B_N is 2(N-1) quantum queries","Parity doubles quantum queries for the hyperoctahedral group","Hyperoctahedral B_N needs 2(N-1) queries due to parity"],"cache_read_input_tokens":64,"weakest_assumption_plain":"A parity rule blocks the sign representation from odd tensor powers and a specific distance formula correctly measures separation in the graph of tensor products.","fun_headline_variants_meta":{"raw":{"variants":["Hyperoctahedral group sets quantum query complexity to 2(N-1)","Exact bound for B_N is 2(N-1) quantum queries","Parity doubles quantum queries for the hyperoctahedral group","Hyperoctahedral B_N needs 2(N-1) queries due to parity"]},"model":"grok-4.3","cost_usd":0.012755,"raw_usage":{"total_tokens":5580,"prompt_tokens":741,"num_sources_used":0,"completion_tokens":79,"cost_in_usd_ticks":127549500,"prompt_tokens_details":{"text_tokens":741,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4760,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":741,"tokens_out":79,"duration_ms":34990,"temperature":1.0,"reasoning_tokens":4760,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-10T13:30:11.195668+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit calculation of the query complexity for N=3 returning any number other than 4.","supporting_citations":[],"review_version":1}