The Quipper System

Safe HaskellNone

QuipperLib.Arith

Contents

Description

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.

Synopsis

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.

data XInt x Source #

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.

Instances

Enum IntM # 

Methods

succ :: IntM -> IntM #

pred :: IntM -> IntM #

toEnum :: Int -> IntM #

fromEnum :: IntM -> Int #

enumFrom :: IntM -> [IntM] #

enumFromThen :: IntM -> IntM -> [IntM] #

enumFromTo :: IntM -> IntM -> [IntM] #

enumFromThenTo :: IntM -> IntM -> IntM -> [IntM] #

Integral IntM # 

Methods

quot :: IntM -> IntM -> IntM #

rem :: IntM -> IntM -> IntM #

div :: IntM -> IntM -> IntM #

mod :: IntM -> IntM -> IntM #

quotRem :: IntM -> IntM -> (IntM, IntM) #

divMod :: IntM -> IntM -> (IntM, IntM) #

toInteger :: IntM -> Integer #

Num IntM # 

Methods

(+) :: IntM -> IntM -> IntM #

(-) :: IntM -> IntM -> IntM #

(*) :: IntM -> IntM -> IntM #

negate :: IntM -> IntM #

abs :: IntM -> IntM #

signum :: IntM -> IntM #

fromInteger :: Integer -> IntM #

Ord IntM # 

Methods

compare :: IntM -> IntM -> Ordering #

(<) :: IntM -> IntM -> Bool #

(<=) :: IntM -> IntM -> Bool #

(>) :: IntM -> IntM -> Bool #

(>=) :: IntM -> IntM -> Bool #

max :: IntM -> IntM -> IntM #

min :: IntM -> IntM -> IntM #

Real IntM # 

Methods

toRational :: IntM -> Rational #

Show IntM # 

Methods

showsPrec :: Int -> IntM -> ShowS #

show :: IntM -> String #

showList :: [IntM] -> ShowS #

Show QDInt # 

Methods

showsPrec :: Int -> QDInt -> ShowS #

show :: QDInt -> String #

showList :: [QDInt] -> ShowS #

QOrd QDInt # 
Zero IntM # 

Methods

zero :: IntM -> IntM Source #

Interval IntM # 

Methods

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

QNum QDInt # 
Eq x => Eq (XInt x) # 

Methods

(==) :: XInt x -> XInt x -> Bool #

(/=) :: XInt x -> XInt x -> Bool #

Show x => Show (XInt x) # 

Methods

showsPrec :: Int -> XInt x -> ShowS #

show :: XInt x -> String #

showList :: [XInt x] -> ShowS #

QCLeaf x => QCData (XInt x) # 

Methods

qcdata_mapM :: Monad m => XInt x -> (q -> m q') -> (c -> m c') -> QCType q c (XInt x) -> m (QCType q' c' (XInt x)) Source #

qcdata_zip :: XInt x -> q -> c -> q' -> c' -> QCType q c (XInt x) -> QCType q' c' (XInt x) -> ErrMsg -> QCType (q, q') (c, c') (XInt x) Source #

qcdata_promote :: BType (XInt x) -> XInt x -> ErrMsg -> BType (XInt x) Source #

QCLeaf x => Labelable (XInt x) String # 

Methods

label_rec :: XInt x -> String -> LabelMonad () Source #

CircLiftingUnpack (Circ QDInt) (Circ QDInt) # 
type QTypeB IntM # 
type QCType x y (XInt z) # 
type QCType x y (XInt z) = XInt (QCType x y z)

type QDInt = XInt Qubit Source #

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

type CInt = XInt Bit Source #

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_length :: QDInt -> Int Source #

Return the length of a QDInt, in bits.

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_length :: CInt -> Int Source #

Return the length of a CInt, in bits.

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 #

Convert an IntM to a list of booleans. The conversion is big-headian, i.e., the head of the list holds the most significant digit. As usual, False is 0 and True is 1. It is an error to apply this operation to an IntM whose length is indeterminate.

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.

intm_length :: IntM -> Maybe Int Source #

Return the size of an IntM, or Nothing if indeterminate.

