The Quipper System

Algorithms.CL.RegulatorClassical

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 bigD l: the unit ideal O, for Δ = bigD, with the ideal’s coefficients given as l-bit integers. ([Jozsa 2003], Prop. 14.)

Like unit_ideal, but considered as a reduced ideal.

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

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

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

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

The ρ operation on reduced ideals.

The ρ–1 operation on reduced ideals.

The ρ operation on ideals-with-distance.

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 an ideal, by repeatedly applying ρ.

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

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.

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

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.

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

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

Uses IdDist and rho_d.

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

Uses '(Ideal,Number)' and rho_num.

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.

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.