Finding a lattice of periods

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 states the extension and its cost together: "Most of the success in solving this problem has been for abelian groups, including finite abelian groups, $\mathbb{Z}$, $\mathbb{Z}^n$, and $\mathbb{R}$. In this paper we extend the hidden subgroup problem to work for $\mathbb{R}^r$." The gap between the integer and the real case is not a matter of constants — "While there is a straightforward solution of the HSP over $\mathbb{Z}^n$, this does not appear to be the case for $\mathbb{R}^r$" — and the limit is stated with its cause rather than as a bound: the 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". That is why the corpus records for both the unit group and the class group say *constant-degree* number field: the constant is the paper's, not ours.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  a constant-degree number field F, with unit rank r = s + t - 1 by
       Dirichlet's unit theorem (s real embeddings, t pairs of complex
       embeddings), r itself therefore held CONSTANT                (Sec. 2)
       problem size  n = log|Delta|  (Delta the field discriminant)  (Sec. 3.2)
       the target lattice  L = Log O* subset R^r,  the image of the unit
       group under the Log embedding  eps |-> (log|eps|_1, ..., log|eps|_r) (Sec. 2)
       a discretized oracle  f_N : Z^r -> I x Z^r  built from reduced-ideal
       computation, with  f(x) = f(y)  iff  x - y in L               (Sec. 3.1)
       # f_N is only known to be computable in poly time for CONSTANT-degree
       #   fields -- via Thiel's unpublished ideal-scanning Algorithm 6.2.20,
       #   or equivalently Schoof's "Scan" algorithm                 (Sec. 3.1)

requires  M = longest vector in a reduced basis of L
    N >= n^r * r^2 * M,  and N greater than 1/n times the minimum distance
        between reduced ideals
    q >= r^2 * M                                                     (Lemma 3.1)
    zero-padding constant  k >= 8r
    # k >= 8r is NOT restated in Lemma 3.1's printed statement; it comes from
    #   the phase bound the lemma's proof rests on, a few lines earlier, which
    #   the paper gives no equation number                            (Sec. 3.2)
    # these bounds are specific to reconstructing THIS lattice from a
    #   reduced-ideal oracle -- not a generic requirement of every HSP
    #   instance over R^r

# --- prepare a coset of L, sampled through the rounded oracle --------------
prepare  (1/sqrt(q^r)) * sum_{a in Z_q^r}  |a> |f_N(a)>
measure the oracle register -- collapses onto some fixed reduced ideal,
    leaving a superposition over one coset  k0 + L  of L inside [0,q)^r
state  ~  (1/sqrt(|L_q|)) * sum_{v in L, k0+v in [0,q)^r}  |rnd(N*(k0+v))>
    # rnd(.) rounds each coordinate up or down, the paper's own bracket
    #   notation [.] -- the sampled point APPROXIMATES N*v, it is not
    #   N*v itself, and this rounding is the source of the quantum-side
    #   noise discussed in the closing note                          (Sec. 3.2)
    # valid once q is large enough relative to M that the fraction of
    #   coset points near the cube boundary is exponentially small    (Sec. 3.2)

# --- zero-pad and Fourier sample the dual lattice ---------------------------
compute the QFT over the ENLARGED domain  Z_{q*N*k}^r,  not  Z_{q*N}^r
    # plain Fourier sampling over Z_{qN}^r "does not appear to be enough to
    #   recover the dual lattice"; the extra factor k must be a CONSTANT   (Sec. 3.2)
measure; keep the outcome  i in Z_{q*N*k}^r  only if every coordinate
    satisfies  |i_j| <= q*N*k/n,  else discard it                     (Lemma 3.1)
    # the paper prints this test WITHOUT absolute-value bars, as
    #   "i_j <= qNk/n" and "points with any coordinate greater than qNk/n
    #   are discarded"; the bars are the usable reading, since i encodes
    #   dual coordinates that can be negative -- the very next line of the
    #   paper writes |w_i| <= N/n + 1 WITH bars. Use |i_j|; the source
    #   text says i_j.                                                (Sec. 3.2, Lemma 3.1)

