SlotLayer 0
Recover the period of a periodic function
Given a function you can evaluate in superposition and a promise that it repeats, find what it repeats by. This is the engine underneath factoring, discrete logarithms and a row of classical number-theory problems that had no efficient algorithm at all — and the whole difficulty is that the period is read out of an interference pattern rather than looked up.
A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted.
The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
This one, drawn
From Function promised to be periodic to The period, recovered
A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.
Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map
Why this is a layer
The routes here are separated by **what kind of thing the period is allowed to be**, and that is a difference in what is possible rather than in cost. Hallgren states it against Shor directly: the structure behind Pell's equation is "a group-like subset of the reals modulo an irrational number", and "this prevents direct application of Shor's algorithms" — an irrational period cannot be written down, so the continued-fraction step that finishes the integer route has nothing to finish. Going from one irrational period to a lattice of them costs again, and for a stated reason: the lattice method "only appears to work for a constant number of dimensions because the rounding introduces new noise into the distribution that is not present in the integer lattice case". So a claim that a problem "reduces to period finding" has said nothing until it says which of the three. The wider family these belong to is the **hidden subgroup problem**, which is deliberately not drawn as a node beside them: it also contains instances with no period interpretation at all — Hallgren names graph isomorphism as one of the "still unsolved problems" it covers — so a node for it would be a family standing beside three of its own members.
Ways to do this
3 methods recorded
- Period finding in a finite cyclic group
Evaluate the function across a superposition of exponents, transform the input register, and measure. What comes back is a multiple of the sample size divided by the period, near enough that a continued-fraction expansion recovers the period exactly — and once it is exact it can be checked classically, so the whole quantum part may fail and be retried.
- Period finding over the reals
When the period is irrational there is no exact answer to land on, so the function is evaluated on a discretisation of the reals and the period is approximated instead. Two samples are taken rather than one, and the continued-fraction step runs on their ratio — the same idea as the integer route, doing a job the integer route cannot do at all.
- Finding a lattice of periods
Some functions repeat in several independent directions at once, so what is hidden is not one period but a lattice of them. Sampling the dual lattice and reconstructing a basis from the samples replaces the continued fraction, and the rounding that makes real-valued directions representable is what limits how many directions can be handled.
Routes that skip this layer
No recorded route avoids this step.
This is a step inside
Nothing in this graph needs this as a step, so it is where a reading starts.
In the Atlas
- Zeta function of a curve over a finite field
Given a curve C of genus g over a finite field F_q, compute the numerator P(t) of its zeta function Z(C,t) = P(t)/((1−t)(1−qt)), a polynomial of degree 2g with integer coefficients, in time polynomial in g and log q jointly rather than in one at the expense of the other.
- Ideals in a finite black-box ring
Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I.