newsynth-0.4.1.0: Exact and approximate synthesis of quantum circuits

Safe HaskellNone
LanguageHaskell2010

Quantum.Synthesis.EuclideanDomain

Contents

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 where Source #

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

Methods

rank :: a -> Integer Source #

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 -> a infixl 7 Source #

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

euclid_div :: EuclideanDomain a => a -> a -> a infixl 7 Source #

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 -> a Source #

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 a Source #

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 -> Bool Source #

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

inv_mod :: EuclideanDomain a => a -> a -> Maybe a Source #

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 -> Bool Source #

Check whether a is a divisor of b.

euclid_associates :: EuclideanDomain a => a -> a -> Bool Source #

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 -> a infixl 7 Source #

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].