Pith. sign in

REVIEW 1 major objections 1 minor 10 references

Quantum Query Complexity of the Hyperoctahedral Group

T0 review · 1 major / 1 minor · reviewed 2026-05-10 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The quantum query complexity of oracle identification on the hyperoctahedral group equals 2(N-1) for every N at least 2.

desk verdict 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. read the letter →

arxiv 2604.13554 v1 submitted 2026-04-15 math.CO

Ji Ho Bae This is my paper · ORCID
classification math.CO
keywords quantumquerycomplexityhyperoctahedralgrouporacleidentificationsymmetricparityobstructionRademacherpolynomialstensorproductgraphadversarybound
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 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.

What carries the argument

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.

What would settle it

An explicit calculation of the query complexity for N=3 returning any number other than 4.

Watch

Extended reading notes

Core claim

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)!!.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

1 major / 1 minor

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.

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 (1)
  1. [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.
minor comments (1)
  1. [Concluding remarks] 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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: [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.

    Authors: 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: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: derivation relies on independent representation-theoretic reductions

full rationale

The paper derives Q_LV(B_N)=2(N-1) by reducing via Rademacher moment polynomials to S_N Kronecker products, applying the bipartition distance d_T(((N),∅),(α,β))=2(N-α_1)-|β| in the tensor-product graph, and imposing the ε-parity obstruction that restricts sgn(σ) to even tensor powers. None of these steps is self-definitional, a fitted input renamed as prediction, or a load-bearing self-citation whose justification collapses into the present result. The closed-form multiplicity (2N-3)!! is obtained from the distance formula rather than presupposing the final complexity value. The derivation is therefore self-contained against external benchmarks and receives the default non-circularity finding.

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

Limited to abstract; relies on standard representation theory of symmetric and hyperoctahedral groups plus specific combinatorial tools whose independence from the target result cannot be verified without the full text.

assumptions (2)
  • standard math Standard facts from the representation theory of the symmetric group S_N and its hyperoctahedral extension B_N, including Kronecker product decompositions and the sign representation.
    Invoked in the reduction to S_N and the restriction of sgn(σ) to even tensor powers.
  • domain assumption The bipartition distance formula d_T(((N),∅),(α,β)) = 2(N-α_1)-|β| holds in the tensor product graph.
    Used directly to obtain the query complexity bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Query Complexity of the Hyperoctahedral Group." pith.science (2026). https://pith.science/paper/2604.13554

@misc{pith2026260413554,
  author       = {Pith},
  title        = {Pith review of: Quantum Query Complexity of the Hyperoctahedral Group},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.13554}},
  note         = {Machine review of arXiv:2604.13554}
}
abstract

We determine the quantum query complexity of oracle identification on the hyperoctahedral group $B_N = \{\pm 1\}^N \rtimes S_N$ with respect to the natural representation: $Q_{LV}(B_N) = 2(N-1)$ for all $N \ge 2$. This is twice the symmetric-group value $Q_{LV}(S_N) = N-1$; the doubling arises from an $\varepsilon$-parity obstruction that restricts the bottleneck representation $\operatorname{sgn}(\sigma)$ 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),\varnothing),(\alpha,\beta)) = 2(N-\alpha_1)-|\beta|$ in the tensor product graph. A closed-form generating function yields the first-appearance multiplicity $(2N-3)!!$. We also show $Q_{\mathrm{decomp}}(\varphi) \le 2\,Q_{\mathrm{signed}}(\varphi)$, with equality on $B_2$, and conjecture a link between the adversary bound and the graph eccentricity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    SIAM Journal on Computing , volume =

    E. Bernstein and U. Vazirani,Quantum complexity theory, SIAM J. Comput.26 (1997), no. 5, 1411–1473. doi:10.1137/S0097539796300921

    work page doi:10.1137/s0097539796300921 1997

  2. [2]

    Journal of Computer and System Sciences , volume =

    A. Ambainis,Quantum lower bounds by quantum arguments, J. Comput. System Sci.64(2002), no. 4, 750–767. doi:10.1006/jcss.2002.1826. arXiv:quant-ph/0002066

    work page doi:10.1006/jcss.2002.1826 2002

  3. [3]

    Copeland and J

    D. Copeland and J. Pommersheim,Quantum query complexity of symmetric oracle problems, Quantum5(2021), 403. doi:10.22331/q-2021-03-07-403. arXiv:1812.09428

    work page doi:10.22331/q-2021-03-07-403 2021

  4. [4]

    Ceccherini-Silberstein, F

    T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli,Representation Theory and Harmonic Analysis of Wreath Products of Finite Groups, London Mathemati- cal Society Lecture Note Series, vol. 410, Cambridge University Press, 2014. doi:10.1017/CBO9781107279087

    work page doi:10.1017/cbo9781107279087 2014

  5. [5]

    J. P. Doeraene and G. Iommi Amun´ ategui,Branching rules for the hyperoctahedral group, J. Math. Phys.30(1989), no. 11, 2469–2475. doi:10.1063/1.528526

    work page doi:10.1063/1.528526 1989

  6. [6]

    Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages =

    P. Høyer, T. Lee, and R. ˇSpalek,Negative weights make adversaries stronger, in:Proc. 39th ACM STOC, 2007, pp. 526–535. doi:10.1145/1250790.1250867. arXiv:quant- ph/0611054. QUANTUM QUERY COMPLEXITY OFB N 33

    work page doi:10.1145/1250790.1250867 2007

  7. [7]

    James and A

    G. James and A. Kerber,The Representation Theory of the Symmetric Group, En- cyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley, 1981

    work page 1981

  8. [8]

    Geck and G

    M. Geck and G. Pfeiffer,Characters of Finite Coxeter Groups and Iwahori–Hecke Algebras, London Mathematical Society Monographs, New Series, vol. 21, Oxford University Press, 2000

    work page 2000

Show all 10 references
  1. [9]

    T. Lee, R. Mittal, B. W. Reichardt, R. ˇSpalek, and M. Szegedy,Quantum query complexity of state conversion, in:Proc. 52nd IEEE FOCS, 2011, pp. 344–353. doi:10.1109/FOCS.2011.75. arXiv:1011.3020

    2011 doi

  2. [10]

    van Dam,Quantum oracle interrogation: Getting all information for almost half the price, in:Proc

    W. van Dam,Quantum oracle interrogation: Getting all information for almost half the price, in:Proc. 39th IEEE FOCS, 1998, pp. 362–367. doi:10.1109/SFCS.1998.743486. [Address] Email address:jihobae@snu.ac.kr

    1998 doi

Pith tools

Reviewed May 10, 2026 · model on record in the stance chip above.