Quantum part of the procedure to approximate the regulator R.

Follows the procedure described in [Jozsa 2003], Sec. 10. An adapted version of the Hidden Subgroup Problem (HSP) Algorithm is used to estimate the (irrational) period of the function f _N (fN, q_fN); this is the function h of [Jozsa 2003], Sec. 9, discretized with precision N = 2 ⁻ⁿ, and so has weak period S = NR. The precision n is determined by n_of_bigD.

Inputs: Δ; i, an assumed bound such that S ≤ 2ⁱ; and a random “jitter” parameter.

Attempt to approximate the regulator R, given an assumed bound i such that S ≤ 2ⁱ, using the probabilistic quantum computation approximate_regulator_circuit twice as described in [Jozsa 2003], Sec. 10.

Check the result for success; if it fails, return Nothing.

(The IO monad is slight overkill here: it is just to make a source of randomness available. A tighter approach could use e.g. a monad transformer such as RandT, applied to the Circ monad.)

verify_period_multiple Δ n m: check whether m is within 1 of a multiple of the period S of f_N.

Since for any ideal I, ρ(ρ(I)) is distance > ln 2 from I, it suffices to check whether the unit ideal is within 4 steps either way of f_N(m).

Approximate the regulator for a given Δ (bigD).

Repeatedly run try_approximate_regulator enough times, with increasing i, that it eventually succeeds with high probability.

Improve the precision of the initial estimate of the regulator R, for a quadratic discriminant Δ.

The implementation is essentially based on the proof of Theorem 5 of [Jozsa 2003].

A set of ideal classes generating CL(K).

Implementation: assuming the Generalized Riemann Hypothesis, it is enough to enumerate the non-principal prime ideals arising as factors of (p), for primes p ≤ 12(ln Δ)². ([Haase and Maier 2006], Prop. 4.4.) For each p, there are at most two such prime ideals, and they are easily described.

Compute the generators of CL(K), function hI.

Compute the ideals from the generators (ĝ function).

Compute i/N. Incomplete.

Compute register sizes for structure_circuit, given Δ and a precise estimate of R. Return a 7-tuple (q,1,2,3,4,5,6) where q is the size of the first k registers, and 1…6 are the sizes of registers k+1…k+6.

The quantum circuit used in computing the structure of CL(K), given Δ, a precise estimate of R, and a generating set for CL(K).

Compute the relations between a given set of reduced generators.

The full implementation of Hallgren’s algorithm.

class_number dd t: computes the class number |CL(K)| for Δ = dd, with success probability at least (1 - 1/2^t).