The Quipper System

Algorithms.CL.CL

Description

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

Synopsis

# Stage 1 (quantum): Approximate regulator to low precision

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 n, and so has weak period S = NR. The precision n is determined by n_of_bigD.

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

Attempt to approximate the regulator R, given an assumed bound i such that S ≤ 2i, 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 fN.

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 fsub /N/.

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

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 Δ)2. ([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) Source #

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

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

Compute the ideals from the generators (ĝ function).

Compute i/N. Incomplete.

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

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] Source #

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] Source #

Compute the relations between a given set of reduced generators.

# Section 5 (classical): compute class number.

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/2t).