newsynth-0.3.0.2: Exact and approximate synthesis of quantum circuits

Safe HaskellNone

Quantum.Synthesis.Ring

Contents

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

fromDyadic :: Dyadic -> aSource

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

Instances

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

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

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

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

Rings with particular automorphisms

Rings with complex conjugation

class Adjoint a whereSource

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

adj :: a -> aSource

Compute the adjoint (complex conjugate transpose).

Instances

Rings with √2-conjugation

class Adjoint2 a whereSource

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

adj2 :: a -> aSource

Compute the adjoint, mapping a + b√2 to a −b√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, s ∈ R. 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

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 n ≤ x.

ceiling_of :: r -> IntegerSource

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

Instances

Particular rings

The ring ℤ₂ of integers modulo 2

data Z2 Source

The ring ℤ₂ of integers modulo 2.

Constructors

Even 
Odd 

Instances

The ring D of dyadic fractions

data Dyadic Source

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

Dyadic !Integer !Integer 

Instances

decompose_dyadic :: Dyadic -> (Integer, Integer)Source

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

integer_of_dyadic :: Dyadic -> Integer -> IntegerSource

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 

Fields

unRationals :: Rational
 

Instances

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

The ring ℤ[√2]

type ZRootTwo = RootTwo IntegerSource

The ring ℤ[√2].

zroottwo_root :: ZRootTwo -> Maybe ZRootTwoSource

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

The ring D[√2]

type DRootTwo = RootTwo DyadicSource

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

The field ℚ[√2]

type QRootTwo = RootTwo RationalsSource

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

type ZComplex = Cplx IntegerSource

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]

type DComplex = Cplx DyadicSource

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

type QComplex = Cplx RationalsSource

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]

type DRComplex = Cplx DRootTwoSource

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]

type QRComplex = Cplx QRootTwoSource

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.

type CDouble = Cplx DoubleSource

Double precision complex floating point numbers.

type CFloat = Cplx FloatSource

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

omega_real :: Omega a -> aSource

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

The ring ℤ[ω]

type ZOmega = Omega IntegerSource

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.

zroottwo_of_zomega :: ZOmega -> ZRootTwoSource

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[ω]

type DOmega = Omega DyadicSource

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 ℚ[ω]

type QOmega = Omega RationalsSource

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.

Conversion to dyadic

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

to_dyadic :: ToDyadic a b => a -> bSource

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_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

Parity

class Parity a whereSource

A type class for things that have parity.

Methods

parity :: a -> Z2Source

Return the parity of something.

Instances

Auxiliary functions

lobit :: Integer -> IntegerSource

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

log2 :: Integer -> Maybe IntegerSource

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

hibit :: Integer -> IntSource

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.