Safe Haskell | None |
---|

This library provides a type of quantum integers, as well as basic arithmetic functions on them.

The type `QDInt`

holds a fixed-size, ℓ-qubit quantum integer,
considered modulo 2^{ℓ}. The integers may be regarded as
signed or unsigned, depending on the operation. If signs are used,
they are assumed to be in two's complement.

Some of the arithmetic operations are adapted from the GFI for the Triangle Finding algorithm. Most algorithms used are, for now, very naïve (ripple adders, etc). Gate count estimates are given in the Toffoli gatebase.

- data XInt x
- type QDInt = XInt Qubit
- type CInt = XInt Bit
- type IntM = XInt Bool
- qulist_of_qdint_bh :: QDInt -> [Qubit]
- qdint_of_qulist_bh :: [Qubit] -> QDInt
- qulist_of_qdint_lh :: QDInt -> [Qubit]
- qdint_of_qulist_lh :: [Qubit] -> QDInt
- qdint_length :: QDInt -> Int
- qdint_extend_unsigned :: Int -> QDInt -> Circ QDInt
- qdint_extend_signed :: Int -> QDInt -> Circ QDInt
- bitlist_of_cint_bh :: CInt -> [Bit]
- cint_of_bitlist_bh :: [Bit] -> CInt
- bitlist_of_cint_lh :: CInt -> [Bit]
- cint_of_bitlist_lh :: [Bit] -> CInt
- cint_length :: CInt -> Int
- cint_extend_unsigned :: Int -> CInt -> Circ CInt
- cint_extend_signed :: Int -> CInt -> Circ CInt
- boollist_of_intm_bh :: IntM -> [Bool]
- intm_of_boollist_bh :: [Bool] -> IntM
- intm_length :: IntM -> Maybe Int
- integer_of_intm_unsigned :: IntM -> Integer
- integer_of_intm_signed :: IntM -> Integer
- intm_with_length :: Maybe Int -> Integer -> IntM
- intm_of_integer :: Integer -> IntM
- intm :: Int -> Integer -> IntM
- intm_promote :: IntM -> XInt x -> String -> IntM
- intm_interval_signed :: IntM -> IntM -> [IntM]
- intm_interval_unsigned :: IntM -> IntM -> [IntM]
- intm_extend_unsigned :: Int -> IntM -> IntM
- intm_extend_signed :: Int -> IntM -> IntM
- qdint_shape :: Int -> QDInt
- cint_shape :: Int -> CInt
- xint_maybe_length :: XInt x -> Maybe Int
- list_of_xint_bh :: XInt x -> [x]
- xint_of_list_bh :: [x] -> XInt x
- list_of_xint_lh :: XInt x -> [x]
- xint_of_list_lh :: [x] -> XInt x
- class QData qa => QNum qa where
- q_increment :: QDInt -> Circ QDInt
- q_decrement :: QDInt -> Circ QDInt
- q_add_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt)
- q_sub_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt)
- q_negate_in_place :: QDInt -> Circ QDInt
- q_add_param :: IntM -> QDInt -> Circ (QDInt, QDInt)
- q_sub_param :: IntM -> QDInt -> Circ (QDInt, QDInt)
- q_add_param_in_place :: IntM -> QDInt -> Circ QDInt
- q_sub_param_in_place :: IntM -> QDInt -> Circ QDInt
- q_mult_param :: IntM -> QDInt -> Circ (QDInt, QDInt)
- q_le_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, Qubit)
- q_le_signed :: QDInt -> QDInt -> Circ (QDInt, QDInt, Qubit)
- q_lt_signed :: QDInt -> QDInt -> Circ (QDInt, QDInt, Qubit)
- q_negative :: QDInt -> Circ (QDInt, Qubit)
- q_moddiv_unsigned_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_mod_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_divrem_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt)
- q_div_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_div :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_quot :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_div_exact_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_div_exact :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)
- q_ext_euclid :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt, QDInt)
- template_symb_plus_ :: QNum qa => Circ (qa -> Circ (qa -> Circ qa))

