The Quipper System

Safe HaskellNone

Algorithms.CL.RegulatorClassical

Contents

Description

This module implements the classical operations on ideals used in Hallgren’s algorithm (including also classical versions of the quantum operations required).

Synopsis

Basic operations on ideals

unit_ideal :: CLIntP -> Ideal Source #

unit_ideal bigD l: the unit ideal O, for Δ = bigD, with the ideal’s coefficients given as l-bit integers. ([Jozsa 2003], Prop. 14.)

unit_idealRed :: CLIntP -> IdealRed Source #

Like unit_ideal, but considered as a reduced ideal.

c_of_ideal :: Ideal -> CLInt Source #

The integer constant c of an ideal. ([Jozsa 2003], page 14 bottom: "Since 4a divides b2-D (cf. proposition 16) we introduce the integer c = |Db2|/(4a)")

gamma_of_ideal :: Ideal -> AlgNum Source #

γ(I) = (b+√Δ)/(2a) for a given ideal I. ([Jozsa 2003], Sec. 6.2.)

rho :: Ideal -> Ideal Source #

The reduction function ρ on ideals. ([Jozsa 2003], Sec. 6.2.)

rho_inv :: Ideal -> Ideal Source #

The ρ-1 function on ideals. Inverse to rho. ([Jozsa 2003], Sec. 6.4.)

rho_red :: IdealRed -> IdealRed Source #

The ρ operation on reduced ideals.

rho_inv_red :: IdealRed -> IdealRed Source #

The ρ–1 operation on reduced ideals.

rho_d :: IdDist -> IdDist Source #

The ρ operation on ideals-with-distance.

rho_inv_d :: IdDist -> IdDist Source #

The ρ–1 operation on ideals-with-distance.

rho_num :: (Ideal, AlgNum) -> (Ideal, AlgNum) Source #

The ρ operation on ideals-with-generator (i.e. pairs of an ideal I and an AlgNum x such that I is the principal ideal (x)).

rho_red_num :: (IdealRed, AlgNum) -> (IdealRed, AlgNum) Source #

Apply ρ to an reduced-ideals-with-generator

Ideal reductions (bounded)

reduce :: Ideal -> IdealRed Source #

Reduce an ideal, by repeatedly applying ρ.

bounded_reduce :: IdDist -> IdDist Source #

Reduce an ideal within a bounded loop. Applies the ρ function until the ideal is reduced. Used in star and fJN algorithms.

bounded_step :: (IdDist -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist Source #

Apply a function (like ρ,ρ-12) to an ideal, bounded by 3*ln(Δ)/2*ln(2). Execute while satisfies condition function.

bounded_step_delta :: (CLReal -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist Source #

Like bounded_step, but the condition is checked against delta of the current ideal.

Products of ideals

dot :: IdDist -> IdDist -> IdDist Source #

The ordinary (not necessarily reduced) product of two reduced fractional ideals.

IJ of [Jozsa 2003], Sec 7.1, following the description given in Prop. 34.

dot' :: IdDist -> IdDist Source #

The dot-square II of an ideal-with-distance I.

star :: IdDist -> IdDist -> IdDist Source #

The star-product of two ideals-with-distance.

This is I*J of [Jozsa 2003], Sec. 7.1, defined as the first reduced ideal-with-distance following IJ.

The function fN, and variants

compute_injl :: Integral int => CLInt -> int -> CLInt -> int -> CLReal Source #

Compute the expression i/N + j/L.

fN :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (Ideal, CLInt) Source #

fN i j n l Δ: find the minimal ideal-with-distance (JJ) such that δJ > x, where x = i/N + j/L, where N = 2n, L = 2l. Return (i,JJx). Work under the assumption that R < 2s.

This is the function h of [Jozsa 2003, Section 9], discretized with precision 1/N = 2n, and perturbed by the jitter parameter j/L.

fN_d :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (IdDist, CLInt) Source #

Like fN, but returning an ideal-with-distance not just an ideal.

fJN :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (Ideal, CLInt) Source #

Analogue of fN, working within the cycle determined by a given ideal J. ([Hallgren 2006], Section 5.)

fJN_d :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (IdDist, CLInt) Source #

Like fJN, but returning an ideal-with-distance not just an ideal.

Classical period-finding

Functions for classically finding the regulator and fundamental unit of a field using the period of f_N.

Auxiliary functions

order :: Eq a => (a -> a) -> a -> Int Source #

Find the order of an endofunction on an argument. That is, order f x returns the first n > 0 such that fsup /n/ = x.

Method: simple brute-force search/comparison.

order_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> Int Source #

Given a function p, an endofunction f, and an argument x, returns the first n > 0 such that p(fsup /n/) = p(x).

Method: simple brute-force search/comparison.

first_return_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> a Source #

Given a function p, an endofunction f, and an argument x, return fsup /n/, for the first n > 0 such that p(fsup /n/) = p(x).

Method: simple brute-force search/comparison.

first_return_with_proj_bdd :: Eq b => Int -> (a -> b) -> (a -> a) -> a -> Maybe a Source #

Given a bound b, a function p, an endofunction f, and an argument x, return fsup /n/, for the first n > 0 such that p(fsup /n/) = p(x), if there exists such an nb.

Method: simple brute-force search/comparison.

period :: (Eq a, Integral int) => (int -> a) -> int Source #

Find the period of a function on integers, assuming that it is periodic and injective on its period. That is, period f returns the first n > 0 such that f(n) = f(0). Method: simple brute-force search/comparison.

Haskell native arithmetic

The functions of this section use Haskell’s native integer and floating computation.

regulator :: CLIntP -> FPReal Source #

Find the regulator R = log ε0 of a field, given the discriminant Δ, by finding (classically) the order of ρ.

Uses IdDist and rho_d.

fundamental_unit :: CLIntP -> AlgNum Source #

Find the fundamental unit ε0 of a field, given the discriminant Δ, by finding (classically) the order of ρ.

Uses '(Ideal,Number)' and rho_num.

fundamental_solution :: CLIntP -> (Integer, Integer) Source #

Find the fundamental solution of Pell’s equation, given d.

Solutions of Pell’s equations are integer pairs (x,y) such that x,y > 0, and (x + y√d)(xy√d) = 1.

In this situation, (x + y√d) is a unit of the algebraic integers of K, and is >1, so we simply search the powers of ε0 for a unit of the desired form.

Fixed-precision arithmetic

The functions of this section perform period-finding using fixed-precision arithmetic. This should parallel closely (though at present not exactly, due to the implementations of floating-point operations) the quantum circuit implementations, and hence allows testing of whether the chosen precisions are accurate.

regulator_fixed_prec :: Int -> CLIntP -> Maybe FPReal Source #

Find the regulator R = log ε0 of a field, given the discriminant Δ, by finding (classically) the order of ρ using fixed-precision arithmetic: fix_sizes_Ideal for Ideals, and given an assumed bound b on log2 R.

Uses IdDist and rho_d.