newsynth-0.3.0.2: Exact and approximate synthesis of quantum circuits

Quantum.Synthesis.Ring

Description

This module provides type classes for rings. It also provides several specific instances of rings, such as the ring ℤ₂ of integers modulo 2, the ring ℚ of rational numbers, the ring ℤ[½] of dyadic fractions, the ring ℤ[i] of Gaussian integers, the ring ℤ[√2] of quadratic integers with radix 2, and the ring ℤ[ω] of cyclotomic integers of degree 8.

Synopsis

# Rings

class Num a => Ring a Source

A type class to denote rings. We make `Ring` a synonym of Haskell's `Num` type class, so that we can use the usual notation `+`, `-`, `*` for the ring operations. This is not a perfect fit, because Haskell's `Num` class also contains two non-ring operations `abs` and `signum`. By convention, for rings where these notions don't make sense (or are inconvenient to define), we set `abs` x = x and `signum` x = 1.

Instances

 Num a => Ring a

# Rings with particular elements

We define several classes of rings with special elements.

## Rings with ½

class Ring a => HalfRing a whereSource

A type class for rings that contain ½.

Minimal complete definition: `half`. The default definition of `fromDyadic` uses the expression `a*half^n`. However, this can give potentially bad round-off errors for fixed-precision types where the expression `half^n` can underflow. For such rings, one should provide a custom definition, for example by using `a/2^n` instead.

Methods

half :: aSource

The value ½.

The unique ring homomorphism from ℤ[½] to any `HalfRing`. This exists because ℤ[½] is the free `HalfRing`.

Instances

 HalfRing Double HalfRing Float HalfRing Rational HalfRing SymReal HalfRing Rationals HalfRing Dyadic (HalfRing a, RealFloat a) => HalfRing (Complex a) Precision e => HalfRing (FixedPrec e) HalfRing a => HalfRing (Omega a) HalfRing a => HalfRing (Cplx a) (Eq a, HalfRing a) => HalfRing (RootTwo a) (HalfRing a, Nat n) => HalfRing (Matrix n n a)

## Rings with √2

class Ring a => RootTwoRing a whereSource

A type class for rings that contain √2.

Minimal complete definition: `roottwo`. The default definition of `fromZRootTwo` uses the expression `x+roottwo*y`. However, this can give potentially bad round-off errors for fixed-precision types, where the expression `roottwo*y` can be vastly inaccurate if `y` is large. For such rings, one should provide a custom definition.

Methods

roottwo :: aSource

The square root of 2.

fromZRootTwo :: RootTwoRing a => ZRootTwo -> aSource

The unique ring homomorphism from ℤ[√2] to any ring containing √2. This exists because ℤ[√2] is the free such ring.

Instances

 RootTwoRing Double RootTwoRing Float RootTwoRing SymReal (RootTwoRing a, RealFloat a) => RootTwoRing (Complex a) Precision e => RootTwoRing (FixedPrec e) Ring a => RootTwoRing (Omega a) RootTwoRing a => RootTwoRing (Cplx a) (Eq a, Ring a) => RootTwoRing (RootTwo a) (RootTwoRing a, Nat n) => RootTwoRing (Matrix n n a)

## Rings with 1/√2

class (HalfRing a, RootTwoRing a) => RootHalfRing a whereSource

A type class for rings that contain 1/√2.

Minimal complete definition: `roothalf`. The default definition of `fromDRootTwo` uses the expression `x+roottwo*y`. However, this can give potentially bad round-off errors for fixed-precision types, where the expression `roottwo*y` can be vastly inaccurate if `y` is large. For such rings, one should provide a custom definition.

Methods

roothalf :: aSource

The square root of ½.

fromDRootTwo :: RootHalfRing a => DRootTwo -> aSource

The unique ring homomorphism from D[√2] to any ring containing 1/√2. This exists because D[√2] = ℤ[1/√2] is the free such ring.

Instances

 RootHalfRing Double RootHalfRing Float RootHalfRing SymReal (RootHalfRing a, RealFloat a) => RootHalfRing (Complex a) Precision e => RootHalfRing (FixedPrec e) HalfRing a => RootHalfRing (Omega a) RootHalfRing a => RootHalfRing (Cplx a) (Eq a, HalfRing a) => RootHalfRing (RootTwo a) (RootHalfRing a, Nat n) => RootHalfRing (Matrix n n a)