# Quantum integers

## Data type definitions

We define three versions of the fixed-length integer type: quantum,
classical input, and classical parameter. The triple (`IntM`

,
`QDInt`

, `CInt`

) forms an instance of the `QShape`

class. All three
types are special cases of the type `XInt`

*x*.

`XInt`

*x* is the type of fixed-length integers, but using
elements of type *x* instead of bits. It is an abstract type, and
details of its implementation is not exposed to user-level code.

Enum IntM # | |

Integral IntM # | |

Num IntM # | |

Ord IntM # | |

Real IntM # | |

Show IntM # | |

Show QDInt # | |

QOrd QDInt # | |

Zero IntM # | |

Interval IntM # | |

QNum QDInt # | |

Eq x => Eq (XInt x) # | |

Show x => Show (XInt x) # | |

QCLeaf x => QCData (XInt x) # | |

QCLeaf x => Labelable (XInt x) String # | |

CircLiftingUnpack (Circ QDInt) (Circ QDInt) # | |

type QTypeB IntM # | |

type QCType x y (XInt z) # | |

type QDInt = XInt Qubit Source #

The type of fixed-length *m*-qubit quantum integers. This is a
circuit execution time value.

The type of fixed-length *m*-bit classical integer inputs. This
is a circuit execution time value.

type IntM = XInt Bool Source #

The type of fixed-length *m*-bit integer parameters. Values of
this type are parameters, i.e., they are classical and known at
circuit generation time.

Unlike values of type `QDInt`

and `CInt`

, a value of type `IntM`

may have an indeterminate length. This happens, for example, if the
value is specified by means of an integer literal (e.g., 17), which
does not carry length information. In such cases, the value can
only be used when it can be deduced from the context. For example,
such values may be used for terminating or controlling a `QDInt`

,
but not for initializing a `QDInt`

.

## Operations on QDInt

qulist_of_qdint_bh :: QDInt -> [Qubit] Source #

Convert a `QDInt`

to a list of qubits. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

qdint_of_qulist_bh :: [Qubit] -> QDInt Source #

Convert a list of qubits to a `QDInt`

. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

qulist_of_qdint_lh :: QDInt -> [Qubit] Source #

Convert a `QDInt`

to a list of qubits. The conversion is
little-headian, i.e., the head of the list holds the least significant
digit.

qdint_of_qulist_lh :: [Qubit] -> QDInt Source #

Convert a list of qubits to a `QDInt`

. The conversion is
little-headian, i.e., the head of the list holds the least significant
digit.

qdint_extend_unsigned :: Int -> QDInt -> Circ QDInt Source #

Extend a `QDInt`

to the given length without changing its
(unsigned) value. This is done by adding the required number of
high bits initialized to 0. It is an error to call this function
when the new length is shorter than the old one.

qdint_extend_signed :: Int -> QDInt -> Circ QDInt Source #

Extend a `QDInt`

to the given length without changing its
(signed) value. This is done by adding the required number of
high bits initialized to copies of the sign bit. It is an error to
call this function when the new length is shorter than the old one.

## Operations on CInt

bitlist_of_cint_bh :: CInt -> [Bit] Source #

Convert a `CInt`

to a list of qubits. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

cint_of_bitlist_bh :: [Bit] -> CInt Source #

Convert a list of qubits to a `CInt`

. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

bitlist_of_cint_lh :: CInt -> [Bit] Source #

Convert a `CInt`

to a list of bits. The conversion is
little-headian, i.e., the head of the list holds the least
significant digit.

cint_of_bitlist_lh :: [Bit] -> CInt Source #

Convert a list of bits to a `CInt`

. The conversion is
little-headian, i.e., the head of the list holds the least significant
digit.

cint_extend_unsigned :: Int -> CInt -> Circ CInt Source #

Extend a `CInt`

to the given length without changing its
(unsigned) value. This is done by adding the required number of
high bits initialized to 0. It is an error to call this function
when the new length is shorter than the old one.

cint_extend_signed :: Int -> CInt -> Circ CInt Source #