# --- repeat and extract a basis of the dual lattice -------------------------
repeat  a constant number of times                                    (Alg. 3.1, step 1a)
    # Algorithm 3.1 names no explicit repeat count. Lemma 3.1 gives a
    #   per-measurement success probability of at least 1/(8(nk)^r) that
    #   a kept point i/(qk) lands within 1/q of a point of L_perp.
    #   Separately, the proof of Theorem 1 shows that, conditioned on that
    #   success, the point lies in a subgroup that generates L_perp with
    #   probability at least 1/4 -- independent of n -- once N >= 4rM.
    # These are two different probabilities for two different questions. (Lemma 3.1; proof of Thm.
    #   1)
collect the surviving points  i/(qk),  each within 1/q of a point of L_perp
extract a basis B for L_perp from the resulting spanning set
    # "given a generating set, a basis can be computed" -- cites a separate
    #   reference, not re-derived here                                (Alg. 3.1, step 1b)

# --- dualize back to the unit lattice ----------------------------------------
compute  B^(-T)
    # this step additionally assumes L is WELL CONDITIONED, i.e. that
    #   ||B|| * ||B^-1|| is bounded -- the paper states this as a needed
    #   technical condition on the lattice, not something proved to hold  (Sec. 3.2)
    # inversion is numerically possible because det(L) >= 0.05, a bound
    #   taken from Thiel, so 1/det(L) does not blow up                    (Sec. 3.2)
return  the columns of B^(-T),  an approximate basis for L = Log O*        (Alg. 3.1, step 2)

verify  each returned vector is actually a unit; discard and repeat the
    whole procedure if the check fails                                    (Alg. 3.1, step 3)

# polynomial time is proved ONLY with r (equivalently the field degree)
#   held CONSTANT, and the paper names TWO obstacles to lifting that, not
#   one: "the quantum limitation of too much noise in Fourier sampling
#   because of the rounding of lattice vectors, AS WELL AS the classical
#   limitation of computing reduced ideals" -- the latter being the
#   constant-degree restriction on f_N noted in the given block above.
#   The rounding noise is the obstacle with no analogue in the integer-
#   lattice (Z^n) case. Arbitrary degree is left explicitly open  (Sec. 1)

Cost, as the source states it

Section 3.2 holds $r$, the dimension of the period lattice $L\subseteq\mathbb{R}^r$, fixed throughout: "an $r$ dimensional lattice $L$, where $r$ is a constant." Write $M$ for the longest vector in a reduced basis of $L$, $\Delta$ for the field's discriminant, and $n=\log|\Delta|$ for the problem size. Lemma 3.1 requires both $N\geq n^r r^2 M$ and $N$ greater than $1/n$ times the minimum distance between ideals, together with $q\geq r^2M$; the zero-padding factor $k\geq 8r$ comes not from the lemma's own statement but from the earlier phase bound it rests on. One Fourier sample over $\mathbb{Z}_{qNk}^r$ then lands within $1/q$ of a point of $L^\perp$ with probability at least $1/(8(nk)^r)$. Algorithm 3.1 draws "a constant number" of samples and names no count; Theorem 1's proof separately gives a per-sample probability of at least $1/4$, independent of $n$, once $N\geq 4rM$. Polynomial time in $n$ is proved only with $r$ fixed.

Implementations

