The Quipper System

QuipperLib.Arith

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

 # Methodssucc :: 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] # # Methodsquot :: 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) # # Methods(+) :: IntM -> IntM -> IntM #(-) :: IntM -> IntM -> IntM #(*) :: IntM -> IntM -> IntM #negate :: IntM -> IntM #abs :: IntM -> IntM #signum :: IntM -> IntM # # Methodscompare :: IntM -> IntM -> Ordering #(<) :: IntM -> IntM -> Bool #(<=) :: IntM -> IntM -> Bool #(>) :: IntM -> IntM -> Bool #(>=) :: IntM -> IntM -> Bool #max :: IntM -> IntM -> IntM #min :: IntM -> IntM -> IntM # # Methods # MethodsshowsPrec :: Int -> IntM -> ShowS #show :: IntM -> String #showList :: [IntM] -> ShowS # # MethodsshowsPrec :: Int -> QDInt -> ShowS #show :: QDInt -> String #showList :: [QDInt] -> ShowS # # Methods # Methods # Methodsinterval :: IntM -> IntM -> [IntM] Source # # Methods Eq x => Eq (XInt x) # Methods(==) :: XInt x -> XInt x -> Bool #(/=) :: XInt x -> XInt x -> Bool # Show x => Show (XInt x) # MethodsshowsPrec :: Int -> XInt x -> ShowS #show :: XInt x -> String #showList :: [XInt x] -> ShowS # QCLeaf x => QCData (XInt x) # Methodsqcdata_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 # Methodslabel_rec :: XInt x -> String -> LabelMonad () Source # # Methods type QTypeB IntM # type QTypeB IntM = QDInt type QCType x y (XInt z) # type QCType x y (XInt z) = XInt (QCType x y z)

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

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.

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.

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.

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.

Return the length of a QDInt, in bits.

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.

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

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.

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.

Return the length of a CInt, in bits.

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.

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.

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.

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

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

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.

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.

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

Create an IntM of indeterminate length from an Integer.

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.

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

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

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.

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

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.

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

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

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.

Instances

 # Methods

In-place increment and decrement

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?

Decrement a QDInt in place. Inverse of q_increment. O(ℓ).

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.

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

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

Arithmetic with classical parameter

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

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

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

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.

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

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

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

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

Text whether a QDInt is nonnegative. O(1)

Division and remainder

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.

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.

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.

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.

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.

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.

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.

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

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.