On the sample complexity of the generalized hidden shift problem over arbitrary finite groups

1 Introduction

• The injective cyclic hidden-shift case is equivalent to the dihedral HSP, for which Kuperberg’s sieve gives a subexponential-time quantum algorithm.No accepted general polynomial-time solution is known, according to the passage.Source: §1 · p. 1
• For M successive injective functions, each slice is a translate of the preceding slice by the same unknown shift, which the task is to recover.The promise is f(b, x) = f(b + 1, x + s) for b=0,...,M−2.Source: §1 · pp. 1–2
• At M=2 the problem is the injective hidden shift problem over ZN and hence the dihedral HSP; at M=N it becomes an abelian HSP solvable by Fourier sampling.Intermediate M does not provide a full group action in the first coordinate, and is not naturally an HSP over a finite group.Source: §1 · p. 2
• The M-parameter offers a controlled way to study how oracle redundancy, noncommutative representation theory, and collective measurement complexity interact.The motivation includes symmetric-group formulations of rigid graph isomorphism and related group-action isomorphism problems, including code equivalence.Source: §1 · p. 2
• Ω(log |G|) lower bounds hold for G=(Z2)^n and G=S_n; Montanaro gives an O(log |G|) upper bound for every finite group.The article’s bounds are stated in terms of group-theoretic data.Source: §1 · p. 2
• The paper formulates generalized hidden shift over generic finite groups and derives sample-complexity upper and lower bounds using the generalized Holevo-Curlander inequality.The analysis recovers the cyclic-group analysis of Childs and van Dam [3].Source: §1 · p. 2

2.1 Quantum state discrimination

• State discrimination is framed as optimizing average success probability over measurements, with a dual formulation minimizing tr(K) subject to K ≥ p_iρ_i.The dual program has the same value by strong duality.Source: §2.1 · pp. 2–3

2.2 Representation theory of finite groups

• The preliminaries define unitary representations and characters, describe the group algebra through irreducible representations, and state Schur’s orthogonality.For finite abelian groups, the characters form an orthonormal basis for the group algebra.Source: §2.2 · p. 3

2.3 Fourier transform over finite groups

• The quantum Fourier transform over a finite group is a unitary encoding of the classical Fourier transform.Its unitarity follows from Schur’s orthogonality.Source: §2.3 · pp. 3–4

3.1 Set up

• The oracle slices are injective and successive slices are related by right multiplication by one unknown group element; the goal is to identify that element.After measuring and discarding the third register, the task reduces to distinguishing the shift-indexed states with a uniform prior.Source: §3.1 · p. 4

3.2 Rewriting the hidden shift states into block-diagonal form

• Applying the Fourier-transform and Schur-orthogonality rewriting yields a compound geometrically uniform ensemble whose generators correspond one-to-one with conjugacy classes of G.The passage describes this as the block-diagonal form of the hidden-shift states.Source: §3.2 · p. 5

4.1 Sample complexity of state discrimination

• For an ensemble of n states, Barnum–Knill’s pairwise-fidelity bound gives k_min ≤ O(log n − log µ).The asymptotic order is unaffected by the constant error threshold ϵ.Source: §4.1 · p. 6
• The analysis focuses on normalized-projector states because general spectral information remains complicated.In this case each state is a projection of rank r.Source: §4.1 · pp. 6–7

4.2 Sample complexity of discriminating the generalized hidden shift states

• The hidden-shift state-discrimination analysis takes m = |G| as its simplifying case.Source: §4.2 · p. 7

4.2.1 Upper bound

• The upper-bound proof computes pairwise fidelities directly, while the generalized Holevo–Curlander estimate offers a simpler trace-based route.The estimate bounds optimal success probability using a trace quantity.Source: §4.1 · p. 6, Proposition 8. Define · p. 9

Proposition 8. Define

• The proposition’s proof presents generalized Holevo–Curlander as a simpler alternative to the direct pairwise-fidelity calculation.Source: Proposition 8. Define · pp. 8–9

4.2.2 Lower bound

• Θ(log |G|) is the sample-complexity scaling for G = (Z/2)^n; the section also gives a lower bound for G = S_n.The lower-bound analysis defines g(G) as the largest element order occurring in G.Source: §4.2.2 · p. 10

• The quantum Fourier transform and Schur’s orthogonality give a block-diagonal description of the hidden-shift states and the pretty good measurement.Source: §5 · p. 11
• The generalized Holevo–Curlander inequality yields upper and lower sample-complexity bounds in terms of group-theoretic data for normalized-projector hidden-shift states.Source: §5 · p. 11
• Θ(log |G|) is the tight sample-complexity scaling for G = (Z/2)^n.Source: §5 · p. 11
• For G = S_n, the lower bound is Ω(√n log n) = Ω(log |G|).The generalized hidden shift problem over S_n directly formulates rigid graph isomorphism.Source: §5 · p. 11