• Quipper's Class Number algorithm in Haskell, stage 4 unfinished

  • Quipper: Concrete Resource Estimation in Quantum Algorithms

  The only source-code artefact I found for this method, and the entry earns its place by saying exactly how little of it exists. Quipper's CL, Class Number, was one of seven algorithms implemented in Quipper under IARPA's Quantum Computer Science program, and the QAPL report of that work describes it as approximating the class group of a real quadratic number field. Its own module header names the target as a real quadratic field $K = \mathbb{Q}(\sqrt{\Delta})$ specified by its discriminant, and says the implementation falls into five stages: stage 1 approximates the regulator with a quantum HSP algorithm, stages 2 and 3 refine that estimate and find a generating set for the class group classically, stage 4 computes relations between those generators, again using a version of the HSP algorithm, and stage 5 reads the group structure off a Smith normal form. Where the artefact belongs takes care, because Hallgren's Section 5 has two lattices in it and they are easy to weld into one. The hidden subgroup stage 4 looks for is the lattice of relations $H = \{(e_1,\ldots,e_m) : g_1^{e_1}\cdots g_m^{e_m} = \mathrm{id}\}$, a sublattice of $\mathbb{Z}^m$; this method's lattice is the other one, $\mathrm{Log}\,\mathcal{O}^{*}\subseteq\mathbb{R}^r$, and it enters because Section 5 can only evaluate that integer HSP's oracle by going through the unit group first — "start by computing the unit group of $F$, resulting in basis $B$" — since class-group elements are not known to have unique efficiently computable representatives. That is the ground the artefact is filed on, together with the corpus filing `class-group-of-a-number-field` under this method. What it never exercises is the machinery this method is named for: a real quadratic field has unit rank $r = s + t - 1 = 1$, so that lattice is one-dimensional, the ideals do sit on a line, and stage 4's entry point `structure_circuit` correspondingly takes the regulator as a scalar `CLReal` rather than as a basis. The implementation follows a detailed specification written for the program by Brian J. Matt, Durward McDonell and David Zaret, and the CL modules are credited to Keith Kim, Peter LeFanu Lumsdaine and Alexandr Virodov.

  Stage 4's circuit is `structure_circuit` in `Quipper/Algorithms/CL/CL.hs`. It initialises one register of $q$ qubits for each class-group generator and applies a Hadamard to each, initialises four further registers whose widths — like $q$ itself — are destructured from a single call to `register_sizes`, applies Hadamards to the distance register to superpose distances, measures and discards `reg_fIN`, applies `qft_int` to each generator register separately, and measures. That measurement is the step whose comment calls it "used to project the system", but with the evaluation step commented out `reg_fIN` still holds the zero it was initialised to and the measurement projects nothing. Between the Hadamards and it sit the six steps that would make this an oracle circuit, and none of them runs. Five are commented out and marked Incomplete: the application of `q_compute_ghat` that would compute the ideal from the exponent registers, the evaluation `q_fJN`, the erasure `erase_at`, the uncomputation `uncompute_i_N_at`, and the second `q_compute_ghat` that would uncompute the ideal. The sixth, `compute_i_N_at`, is the only one left uncommented, and it is declared with a full type signature over a body that is `error "incomplete"`. The comment above the Fourier transform is a question rather than a decision: it says the transform seems to be applicable per register and asks that this be checked, then asks separately whether the endianness is right. The classical side of the same stage is finished: `fJN` and `fJN_d` in `RegulatorClassical.hs` compute the analogue of $f_N$ working within the cycle determined by a given ideal $J$ — which the circuit's own comment identifies with the $f_{I,N}$ the quantum side is missing — cited in the source to Hallgren's Section 5, and `SmithReduction.hs` supplies the normal form stage 5 needs. `RegulatorQuantum.hs`, whose header says it implements the quantum operations required in stages 1 and 4, states in the third paragraph of that same header that the key functions for stage 4 are not yet implemented.

  No dataset. The input is a handful of numbers on a command line: the discriminant $\Delta$, whose default is 28, together with stage-4 parameters left at toy defaults — an approximate regulator of 12.345 and $q = 4$, $k = 3$, $n = 3$, $m = 5$ — plus the stage-1 bounds `-s` and `-i`, an optional generator list and a random seed. Everything else the circuit would need is computed rather than supplied: `compute_generators` enumerates, under the Generalized Riemann Hypothesis, the non-principal prime ideals arising as factors of $(p)$ for primes $p \leq 12(\ln\Delta)^2$, at most two per prime, following Proposition 4.4 of Haase and Maier. The shipped tests are classical throughout, and neither of the two testing routines touches a quantity stage 4 produced. `test_SNF` runs the stage-5 Smith normal form over three hard-coded sample matrices rather than over any relation matrix stage 4 computed, and `period_of_ideals` walks the cycle of reduced ideals for a given $\Delta$ by iterating $\rho$ until the unit ideal comes round again, reporting how many ideals that took and the sum of their distances. `Test.hs`'s own `main` calls neither of them: every line of it except `star_all_ideals 28` is commented out.

  The package is `quipper-algorithms`, and on 2026-08-27 its Hackage page listed exactly one version, 0.9.0.0, released — by the package's own ChangeLog — on December 29, 2019. The cabal file gives the licence as BSD3 with the text in COPYRIGHT, a three-clause BSD notice beginning "Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met", and that file also carries the IARPA funding acknowledgement and its disclaimer. Line counts read from that release on 2026-08-27: `CL.hs` 473, `RegulatorQuantum.hs` 504, `RegulatorClassical.hs` 417, `Types.hs` 639, `Auxiliary.hs` 482, `Main.hs` 395, `Test.hs` 227, `RegulatorTemplate.hs` 190, `SmithReduction.hs` 165, for 3,492 lines of Haskell across the nine CL modules. The README documents the `cl` executable's `-4` option as outputting the circuit for stage 4 of the algorithm; the function that option dispatches to, `main_stage4` in `Main.hs`, has a body of one `putStrLn` echoing the parsed options and nothing else. `structure_circuit`, `compute_relations` and `class_number` — the last being the driver that chains all five stages and hands the collected relations to the Smith normal form — appear nowhere outside `CL.hs`, so no command-line path in the shipped binary reaches any of them, and `programs/cl.hs` is a stub that re-exports `Quipper.Algorithms.CL.Main.main` and nothing more. A GitHub mirror last pushed in 2015, thephoeron/quipper-language, carries the same files under `Algorithms/CL/` with the same five Incomplete markers, the same `error "incomplete"`, and a `main_stage4` whose body is the same single `putStrLn`, so the state is not a regression introduced by the release: it is unchanged from at least 2015 through the 2019 version. The project homepage is Peter Selinger's Quipper page at Dalhousie.

  Nothing was run on quantum hardware and the package reports no simulator run. What the `cl` binary can actually produce is the stage-1 circuit and the individual subroutine circuits its `-S` option offers — rho, rhoinv, normalize, dotprod, starprod and fn — every one of them stage-1 machinery, with nothing from stage 4 on the list, plus three purely classical computations giving the regulator, the fundamental unit and the fundamental solution of Pell's equation for a given $\Delta$. The QAPL report's claim for all seven algorithms is hedged in the same direction: they are running, in the sense that one can generate the circuit and portion thereof. The single concrete count that report prints is for the triangle-finding algorithm, 30,189,977,982,990 total gates and 4676 qubits; it prints no gate count for CL. This record was written by reading the source, and the package was not built here, so what `cl -4` prints is read off the body of `main_stage4` rather than observed.

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.

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

In the Atlas

• The class group of a constant-degree number field

  The class group of a number field is the finite abelian group of ideals modulo principal ideals. Computing it means computing the structure of that abelian group, not merely its order.

• The unit group of a constant-degree number field

  The unit group of a number field is the set of invertible algebraic integers inside it. By Dirichlet's unit theorem it is, up to a root of unity, free abelian of a rank determined by the field's real and complex embeddings, so computing it means finding a fundamental system of units.

Sources

• Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field↗Sean Hallgren · 2005theory yes · simulation ? · hardware no