newsynth-0.2: Exact and approximate synthesis of quantum circuits

Quantum.Synthesis.EuclideanDomain

Description

This module provides a type class for Euclidean domains. A Euclidean domain is a ring with a notion of division with remainder, and therefore greatest common divisors.

Synopsis

# Euclidean domains

## Definition

class (Eq a, Ring a) => EuclideanDomain a whereSource

A type class for Euclidean domains. A Euclidean domain is a ring with a Euclidean function and a division with remainder.

Methods

rank :: a -> IntegerSource

The Euclidean function for the Euclidean domain. This is a function rank : R\{0} → ℕ such that:

• for all nonzero a, bR, rank(a) ≤ rank(ab);
• if b ≠ 0 and (q,r) = a `divmod` b, then either r = 0 or rank(r) < rank(b).

divmod :: a -> a -> (a, a)Source

Given a and b≠0, return a quotient and remainder for division of a by b. Specifically, return (q,r) such that a = qb + r, and such that r = 0 or rank(r) < rank(b).

## Functions

euclid_mod :: EuclideanDomain a => a -> a -> aSource

Calculate the remainder for the division of x by y. Assumes that y ≠ 0.

euclid_div :: EuclideanDomain a => a -> a -> aSource

Calculate the quotient for the division of x by y, ignoring the remainder, if any. This is typically, but not always, used in situations where the remainder is known to be 0 ahead of time. Assumes that y ≠ 0.

euclid_gcd :: EuclideanDomain a => a -> a -> aSource

Calculate the greatest common divisor in any Euclidean domain.

extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a)Source

Perform the extended Euclidean algorithm. On inputs x and y, this returns (a,b,s,t,d) such that:

• d = gcd(x,y),
• ax + by = d,
• sx + ty = 0,
• at - bs = 1.

euclid_inverse :: EuclideanDomain a => a -> Maybe aSource

Find the inverse of a unit in a Euclidean domain. If the given element is not a unit, return `Nothing`.

is_unit :: EuclideanDomain a => a -> BoolSource

Determine whether an element of a Euclidean domain is a unit.

inv_mod :: EuclideanDomain a => a -> a -> Maybe aSource

Compute the inverse of a in R/(p), where R is a Euclidean domain. Note: this works whenever a and p are relatively prime. If a and p are not relatively prime, return `Nothing`.

euclid_divides :: EuclideanDomain a => a -> a -> BoolSource

Check whether a is a divisor of b.

euclid_associates :: EuclideanDomain a => a -> a -> BoolSource

Check whether a and b are associates, i.e., differ at most by a multiplicative unit.

euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a)Source

Given elements x and y of a Euclidean domain, find the largest k such that x can be written as ykz. Return the pair (k, z).

If x=0 or y is a unit, return (0, x).

# Auxiliary functions

rounddiv :: Integral a => a -> a -> aSource

For y ≠ 0, find the integer q closest to x / y. This works regardless of whether x and/or y are positive or negative. The distance qx / y is guaranteed to be in (-1/2, 1/2].