The Quipper System

Safe Haskell None

Algorithms.CL.RegulatorQuantum

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

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

On distances, send δI to δI - log (l/ka).

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

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.

As q_rho_d, but for reduced ideals.

As q_rho_inv_d, but for reduced ideals.

# Products of ideals

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.

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

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.

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.