## Rings with i

class Ring a => ComplexRing a whereSource

A type class for rings that contain a square root of -1.

Methods

i :: aSource

The complex unit.

Instances

 (Ring a, RealFloat a) => ComplexRing (Complex a) Ring a => ComplexRing (Omega a) Ring a => ComplexRing (Cplx a) (Eq a, ComplexRing a) => ComplexRing (RootTwo a) (ComplexRing a, Nat n) => ComplexRing (Matrix n n a)

## Rings with ω

class Ring a => OmegaRing a whereSource

A type class for rings that contain a square root of i, or equivalently, a fourth root of −1.

Methods

omega :: aSource

The square root of i.

Instances

 (ComplexRing a, RootHalfRing a) => OmegaRing a OmegaRing ZOmega OmegaRing (Omega Z2)

# Rings with particular automorphisms

## Rings with complex conjugation

A type class for rings with complex conjugation, i.e., an automorphism mapping i to −i.

When instances of this type class are vectors or matrices, the conjugation also exchanges the roles of rows and columns (in other words, it is the adjoint).

For rings that are not complex, the conjugation can be defined to be the identity function.

Methods

Compute the adjoint (complex conjugate transpose).

Instances

## Rings with √2-conjugation

A type class for rings with a √2-conjugation, i.e., an automorphism mapping √2 to −√2.

When instances of this type class are vectors or matrices, the √2-conjugation does not exchange the roles of rows and columns.

For rings that have no √2, the conjugation can be defined to be the identity function.

Methods

Compute the adjoint, mapping a + b√2 to ab√2.

Instances

# Normed rings

class Ring r => NormedRing r whereSource

A (number-theoretic) norm on a ring R is a function N : R → ℤ such that N(rs) = N(r)N(s), for all r, sR. The norm also satisfies N(r) = 0 iff r = 0, and N(r) = ±1 iff r is a unit of the ring.

Methods

norm :: r -> IntegerSource

Instances

 NormedRing Integer NormedRing a => NormedRing (Omega a) NormedRing a => NormedRing (Cplx a) (Eq a, NormedRing a) => NormedRing (RootTwo a)

# Floor and ceiling

class Ring r => Floor r whereSource

The `floor` and `ceiling` functions provided by the standard Haskell libraries are predicated on many unnecessary assumptions. This type class provides an alternative.

Minimal complete definition: `floor_of` or `ceiling_of`.

Methods

floor_of :: r -> IntegerSource

Compute the floor of x, i.e., the greatest integer n such that nx.

ceiling_of :: r -> IntegerSource

Compute the ceiling of x, i.e., the least integer n such that xn.

Instances

 Floor Double Floor Float Floor Integer Floor Rational Floor QRootTwo Floor Rationals Precision e => Floor (FixedPrec e)

# Particular rings

## The ring ℤ₂ of integers modulo 2

data Z2 Source

The ring ℤ₂ of integers modulo 2.

Constructors

 Even Odd

Instances

 Eq Z2 Num Z2 Show Z2 Adjoint2 Z2 Adjoint Z2 Residue Integer Z2 OmegaRing (Omega Z2) ShowLaTeX (Omega Z2)

## The ring D of dyadic fractions

A dyadic fraction is a rational number whose denominator is a power of 2. We denote the dyadic fractions by D = ℤ[½].

We internally represent a dyadic fraction a/2n as a pair (a,n). Note that this representation is not unique. When it is necessary to choose a canonical representative, we choose the least possible n≥0.

Constructors

Instances

Given a dyadic fraction r, return (a,n) such that r = a/2n, where n≥0 is chosen as small as possible.

Given a dyadic fraction r and an integer k≥0, such that a = r2k is an integer, return a. If a is not an integer, the behavior is undefined.

## The ring ℚ of rational numbers

newtype Rationals Source

We define our own variant of the rational numbers, which is an identical copy of the type `Rational` from the standard Haskell library, except that it has a more sensible `Show` instance.

Constructors

 ToRationals FieldsunRationals :: Rational

showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowSSource

