MethodLayer 0
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.
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.
Same contract as the slot it fills.
This one, drawn
From Function promised to be periodic to The period, recovered
A circle is an object you are holding. This method is drawn heavier, opened into its own steps; the other lines between the same two ends are the alternatives recorded for the same slot. 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
What it fills
- 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.
When it applies
Hallgren is explicit that this is a different method and not a re-run of Shor's: the principal ideal problem "reduces to a discrete log type problem, but there is no longer an underlying group. Instead, a group-like subset of the reals modulo an irrational number is used. This prevents direct application of Shor's algorithms." He names the technique and its limit in the same breath — "Fourier sampling can only be performed over finite groups... In this work we extend Fourier sampling to non-finitely generated groups, as there will be an underlying periodic function over the reals whose period we wish to approximate" — and states where the new difficulty sits: "The general idea for the algorithm is the same as in Shor's discrete log algorithm, but we have new technical difficulties because we are computing modulo an irrational number."
Requires
Every step this method names moves its route along, so there is nothing it needs alongside them.
Example
given f : Z -> X, epsilon-pseudo-periodic with real period S (Def. 3.1)
# f(k) = f(k + [iS]) for at least an epsilon-fraction of offsets
# k in {0, ..., floor(S)}, where [iS] means iS rounded down OR up --
# the discretisation this method needs because S is irrational and
# no q makes f exactly periodic on any finite grid
f injective across that epsilon-fraction of pseudo-periodic offsets (Alg. 3.1, Input)
verify(T), an efficient procedure that accepts when T is within 1
of S, or within 1 of an integer multiple of S (Def. 3.2)
an upper bound M on S (Alg. 3.1, Input)
# verify() is ASSUMED, not built: the paper takes it "for the sake of
# simplicity", noting one exists in the Section 3.2 application (Sec. 3.1)
requires S greater than some absolute constant -- below it the success
probability this method relies on is not claimed to hold. The lemma
states no numeric value for that constant; the log M >= 262 that
appears in Claim 3.1 is an interior step of the proof, not a stated
precondition of the method (Lemma 3.1)
# --- fix a modulus large enough to resolve S from the samples --------------
choose an integer q >= 3*M^2 (Alg. 3.1, step 1)
# the proof needs q >= 3*S^2 for the continued-fraction bound and
# q >= S^2 for the final rounding bound; M >= S makes step 1 cover
# both, which is the only reason the bound M is required at all (Lemma 3.1, proof)
# --- Fourier sample f twice over Z_q ---------------------------------------
c = Fourier-sample f over Z_q
d = Fourier-sample f over Z_q (Alg. 3.1, step 2)
# each sample lands within 1/2 of an unknown integer multiple of the
# irrational q/S: c = round(k*q/S), d = round(l*q/S), for unknown
# integers k <= l <= S
# one sample alone is useless: the multiple is unknown. Dividing the two
# cancels q/S and leaves k/l; dividing c back by k then returns q/S
# itself, and S with it (Sec. 3.1)
# --- recover k from the continued fraction of the ratio --------------------
expand c/d as a continued fraction, with convergents k_i/l_i (Alg. 3.1, step 3)
# written k_i/l_i here rather than the paper's own c_i/d_i, so the names
# do not collide with the samples c and d -- one of which the next
# line needs by name
# k/l is a convergent of c/d whenever |c/d - k/l| <= 1/(2*l^2), which
# q >= 3*S^2 secures (Lemma 3.1, proof)
for each convergent k_i/l_i:
candidate = round(k_i * q / c) (Alg. 3.1, step 4)
# nearest integer. The denominator is the FIRST Fourier sample c --
# one fixed integer, the same for every convergent -- not the
# convergent's own denominator l_i. Only the numerator k_i is
# taken from the convergent; l_i serves only to pick it out
# this is the quantity the correctness bound is proved for:
# if c = round(k*q/S) and q >= S^2 then |S - round(k*q/c)| <= 1 (Lemma 3.1, proof)
if verify(candidate):
keep candidate
return the smallest kept candidate (Alg. 3.1, step 5)
# an integer within 1 of S, in time polynomial in log S -- an
# approximation, not S exactly, since S is irrational and there is no
# integer to land on (Lemma 3.1)
# succeeds with probability Omega(epsilon^2 / (log M)^4) per attempt.
# The three events priced there: f is pseudo-periodic at the measured
# offset (probability epsilon, twice over), both samples fall below
# q/log M, and k, l are relatively prime (Lemma 3.1, proof)
# that per-attempt figure is far below 1. Repetition is what boosts it,
# but Lemma 3.1 itself does not say so -- the boosting statement is
# made for the regulator application, where polynomially many
# repetitions in log Delta push correctness exponentially close to 1 (Sec. 3.2, Thm. 2 proof)
# if M is not known in advance: start at M = 2, and each time the answer is
# wrong, double the bound and rerun -- a correct bound is reached, and
# this method then returns correctly, within a number of doublings
# polynomial in log S (Sec. 3.1)
# turning the returned period into a regulator or an ideal's distance is a
# separate construction, not part of this primitive: the application
# builds its own pseudo-periodic f_N on the reals and takes N >= 2*sqrt(Delta)
# to make f_N 1/2-pseudo-periodic with period N*R (Lemma 3.2)
# note that q is NOT re-derived against the discriminant there. Its only
# stated constraint anywhere is step 1's q >= 3*M^2, tied to Delta only
# indirectly, through M as a bound on the period N*R (Sec. 3.1)Cost, as the source states it
Lemma 3.1 prices Algorithm 3.1 itself: given an upper bound on the period, it returns an integer within 1 of the period in time polynomial in . That is a per-attempt figure — the success probability recorded above, with the fraction of offsets on which the function is pseudo-periodic, is far below one, so the run has to be repeated. Section 3.2 says what is for Pell's equation: approximating the regulator of the order of discriminant becomes approximating the period of a function , for an integer taken large enough relative to , and polynomially many repetitions in push the probability of correctness exponentially close to 1. Theorem 2 is the proved end-to-end statement: the regulator to within , in time polynomial in and .
Implementations
Nobody has written one up yet. That is a gap in this record, not a statement that the method has never been run — the paper register already records, per paper, which sources report numerics or a hardware run.
Where the claim is contested
Hallgren's later paper calls this a special case of the next method rather than a parallel one: "Solving Pell's equation is a special case of the more general problem of finding the unit group of a number field." The two are kept as separate nodes because the techniques are separably hard rather than nested — the rank-1 construction here does not generalise on its own, and the lattice route needed new machinery for the rounding noise that appears only in higher rank. A reader should hold both facts: mathematically one contains the other, and as algorithms they were solved apart.
What it needs
Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.
Other ways to fill the same slot
Different approaches
- 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.
- 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.
In the Atlas
- Pell's equation by computing the regulator
Given a positive non-square integer d, Pell's equation is x² − dy² = 1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R = ln(x₁ + y₁√d), from which the solution can be recovered.
- The principal ideal problem in a real quadratic field
Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α.