Assert that a condition is true, otherwise throwing an error with a given error message, in a functional setting.

Assert a condition, imperatively in a monad.

Given a list of monadic actions and a predicate on their results, do the actions in sequence until one produces a result satisfying the predicate; return this result.

Test whether elements of a list are all equal

Apply a function to data while condition holds true. For example:

while (not . isReduced . fst) rho ideal

will apply the function rho to an ideal-with-distance while it is not yet reduced (until it is reduced).

Like while, but with a known bound on number of iterations. This construct can be converted to a quantum circuit, while a general unbounded while cannot be lifted.

A bounded version of Haskell iterate function that produces an infinite list. This function produces a finite bounded list.

Generate primes using the Sieve of Eratosthenes. Straightforward implementation - when a prime is found, filter all of its multiples out of the already filtered list. This implementation may eventually blow out of stack, but it should grow with the number of primes, which seems to be O(log log n).

Generate primes up to a given number. See implementation of primes for details.

Check if a number is square-free (by brute force).

Compute the Jacobi symbol. The definition and algorithm description is taken from http://en.wikipedia.org/wiki/Jacobi_symbol.

mod_with_max x y max: reduce x modulo y, returning the unique representative x' in the range max – y < x' ≤ max.

Integer division with asserts making sure that the denominator indeed divides the numerator.

extended_euclid a b: return (d,x,y), such that d = gcd(a,b), and ax + by = d.

a divides b: return True if a divides b.

Test whether a real number is an integer.

Generate the list of integers describing the continued fraction of a given rational number. Since the number is rational, the expansion is finite.

Each rational number q is equal to a unique expression of the form

where n ≥ 0, a₀ is an integer, a₁, …, a_n are positive integers, and a_n ≠ 1 unless n=0. This is called the (short) continued fraction expansion of q. The function continued_list inputs two integers num and denom, computes the continued fraction expansion of q = num / denom, and returns the non-empty sequence [a₀, …, a_n].

Generate a list of convergents from a continued fraction (as described by the non-empty list of integers of that fraction).

Unimplemented components need to be given as black boxes — like named gates, except their types may not just be an endomorphism; like subroutines, except with only a placeholder on the inside.

For this module, black boxes are only needed for classical functional routines, i.e. with type qa -> Circ (qa, qb)

Like box, but prepends "Arith." to subroutine names, as a crude form of namespace management.

Boxed analogue of q_ext_euclid.

Boxed analogue of q_add.

Boxed analogue of q_mult.

Boxed analogue of q_div_exact.

Boxed analogue of q_add_in_place.

Boxed analogue of q_add_param_in_place.

Boxed analogue of q_div.

Boxed analogue of q_mult_param.

Boxed analogue of q_mod_unsigned.

Boxed analogue of q_sub_in_place.

Boxed analogue of q_increment.

Turn a QDInt into an FPRealQ, with shape specified by another FPRealQ

Divide a QDInt by 2, in place. (Behavior on odd integers: so far, not required.) As this is not required on odd integers, we can assume that the least significant bit is 0, and use an operation equivalent to a right rotate, instead of a right shift. This can be achieved by changing the list indices within the QDInt, and not a quantum operation, but this operation is *NOT* controllable.

Square a QDInt. This is achieved by creating a copy of the input, using the out of place multiplier, and then uncopying the input.

Test whether a QDInt is (strictly) greater than a parameter IntM.

Test whether a QDInt is greater than or equal to a parameter IntM.

q_mod_semi_signed x y: reduce x modulo y. x is treated as signed, y as unsigned.

Note: not non-linear safe in x.

q_mod_with_max x y m: reduce x modulo y, into the range max – y < x' ≤ max. (Compare mod_with_max.)

Obsolete function, retained for testing since it evokes a subtle bug in with_computed.

Perform a bounded while loop, whose body may produce extra output.

Perform a bounded-length while loop, with an endo-typed body.

Note: uses 2 * bound ancillas. Can this be avoided?

Perform a bounded while loop, whose body may produce extra output.

Perform a bounded “do_until” loop.