integer_of_intm_unsigned :: IntM -> Integer Source #

Convert an IntM of length m to an Integer in the range {0, …, 2m-1}. If the IntM has indeterminate length, return the original Integer.

integer_of_intm_signed :: IntM -> Integer Source #

Convert an IntM of length m to an Integer in the range {-2m-1, …, 2m-1-1}. If the IntM has indeterminate length, return the original Integer.

intm_with_length :: Maybe Int -> Integer -> IntM Source #

Create an IntM of the given length and value. Leave the length indeterminate if it is given as Nothing.

intm_of_integer :: Integer -> IntM Source #

Create an IntM of indeterminate length from an Integer.

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

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

intm_promote :: IntM -> XInt x -> String -> IntM Source #

Try to set the length of an IntM to that of another XInt value (which could be a QDInt, a CInt, or another IntM). This will fail with an error if both numbers already have determinate lengths that don't coincide. In this case, the string argument is used as an error message.

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

Return the interval [x..y], with x and y regarded as signed values of type IntM.

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

Return the interval [x..y], with 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

xint_maybe_length :: XInt x -> Maybe Int Source #

Return the size of a XInt, or Nothing if indeterminate.

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

From a XInt, which must be of determinate length, extract a list of xs. The conversion is big-headian, i.e., the head of the list holds the most significant digit. It is an error to call this function with an XInt of indeterminate length.

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

Create a XInt x from a list of xs. 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.

Minimal complete definition

q_add, q_mult, q_sub, q_abs, q_negate, q_signum, q_fromQDInt

Methods

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

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

Compute a quantum number of the same precision as the input, with value 1, 0, or –1, depending on the sign of the input. Analogous to Haskell’s signum. The QDInt instance is O(ℓ).

q_fromQDInt :: QDInt -> Circ (QDInt, qa) Source #

Convert a QDInt to a quantum number. For the QDInt instance, this is just a copy operation.

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,yx). Arguments are assumed to be of equal size. O(ℓ) gates.

q_negate_in_place :: QDInt -> Circ QDInt Source #

Negate a (signed) QDInt in place. O(ℓ).

Arithmetic with classical parameter

q_add_param :: IntM -> QDInt -> Circ (QDInt, QDInt) Source #

Add a parameter IntM and a QDInt, into a fresh QDInt: (x, y) ↦ (y, x+y). The parameter x must be of the same length as y, or x can also be of undetermined length. O(ℓ).

q_sub_param :: IntM -> QDInt -> Circ (QDInt, QDInt) Source #

Subtract a parameter IntM from a QDInt, into a fresh QDInt. The IntM cannot be shorter than the QDInt (that would give ill-defined behavior), but can be of undetermined length. O(ℓ).

q_add_param_in_place :: IntM -> QDInt -> Circ QDInt Source #

Add a parameter IntM onto a QDInt, in place; i.e. (x,y) ↦ x+y. The parameter x must be of the same length as y, or x can also be of undetermined length. O(ℓ).

q_sub_param_in_place :: IntM -> QDInt -> Circ QDInt Source #

Subtract a parameter IntM from a QDInt, in place; i.e. (x,y) ↦ (x,x-y). x cannot be shorter than y. O(l) gates.

q_mult_param :: IntM -> QDInt -> Circ (QDInt, QDInt) Source #

Multiply a parameter IntM by a QDInt, into a fresh QDInt. The IntM cannot be shorter than the QDInt (that would give ill-defined behavior), but can be of undetermined length. O(ℓ).

Comparison

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

Comparison of two QDInts, considered as unsigned. O(ℓ).

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

Comparison of two QDInts, considered as signed. Used in instance QOrd QDInt. O(ℓ).

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

Comparison of two QDInts, considered as signed. Used in instance QOrd QDInt. O(ℓ).

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

Text whether a QDInt is nonnegative. O(1)

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 QDInts, 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 QDInts, 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 QDInts 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 QDInts 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 QDInts, 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 QDInts, 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.

template_symb_plus_ :: QNum qa => Circ (qa -> Circ (qa -> Circ qa)) Source #

Quantum lifting of the + operator.