An auxiliary function for printing rational numbers, using correct precedences, and omitting denominators of 1.

fromRationals :: Fractional a => Rationals -> aSource

Conversion from `Rationals` to any `Fractional` type.

## The ring R[√2]

data RootTwo a Source

The ring R[√2], where R is any ring. The value `RootTwo` a b represents a + b √2.

Constructors

 RootTwo !a !a

Instances

 Show DRComplex Parity ZRootTwo DenomExp DRootTwo Floor QRootTwo EuclideanDomain ZRootTwo WholePart DRootTwo ZRootTwo Eq a => Eq (RootTwo a) (Eq a, Fractional a) => Fractional (RootTwo a) (Eq a, Num a) => Num (RootTwo a) (Eq a, Ring a) => Ord (RootTwo a) (Show a, Eq a, Ring a) => Show (RootTwo a) ToQOmega a => ToQOmega (RootTwo a) (Eq a, NormedRing a) => NormedRing (RootTwo a) (Adjoint2 a, Num a) => Adjoint2 (RootTwo a) Adjoint a => Adjoint (RootTwo a) (Eq a, ComplexRing a) => ComplexRing (RootTwo a) (Eq a, HalfRing a) => RootHalfRing (RootTwo a) (Eq a, Ring a) => RootTwoRing (RootTwo a) (Eq a, HalfRing a) => HalfRing (RootTwo a) (ShowLaTeX a, Eq a, Ring a) => ShowLaTeX (RootTwo a) HalfRing a => RealPart (Omega a) (RootTwo a) ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b) Residue a b => Residue (RootTwo a) (RootTwo b) Nat m => Show (Matrix m n DRComplex) Nat m => Show (Matrix m n DRootTwo) Nat n => ShowLaTeX (Matrix n m DRComplex)

## The ring ℤ[√2]

The ring ℤ[√2].

Return a square root of an element of ℤ[√2], if such a square root exists, or else `Nothing`.

## The ring D[√2]

The ring D[√2] = ℤ[1/√2].

## The field ℚ[√2]

The field ℚ[√2].

fromQRootTwo :: (RootTwoRing a, Fractional a) => QRootTwo -> aSource

The unique ring homomorphism from ℚ[√2] to any ring containing the rational numbers and √2. This exists because ℚ[√2] is the free such ring.

## The ring R[i]

data Cplx a Source

The ring R[i], where R is any ring. The reason we do not use the `Complex` a type from the standard Haskell libraries is that it assumes too much, for example, it assumes a is a member of the `RealFloat` class. Also, this allows us to define a more sensible `Show` instance.

Constructors

 Cplx !a !a

Instances

 Show DRComplex EuclideanDomain ZComplex Eq a => Eq (Cplx a) Fractional a => Fractional (Cplx a) Num a => Num (Cplx a) (Eq a, Show a, Num a) => Show (Cplx a) ToQOmega a => ToQOmega (Cplx a) DenomExp a => DenomExp (Cplx a) NormedRing a => NormedRing (Cplx a) (Adjoint2 a, Ring a) => Adjoint2 (Cplx a) (Adjoint a, Ring a) => Adjoint (Cplx a) Ring a => ComplexRing (Cplx a) RootHalfRing a => RootHalfRing (Cplx a) RootTwoRing a => RootTwoRing (Cplx a) HalfRing a => HalfRing (Cplx a) (ShowLaTeX a, Ring a, Eq a) => ShowLaTeX (Cplx a) RealPart (Cplx a) a WholePart a b => WholePart (Cplx a) (Cplx b) ToDyadic a b => ToDyadic (Cplx a) (Cplx b) Residue a b => Residue (Cplx a) (Cplx b) Nat m => Show (Matrix m n DRComplex) Nat n => ShowLaTeX (Matrix n m DRComplex)

## The ring ℤ[i] of Gaussian integers

The ring ℤ[i] of Gaussian integers.

fromZComplex :: ComplexRing a => ZComplex -> aSource

The unique ring homomorphism from ℤ[i] to any ring containing i. This exists because ℤ[i] is the free such ring.

## The ring D[i]

The ring D[i] = ℤ[½, i] of Gaussian dyadic fractions.