Extend a `CInt`

to the given length without changing its
(signed) value. This is done by adding the required number of
high bits initialized to copies of the sign bit. It is an error to
call this function when the new length is shorter than the old one.

## Operations on IntM

`IntM`

is an instance of Haskell's `Eq`

, `Num`

, `Ord`

, `Real`

,
`Enum`

, and `Integral`

type classes. This means that integer
literals (e.g., 17), and the usual arithmetic functions, such as
`+`

, `-`

, `*`

, `abs`

, `succ`

, `pred`

, `mod`

, `div`

, and others, can
be used for values of type `IntM`

. In general, we treat `IntM`

as a
signed integer type. Use `fromIntegral`

to convert an integer to an
`IntM`

of indeterminate length.

The general convention for binary operations (such as multiplication) is: both operands must have the same length, except: if one operand has indeterminate length, it takes on the length of the other; if both operands have indeterminate length, the result will have indeterminate length.

boollist_of_intm_bh :: IntM -> [Bool] Source #

intm_of_boollist_bh :: [Bool] -> IntM Source #

Convert a boolean list to an `IntM`

. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

integer_of_intm_signed :: IntM -> Integer Source #

intm :: Int -> Integer -> IntM Source #

Create an `IntM`

of the specified length (first argument) and
value (second argument).

intm_interval_signed :: IntM -> IntM -> [IntM] Source #

Return the interval `[`

, with *x*..*y*]*x* and *y* regarded as
signed values of type `IntM`

.

intm_interval_unsigned :: IntM -> IntM -> [IntM] Source #

Return the interval `[`

, with *x*..*y*]*x* and *y* regarded as
unsigned values of type `IntM`

.

intm_extend_unsigned :: Int -> IntM -> IntM Source #

Extend an `IntM`

to the given length without changing its
(unsigned) value. This is done by adding the required number of
high bits initialized to 0. It is an error to call this function
when the new length is shorter than the old one.

intm_extend_signed :: Int -> IntM -> IntM Source #

Extend an `IntM`

to the given length without changing its
(signed) value. This is done by adding the required number of
high bits initialized to copies of the sign bit. It is an error to
call this function when the new length is shorter than the old one.

## Shape parameters

qdint_shape :: Int -> QDInt Source #

Return a piece of shape data to represent an *m*-qubit quantum
integer. Please note that the data can only be used as shape; it
will be undefined at the leaves.

cint_shape :: Int -> CInt Source #

Return a piece of shape data to represent an *m*-bit `CInt`

.
Please note that the data can only be used as shape; it will be
undefined at the leaves.

## Operations on XInt

list_of_xint_bh :: XInt x -> [x] Source #

xint_of_list_bh :: [x] -> XInt x Source #

Create a `XInt`

*x* from a list of *x*s. The conversion is
big-headian, i.e., the head of the list holds the most significant
digit.

list_of_xint_lh :: XInt x -> [x] Source #

Convert an integer to a bit list. The conversion is little-headian, i.e., the head of the list holds the least significant digit.

xint_of_list_lh :: [x] -> XInt x Source #

Convert a bit list to an integer. The conversion is little-headian, i.e., the head of the list holds the least significant digit.

# Quantum arithmetic operations

## The QNum type class

class QData qa => QNum qa where Source #

Quantum analogue of Haskell’s `Num`

type class. This provides
basic addition, subtraction, multiplication, sign operations, and
conversion from integers.

q_add :: qa -> qa -> Circ (qa, qa, qa) Source #

Add two quantum numbers into a fresh one. The arguments are
assumed to be of equal size. The `QDInt`

instance uses *O*(ℓ)
gates, both before and after transformation to Toffoli.

q_mult :: qa -> qa -> Circ (qa, qa, qa) Source #

Multiply two quantum numbers into a fresh third. The arguments
are assumed to be of equal size. The `QDInt`

instance is
*O*(ℓ^{2}).

q_sub :: qa -> qa -> Circ (qa, qa, qa) Source #

Subtract two quantum numbers into a fresh one. The arguments
are assumed to be of equal size. The `QDInt`

