Safe Haskell | None |
---|

This module implements the specialized quantum operations required in stages 1 and 4 of Hallgren’s algorithm.

The key operation for stage 1 is `q_fN`

, implementing *f*_{N}, the quasi-periodic
function used in approximating the regulator. This is the function *h* of
[Jozsa 2003], Sec. 9, discretized with precision 1/*N* and translated by a
specified jitter parameter.

The key functions for stage 4 are not yet implemented. These essentially
consist of the functions *f*_{I,N}, analogues of *f*_{N} operating
within the equivalence classes of possibly non-principal ideals *I* (representing
other elements of the class group), as described in [Hallgren 2006, Section 5].

- q_normalize :: IdDistQ -> Circ (IdDistQ, IdDistQ)
- q_rho_d :: IdDistQ -> Circ (IdDistQ, IdDistQ)
- q_rho_inv_d :: IdDistQ -> Circ (IdDistQ, IdDistQ)
- q_rho_red_d :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ)
- q_rho_inv_red_d :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ)
- q_dot_prod :: IdealRedQ -> IdealRedQ -> Circ (IdealRedQ, IdealRedQ, IdealQ)
- q_dot_prod_with_dist :: IdRedDistQ -> IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ, IdDistQ)
- q_star_prod :: IdRedDistQ -> IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ, IdRedDistQ)
- q_star_square :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ)
- q_fN :: CLIntP -> Int -> Int -> QDInt -> IntM -> Circ (QDInt, (IdealRedQ, FPRealQ))

# Basic operations on ideals

q_normalize :: IdDistQ -> Circ (IdDistQ, IdDistQ) Source #

Send *I* = <*k*,*l*,*a*,*b*> to *l*/*ka* *I* = <1,*a*,*a*,*b*>.

On distances, send δ_{I} to δ_{I} - log (*l*/*ka*).

q_rho_red_d :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ) Source #

As `q_rho_d`

, but for reduced ideals.

q_rho_inv_red_d :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ) Source #

As `q_rho_inv_d`

, but for reduced ideals.

# Products of ideals

q_dot_prod :: IdealRedQ -> IdealRedQ -> Circ (IdealRedQ, IdealRedQ, IdealQ) Source #

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

This is *I*⋅*J* of [Jozsa 2003], Sec 7.1, following the description
given in Prop. 34.

q_dot_prod_with_dist :: IdRedDistQ -> IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ, IdDistQ) Source #

Compute the dot-product of two reduced fractional ideals, all with distance.

q_star_prod :: IdRedDistQ -> IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ, IdRedDistQ) Source #

Given two reduced ideals-with-distance, compute their star-product, with distance.

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

q_star_square :: IdRedDistQ -> Circ (IdRedDistQ, IdRedDistQ) Source #

Compute *I* * *I*, where *I* is a reduced ideal/distance pair.

# The function f_{N}

q_fN :: CLIntP -> Int -> Int -> QDInt -> IntM -> Circ (QDInt, (IdealRedQ, FPRealQ)) Source #

: find the minimal ideal-with-distance (`q_fN`

Δ *s* *n* *l* *qi* *j**J*,δ_{J}) such that δ_{J} > *x*, where *x* = *i*/*N* + *j*/*L*, where *N* = 2^{n}, *L* = 2^{l}. *qi* is quantum; other inputs are classical parameters. Return (*i*,*J*,δ_{J}–*x*). Work under the assumption that *R* < 2^{s}.

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