Integers that may be passed into or received out of quantum computations.

Integers that will be used for parameter computation only, potentially large.

Rational numbers for the Class Number code.

Real numbers for the Class Number code.

Compute Δ, given d. (See [Jozsa 2003], Prop. 6 et seq. We use Δ, or in code bigD, where Jozsa uses D.)

Compute d, given Δ. (Again, see [Jozsa 2003], Prop. 6 et seq.)

Check if d is a valid input to Hallgren’s algorithm, i.e. correctly defines a real quadratic number field.

Check if Δ is a valid input to Hallgren’s algorithm, i.e. is the discriminant of a real quadratic number field. (Cf. http://en.wikipedia.org/wiki/Fundamental_discriminant)

The (infinite, lazy) list of all valid inputs d, i.e. of all square-free integers above 2.

The (infinite, lazy) list of all valid inputs Δ, i.e. of all discriminants of real quadratic number fields.

A data type describing a number in the algebraic number field K = ℚ[√Δ]: AlgNumGen a b Δ represents a + b√Δ.

In general, the type of coefficients may be any type of (classical or quantum) numbers, i.e. an instance of the Num or QNum class. Given this, the algebraic numbers with a fixed Δ will in turn be an instance of Num or QNum.

A value a :: x may also be used as an AlgNumGen x, with no Δ specified, to represent simply a + 0√Δ; this can be considered polymorphic over all possible values of Δ.

This is similar to the use of IntMs or FPReals of indeterminate size, although unlike for them, we do not restrict this to the classical case. However, the question of whether an AlgNumGen has specified √Δ is (like e.g. the length of a list) is a parameter property, known at circuit generation time, not a purely quantum property.

The specific instance of AlgNumGen used for classical (parameter) computation.

Extract the first co-ordinate of an AlgNumGen

Extract the second co-ordinate of an AlgNumGen

Print an algebraic number in human-readable (though not Haskell-readable) format, as e.g. a + b√Δ.

Realize an algebraic number as a real number (of any Floating type).

Coerce one algebraic number into the field of a second, if possible. If not possible (i.e. if their Δ’s mismatch), throw an error.

The algebraic conjugate: sends a + b √Δ to a - b √Δ.

Test whether an algebraic number is an algebraic integer.

(A number is an algebraic integer iff it can be written in the form m + n(Δ + √Δ)/2, where m, n are integers. See [Jozsa 2003], proof of Prop. 14.)

Test whether an algebraic number is a unit of the ring of algebraic integers.

The number ω associated to the field K.

Data specifying an ideal in an algebraic number field. An ideal is described by a tuple (Δ,m,l,a,b), representing the ideal

m/l (aZ + (b+√Δ)/2 Z),

where moreover we assume and ensure always that the ideal is in standard form ([Jozsa 2003], p.11, Prop. 16). Specifically,

• a,k,l > 0;
• 4a | b² – Δ;
• b = τ(a,b);
• gcd(k,l) = 1

In particular, this gives us bounds on the size of a and b, and hence tells us the sizes needed for these registers (see length_for_ab below).

Classical parameter specifying an ideal.

Quantum circuit-type counterpart of IdealX.

Classical circuit-type counterpart of IdealX.

Data specifying a reduced ideal, by a tuple (Δ,a,b); this corresponds to the ideal specified by (Δ,1,a,a,b), i.e., Z + (b+√Δ)/2a Z.

Classical parameter specifying a reduced ideal.

Quantum circuit-type counterpart of IdealRedX.

Classical circuit-type counterpart of IdealRedX.

An ideal I, together with a distance δ for it — that is, some representative, mod R, for δ(I) as defined on G p.4. Most functions described as acting on ideals need in fact to be seen as a pair of an ideal and a distance for it.

Quantum analogue of IdDist.

A reduced ideal I, together with a distance δ for it.

Quantum analogue of IdRedDist.

Extract the d component from an IdealQ.

Extract the d component from an IdealRedQ.

Extract Δ from an IdealQ.

Extract Δ from an IdealRedQ.

Extract the delta part from an ideal/distance pair.

tau Δ b a: the function τ(b,a). Gives the representative for b mod 2a, in a range dependent on a and √Δ.

(This doesn't quite belong here, but is included as a prerequisite of the assertions).

Return True if the given ideal is in standard form. (Functions should always keep ideals in standard form).

Test whether an IdealX is reduced. (An ideal <m,l,a,b> is reduced iff m = 1, l = a, b ≥ 0 and b + √Δ > 2a ([Jozsa 2003], Prop. 20)).

Test whether an IdealRedX is really reduced. (An ideal <1,a,a,b> is reduced iff b ≥ 0 and b + √Δ > 2a ([Jozsa 2003], Prop. 20)).

Coerce an IdealRedX to an IdealX.

Coerce an IdealX to an IdealRedX, if it is reduced, or throw an error otherwise. Cf. [Jozsa 2003], Prop. 20.

Throw an error if an IdealX is not reduced; otherwise, the identity function.

Throw an error if an IdealRedX is not really reduced; otherwise, the identity function.

Quantum analogue of tau. q_tau Δ qb qa: compute the representative for qb mod 2qa, in a range dependent on qa and √Δ.

Test whether a given IdealQ is reduced. <m,l,a,b> is reduced iff m = 1, l = a, b ≥ 0 and b + √Δ > 2a ([Jozsa 2003], Prop. 20).

Test whether a given IdealQ is really reduced (as it should always be, if code is written correctly). An ideal <1,a,a,b> is reduced iff b ≥ 0 and b + √Δ > 2a ([Jozsa 2003], Prop. 20).

Coerce an IdealRedQ to an IdealQ, initializing the extra components appropriately.

Coerce an IdealQ to an IdealRedQ, assertively terminating the extra components (and hence throwing an error at quantum runtime if the input is not reduced).

Throw a (quantum-runtime) error if an IdealRedQ is not really reduced; otherwise, do nothing.

Compare assert_reduced, q_is_really_reduced in Quipper.Algorithms.CL.RegulatorQuantum, and [Jozsa 2003] Prop. 20.

Given Δ, return the size of integers to be used for the coefficients a, b of reduced ideals.

Note: can we bound this more carefully? In reduced ideals, we always have 0 ≤ a,b ≤ √Δ (see notes on is_standard, is_reduced), and the outputs of ρ, ρ^–1 and dot-products of reduced ideals always keep |a| ≤ Δ. However, intermediate calculations may involve larger values, so we allocate a little more space. For now, this padding is a seat-of-the-pants estimate.

Given Δ, return the size of integers to be used for the coefficients m, l of general ideals.

TODO: bound this! Neither Hallgren nor [Jozsa 2003] discusses bounds on the values of m and l that will appear, and we do not yet have a bound. For now we use the same length as for a and b, for convenience; this should be considered a dummy bound, quite possibly not sufficient in general.

Given Δ, return the precision n = log₂N to be used for discretizing the quasi-periodic function f to f_N.

(“Precision” here means the number of binary digits after the point).

Taken to ensure 1/N < 3/(32 Δ log Δ). (Cf. [Jozsa 2003], Prop. 36 (iii).)

Given Δ, n, l (as for fN, q_fN), return the precision required for intermediate distance calculations during the computation of f_N.

TODO: bound this more carefully. [Jozsa 2003] asks for the final output to be precision n, but does not discuss intermediate precision, and we have not yet got a confident answer. For now, just a back-of-the-envelope estimate, which should be sufficient and O(correct), but is almost certainly rather larger than necessary.

Set the IntM coefficients of an IdealX to the standard lengths, if they are not already fixed incompatibly. The standard lengths are determined by length_for_ml, length_for_ab. (Compare intm_promote, etc.)

Set the IntM coefficients of an IdealRedX to the standard lengths, if they are not already fixed incompatibly. The standard lengths are determined by length_for_ml, length_for_ab. (Compare intm_promote, etc.)