instance uses *O*(ℓ)
gates, both before and after transformation to Toffoli.

q_abs :: qa -> Circ (qa, qa) Source #

Compute the absolute value of a (signed) quantum number. The
`QDInt`

instance is *O*(ℓ).

q_negate :: qa -> Circ (qa, qa) Source #

Compute the negation of a (signed) quantum number. The `QDInt`

instance is *O*(ℓ).

## In-place increment and decrement

q_increment :: QDInt -> Circ QDInt Source #

Increment a `QDInt`

in place. *O*(ℓ) gates.

Implementation note: currently tries to minimize gate count, at the cost of a rather long Quipper description. Can the latter be reduced without increasing the former?

q_decrement :: QDInt -> Circ QDInt Source #

Decrement a `QDInt`

in place. Inverse of `q_increment`

. *O*(ℓ).

## In-place addition and subtraction

q_add_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt) Source #

Add one `QDInt`

onto a second, in place; i.e. (*x*,*y*) ↦ (*x*,*x*+*y*). Arguments are assumed to be of equal size. *O*(ℓ) gates.

q_sub_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt) Source #

Subtract one `QDInt`

from a second, in place; i.e. (*x*,*y*) ↦ (*x*,*y*–*x*). Arguments are assumed to be of equal size. *O*(ℓ) gates.

## Arithmetic with classical parameter

## Comparison

q_le_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, Qubit) Source #

Comparison of two `QDInt`

s, considered as unsigned. *O*(ℓ).

## Division and remainder

q_moddiv_unsigned_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Reduce one `QDInt`

modulo another, in place, returning also the
integer quotient, i.e. (*x*, *y*) ↦ (*x* mod *y*, *y*, *x* div *y*).
All inputs and outputs are considered unsigned. Inputs are assumed
to have the same length. Division by zero returns (*x*,0,-1).

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_mod_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Reduce one `QDInt`

modulo another, i.e. (*x*, *y*) ↦ (*x*, *y*, *x* mod *y*).
All inputs and outputs are considered unsigned. Inputs are assumed
to have the same length. If *y* = 0, returns (*x*,0,*x*).

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_divrem_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s, returning the quotient and remainder,
i.e. (*x*,*y*) ↦ (*x*,*y*,*x* div *y*,*x* mod *y*).
All inputs and outputs are considered unsigned.
Inputs are assumed to have the same length.
Division by zero returns (-1,*x*).

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_div_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s, returning just the quotient.
All inputs/outputs considered unsigned.
Inputs are assumed to have the same length.
Division by zero returns –1.

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_div :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s into a fresh third, rounding towards –∞.
The first argument is the numerator, and is assumed to be signed.
The second argument is the denominator, and is assumed to be unsigned.
The output is signed.
Inputs are assumed to have the same length.

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_quot :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s into a fresh third, rounding towards 0.
The first argument is the numerator, and is assumed to be signed.
The second argument is the denominator, and is assumed to be unsigned.
The output is signed.
Inputs are assumed to have the same length.

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_div_exact_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s, returning the quotient,
assuming that the second exactly divides the first and throwing an error otherwise.
All inputs/outputs considered unsigned.
Inputs are assumed to have the same length.

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

q_div_exact :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt) Source #

Integer division of two `QDInt`

s, returning the quotient,
assuming that the second exactly divides the first.
The first argument is the numerator, considered signed.
The second argument is the denominator, considered unsigned.
The output is signed.

*O*(ℓ^{2}) gates, *O*(ℓ) qubits.

## Specialized functions

q_ext_euclid :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt, QDInt) Source #

Euclid's extended algorithm. `q_ext_euclid`

*a* *b*: returns
(*a*,*b*,*x*,*y*,*d*) such that *ax* + *by* = *d* = gcd(*a*,*b*).

# Lifting of arithmetic functions

This sections provides templates for lifting various arithmetic
functions in connection with the `build_circuit`

keyword. This
extends the liftings given in Quipper.CircLifting to operations
of the `Num`

type class.