Quipper.Algorithms.CL.CL

An implementation of the quantum algorithms, based on the works of Hallgren, to compute the class number of a real quadratic number field.

Stage 1 (quantum): Approximate regulator to low precision

approximate_regulator_circuit :: CLIntP -> Int -> CLIntP -> Circ CInt

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.

try_approximate_regulator :: CLIntP -> Int -> IO (Maybe CLReal)

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 :: CLIntP -> Int -> CLInt -> Bool

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_regulator :: CLIntP -> IO CLReal

Approximate the regulator for a given Δ (bigD).

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

Stage 2 (classical): Compute the regulator more accurately.

improve_regulator_accuracy :: CLReal -> Integer -> CLReal

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

Stage 3 (classical): Find generators of the class group.

compute_generators :: CLIntP -> [IdealRed]

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.

Stage 4 (quantum): Find relations between generators.

Notation is as in [Hallgren 2006, Section 5]. Note: Some components are currently missing here, and are marked "incomplete" in the code below.

hI :: IdDist -> CLInt -> CLInt -> CLInt -> CLIntP -> CLIntP -> (IdDist, CLInt)

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

compute_ghat :: Integral int => [IdDist] -> [int] -> IdDist

Compute the ideals from the generators (ĝ function).

compute_i_N_at :: QDInt -> QDInt -> Circ ()

Compute i/N. Incomplete.

register_sizes :: CLIntP -> CLReal -> (Int, Int, Int, Int, Int, Int, Int)

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.

structure_circuit :: CLIntP -> CLReal -> [IdealRed] -> Circ [CInt]

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_relations :: CLIntP -> CLReal -> [IdealRed] -> IO [CLInt]

Compute the relations between a given set of reduced generators.

Section 5 (classical): compute class number.

class_number :: CLIntP -> Int -> IO CLInt

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