Hidden Subgroup Problems

A shared language for hidden regularity

The hidden subgroup problem, or HSP, describes functions whose repeated values reveal a group symmetry. It unifies several quantum algorithms without making them identical. Simon hides an XOR symmetry. Order finding hides repetition in modular powers. Discrete logarithms can be expressed through a hidden relation between two exponents. Fourier sampling is especially effective when the group is Abelian, meaning its operation commutes.

Review Simon’s algorithm, the QFT and order finding. This chapter introduces group vocabulary through finite examples. A group is a set with an associative composition, an identity and inverses; a subgroup is a subset that remains a group under the same operation.

WORKED DIAGRAM · A15Hidden subgroup {0,4} modulo eight

The inputs differ by four. Their Fourier contributions cancel at odd labels and reinforce at even labels, each of which has probability 1/4.

The promise

Let G be a finite group and H an unknown subgroup. The function is constant on each coset of H and takes different values on different cosets. In an additive Abelian group, a coset is a set x plus H. The task is to identify H, typically by returning a compact set of generators rather than listing every element.

The function is supplied through coherent reversible access. The group representation and arithmetic also need efficient implementations for an efficient algorithmic result. Merely calling an enormous set a group does not supply a cheap Fourier transform, uniform preparation or oracle. State those resources alongside the promise.

A function with occasional accidental collisions does not satisfy this contract. The equal-output classes must be exactly the promised cosets. Like other promise problems, a circuit can still run on an invalid input, but its subgroup interpretation then lacks the stated guarantee.

Work a subgroup of integers modulo eight

Take G to be the integers zero through seven under addition modulo eight. Let H contain zero and four. Its cosets are the pairs zero/four, one/five, two/six and three/seven. A valid oracle gives one output label to each pair and different labels to different pairs.

Prepare a uniform superposition over G and query. If measuring the output selects the one/five label, the input becomes the equal superposition of one and five. Apply the eight-point QFT. The contribution from five differs from the contribution from one by a factor of negative one raised to the output label y. Odd y values cancel; even y values survive.

The possible Fourier samples are therefore zero, two, four and six, each with probability one quarter. These labels are exactly the characters that are trivial on the hidden subgroup. Several samples reveal constraints consistent with H. The oracle’s arbitrary output names are irrelevant; the repeated-value structure is what matters.

Characters explain the cancellation

For an Abelian group, a character assigns a unit complex phase to each group element while turning group composition into phase multiplication. On integers modulo N, the characters are the familiar Fourier phase factors. A character is trivial on H if it assigns phase one to every element of H.

The Fourier amplitude of a coset state contains a sum of character values over H. For a character trivial on H, the terms reinforce. For a nontrivial restriction, symmetry forces cancellation. The measured support is therefore the annihilator of H: the set of characters that are trivial on it. Classical group arithmetic then reconstructs H from those constraints.

This is the group-theoretic version of Simon’s orthogonality equation. In the XOR group, characters are signs determined by binary dot products, and being trivial on the two-element subgroup generated by s means y dot s equals zero. The language is more general, but the interference mechanism is the same pairing or symmetry cancellation you already know.

Connection to order finding

Modular powers repeat with a period. In a finite cyclic setting where the domain length is compatible with that period, the repeated-value classes form cosets of a subgroup. Fourier sampling returns reciprocal-period information. Practical order finding handles a power-of-two approximation grid and uses rational reconstruction, so it should not be reduced to the oversimplified claim that every period divides the chosen register length.

The HSP perspective identifies the shared structure while the order-finding chapter supplies the precision, arithmetic and reconstruction details. A unifying abstraction is useful only when it preserves the application-specific assumptions that make the algorithm implementable.

A discrete-logarithm example

Suppose a cyclic group has prime order q, generator g, and an element h equal to g raised to an unknown x. Define a function of two exponents by g to the power a times h to the power b. Its value depends on a plus x times b modulo q. The hidden subgroup consists of pairs satisfying that expression equal to zero.

Fourier samples supply relations between the two output coordinates. With the convention used here, a sample k, l satisfies l equal to k times x modulo q. When k is nonzero, invert k and recover x. For q five and x three, sample k two and l one gives x equal to three, because the inverse of two modulo five is three.

This demonstrates why discrete logarithms fit the same hidden-relation framework, but its oracle arithmetic differs from factoring. An application must implement the chosen group’s operations and ensure the encoding supports the required coherent evaluation. Group theory describes the structure; it does not erase arithmetic costs.

Abelian and non-Abelian boundaries

In finite Abelian groups, one-dimensional characters make Fourier sampling particularly clean. Non-Abelian groups have higher-dimensional representations and additional choices about what information to measure. The Abelian cancellation proof does not automatically produce an efficient general non-Abelian algorithm. Any claim for a specific non-Abelian family needs its own access assumptions, reconstruction procedure and complexity analysis.

This boundary is pedagogically important. A framework can connect solved tasks and still contain difficult families. Learning the HSP does not mean that every problem with a hidden symmetry is now efficiently solved. Ask which group, which oracle, which measurements and which classical reconstruction are actually available.

Exercises

1. In the modulo-eight example, why can Fourier label three not occur for the coset one/five? Calculate the relative phase of the two contributions.

2. For a prime-order discrete-logarithm instance with q seven, a Fourier sample satisfies k two and l six. Recover x under the stated relation. Why is k zero unhelpful for that division step?

Worked answers

1. The inputs differ by four, so their relative Fourier phase at y three is exp of two pi i times four times three over eight, which is negative one. Equal-magnitude contributions cancel.

2. The inverse of two modulo seven is four. Multiplying six by four gives twenty-four, congruent to three, so x is three. Zero has no multiplicative inverse modulo seven, so a zero first coordinate does not support this direct reconstruction.

Sources

Quantum factoring, discrete logarithms and the hidden subgroup problem develops the algebraic framework. The QFT and extensions of the Abelian HSP is a primary treatment of related Fourier methods and access issues.

Check your understanding

PAUSE & THINK

In the modulo-eight coset example, why is Fourier label three absent?

Choose your answer

Its two contributions have relative phase −1 and cancelIt is outside the registerEvery odd number is forbidden in every QFT

Check my answer

Answer: Its two contributions have relative phase −1 and cancel. The input separation is four, so the relative phase at label three is exp(2πi·4·3/8)=−1. This cancellation depends on the particular hidden subgroup.