The Quipper System

Safe HaskellNone

Algorithms.CL.RegulatorQuantum

Contents

Description

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 fN, 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 fI,N, analogues of fN 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].

Synopsis

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_d :: IdDistQ -> Circ (IdDistQ, IdDistQ) Source #

Apply the function ρ to an IdealQ together with a distance. See [Jozsa 2003], Sect 6.2, preceding Prop. 21; compare rho_d.

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

Apply the function ρ–1 to an IdealQ together with a distance. See [Jozsa 2003], Sec 6.2, preceding Prop. 21, and Sec 6.4; compare rho_inv_d.

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

As q_rho_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 IJ 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 IJ.

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

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

The function fN

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

q_fN Δ s n l qi j: find the minimal ideal-with-distance (JJ) such that δJ > x, where x = i/N + j/L, where N = 2n, L = 2l. qi is quantum; other inputs are classical parameters. Return (i,JJx). Work under the assumption that R < 2s.

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