fromDComplex :: (ComplexRing a, HalfRing a) => DComplex -> aSource

The unique ring homomorphism from D[i] to any ring containing ½ and i. This exists because D[i] is the free such ring.

## The ring ℚ[i] of Gaussian rationals

The ring ℚ[i] of Gaussian rationals.

fromQComplex :: (ComplexRing a, Fractional a) => QComplex -> aSource

The unique ring homomorphism from ℚ[i] to any ring containing the rational numbers and i. This exists because ℚ[i] is the free such ring.

## The ring D[√2, i]

The ring D[√2, i] = ℤ[1/√2, i].

fromDRComplex :: (RootHalfRing a, ComplexRing a) => DRComplex -> aSource

The unique ring homomorphism from D[√2, i] to any ring containing 1/√2 and i. This exists because D[√2, i] = ℤ[1/√2, i] is the free such ring.

## The ring ℚ[√2, i]

The field ℚ[√2, i].

fromQRComplex :: (RootTwoRing a, ComplexRing a, Fractional a) => QRComplex -> aSource

The unique ring homomorphism from ℚ[√2, i] to any ring containing the rational numbers, √2, and i. This exists because ℚ[√2, i] is the free such ring.

## The ring ℂ of complex numbers

We provide two versions of the complex numbers using floating point arithmetic.

Double precision complex floating point numbers.

Single precision complex floating point numbers.

## The ring R[ω]

data Omega a Source

The ring R[ω], where R is any ring, and ω = eiπ/4 is an 8th root of unity. The value `Omega` a b c d represents aω3+bω2+cω+d.

Constructors

 Omega !a !a !a !a

Instances

 Show DOmega DenomExp DOmega OmegaRing ZOmega ShowLaTeX DOmega ShowLaTeX ZOmega EuclideanDomain ZOmega WholePart DOmega ZOmega Eq a => Eq (Omega a) Fractional a => Fractional (Omega a) Num a => Num (Omega a) (Show a, Ring a) => Show (Omega a) ToQOmega a => ToQOmega (Omega a) NormedRing a => NormedRing (Omega a) (Adjoint2 a, Ring a) => Adjoint2 (Omega a) (Adjoint a, Ring a) => Adjoint (Omega a) OmegaRing (Omega Z2) Ring a => ComplexRing (Omega a) HalfRing a => RootHalfRing (Omega a) Ring a => RootTwoRing (Omega a) HalfRing a => HalfRing (Omega a) ShowLaTeX (Omega Z2) HalfRing a => RealPart (Omega a) (RootTwo a) ToDyadic a b => ToDyadic (Omega a) (Omega b) Residue a b => Residue (Omega a) (Omega b) Nat m => Show (Matrix m n DOmega) Nat n => ShowLaTeX (Matrix n m DOmega)

omega_real :: Omega a -> aSource

An inverse to the embedding RR[ω]: return the "real rational" part. In other words, map aω3+bω2+cω+d to d.

## The ring ℤ[ω]

The ring ℤ[ω] of cyclotomic integers of degree 8. Such rings were first studied by Kummer around 1840, and used in his proof of special cases of Fermat's Last Theorem. See also:

fromZOmega :: OmegaRing a => ZOmega -> aSource

The unique ring homomorphism from ℤ[ω] to any ring containing ω. This exists because ℤ[ω] is the free such ring.

Inverse of the embedding ℤ[√2] → ℤ[ω]. Note that ℤ[√2] = ℤ[ω] ∩ ℝ. This function takes an element of ℤ[ω] that is real, and converts it to an element of ℤ[√2]. It throws an error if the input is not real.

## The ring D[ω]

The ring D[ω]. Here D=ℤ[½] is the ring of dyadic fractions. In fact, D[ω] is isomorphic to the ring D[√2, i], but they have different `Show` instances.

fromDOmega :: (RootHalfRing a, ComplexRing a) => DOmega -> aSource

The unique ring homomorphism from D[ω] to any ring containing 1/√2 and i. This exists because D[ω] is the free such ring.

## The field ℚ[ω]

The field ℚ[ω] of cyclotomic rationals of degree 8.

fromQOmega :: (RootHalfRing a, ComplexRing a, Fractional a) => QOmega -> aSource

