Safe Haskell | None |
---|

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

- approximate_regulator_circuit :: CLIntP -> Int -> CLIntP -> Circ CInt
- try_approximate_regulator :: CLIntP -> Int -> IO (Maybe CLReal)
- verify_period_multiple :: CLIntP -> Int -> CLInt -> Bool
- approximate_regulator :: CLIntP -> IO CLReal
- improve_regulator_accuracy :: CLReal -> Integer -> CLReal
- compute_generators :: CLIntP -> [IdealRed]
- hI :: IdDist -> CLInt -> CLInt -> CLInt -> CLIntP -> CLIntP -> (IdDist, CLInt)
- compute_ghat :: Integral int => [IdDist] -> [int] -> IdDist
- compute_i_N_at :: QDInt -> QDInt -> Circ ()
- register_sizes :: CLIntP -> CLReal -> (Int, Int, Int, Int, Int, Int, Int)
- structure_circuit :: CLIntP -> CLReal -> [IdealRed] -> Circ [CInt]
- compute_relations :: CLIntP -> CLReal -> [IdealRed] -> IO [CLInt]
- class_number :: CLIntP -> Int -> IO CLInt

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

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

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* ≤ 2^{i};
and a random “jitter” parameter.

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

Attempt to approximate the regulator *R*, given an assumed
bound *i* such that *S* ≤ 2^{i}, 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 Source #

:
check whether `verify_period_multiple`

Δ *n* *m**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*sub /N/.

approximate_regulator :: CLIntP -> IO CLReal Source #

Approximate the regulator for a given Δ (*bigD*).

Repeatedly run

enough times, with increasing
`try_approximate_regulator`

*i*, that it eventually succeeds with high probability.

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

improve_regulator_accuracy :: CLReal -> Integer -> CLReal Source #

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

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

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.