The unique ring homomorphism from ℚ[ω] to any ring containing the rational numbers, √2, and i. This exists because ℚ[ω] is the free such ring.

class ToDyadic a b | a -> b whereSource

A type class relating "rational" types to their dyadic counterparts.

Methods

maybe_dyadic :: a -> Maybe bSource

Convert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, return `Nothing`.

Instances

Convert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, throw an error.

# Real part

class RealPart a b | a -> b whereSource

A type class for rings that have a "real" component. A typical instance is a = `DRComplex` with b = `DRootTwo`.

Methods

real :: a -> bSource

Take the real part.

Instances

 RealPart (Cplx a) a HalfRing a => RealPart (Omega a) (RootTwo a)

# Rings of integers

class WholePart a b | a -> b whereSource

A type class for rings that have a distinguished subring "of integers". A typical instance is a = `DRootTwo`, which has b = `ZRootTwo` as its ring of integers.

Methods

from_whole :: b -> aSource

The embedding of the ring of integers into the larger ring.

to_whole :: a -> bSource

The inverse of `from_whole`. Throws an error if the given element is not actually an integer in the ring.

Instances

 WholePart () () WholePart DOmega ZOmega WholePart DRootTwo ZRootTwo WholePart Dyadic Integer WholePart a b => WholePart [a] [b] WholePart a b => WholePart (Cplx a) (Cplx b) (WholePart a a', WholePart b b') => WholePart (a, b) (a', b') WholePart a b => WholePart (Vector n a) (Vector n b) WholePart a b => WholePart (Matrix m n a) (Matrix m n b)

# Common denominators

class DenomExp a whereSource

A type class for things from which a common power of 1/√2 (a least denominator exponent) can be factored out. Typical instances are `DRootTwo`, `DRComplex`, as well as tuples, lists, vectors, and matrices thereof.

Methods

denomexp :: a -> IntegerSource

Calculate the least denominator exponent k of a. Returns the smallest k≥0 such that a = b/√2k for some integral b.

denomexp_factor :: a -> Integer -> aSource

Factor out a kth power of 1/√2 from a. In other words, calculate a√2k.

Instances

 DenomExp () DenomExp DOmega DenomExp DRootTwo DenomExp a => DenomExp [a] DenomExp a => DenomExp (Cplx a) (DenomExp a, DenomExp b) => DenomExp (a, b) DenomExp a => DenomExp (Vector n a) DenomExp a => DenomExp (Matrix m n a)

denomexp_decompose :: (WholePart a b, DenomExp a) => a -> (b, Integer)Source

Calculate and factor out the least denominator exponent k of a. Return (b,k), where a = b/(√2)k and k≥0.

showsPrec_DenomExp :: (WholePart a b, Show b, DenomExp a) => Int -> a -> ShowSSource

Generic `show`-like method that factors out a common denominator exponent.

# Conversion to ℚ[ω]

`QOmega` is the largest one of our "exact" arithmetic types. We define a `toQOmega` family of functions for converting just about anything to `QOmega`.

class ToQOmega a whereSource

A type class for things that can be exactly converted to ℚ[ω].

Methods

toQOmega :: a -> QOmegaSource

Conversion to `QOmega`.

Instances

 ToQOmega Integer ToQOmega Rational ToQOmega Rationals ToQOmega Dyadic ToQOmega a => ToQOmega (Omega a) ToQOmega a => ToQOmega (Cplx a) ToQOmega a => ToQOmega (RootTwo a)

# Parity

class Parity a whereSource

A type class for things that have parity.

Methods

parity :: a -> Z2Source

Return the parity of something.

Instances

 Integral a => Parity a Parity ZRootTwo

# Auxiliary functions

Return the position of the rightmost "1" bit of an Integer, or -1 if none. Do this in time O(n log n), where n is the size of the integer (in digits).

If n is of the form 2k, return k. Otherwise, return `Nothing`.

Return 1 + the position of the leftmost "1" bit of a non-negative `Integer`. Do this in time O(n log n), where n is the size of the integer (in digits).

intsqrt :: Integral n => n -> nSource

For n ≥ 0, return the floor of the square root of n. This is done using integer arithmetic, so there are no rounding errors.