-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | The Quantum IO Monad is a library for defining quantum computations in Haskell
--   
--   The Quantum IO Monad is a library for defining quantum computations in
--   Haskell. It can be thought of as an embedded language within Haskell,
--   and comes with functions for simulating the running of these quantum
--   computations. The distribution contains many example computations
--   written in QIO, including an implementation of Shor's algorithm.
@package QIO
@version 1.2


-- | This module defines a Vector as a list of pairs. In the context of
--   QIO, a Vector is the type used to represent a probability
--   distribution.
module QIO.Vec

-- | A Vector over types <tt>x</tt> and <tt>a</tt> is a wrapper around list
--   of pairs of <tt>a</tt> and <tt>x</tt>.
newtype Vec x a
Vec :: [(a, x)] -> Vec x a
unVec :: Vec x a -> [(a, x)]

-- | An empty Vector is defined as the empty list
empty :: Vec x a

-- | The "probability" of an object in a Vector, is the sum of all the
--   probabilities associated with that object.
(<@@>) :: (Num x, Eq a) => Vec x a -> a -> x

-- | A Vector can be multiplied by a scalar, by mapping the multiplcation
--   over each probability in the vector.
(<**>) :: Num x => x -> (Vec x a) -> Vec x a

-- | Two Vectors can be added, using list concatenation.
(<++>) :: (Vec x a) -> (Vec x a) -> Vec x a
instance (Show x, Show a) => Show (Vec x a)
instance Num n => Monad (Vec n)


-- | This module defines the Syntax of the Quantum IO Monad, which is an
--   embedded language for writing quantum computations.
module QIO.QioSyn

-- | For Real numbers, we simply use the built in Double type
type RR = Double

-- | For Complex numbers, we use the built in Complex numbers, over our
--   Real number type (i.e. Double)
type CC = Complex RR

-- | The amplitude of a complex number is the magnitude squared.
amp :: CC -> RR

-- | The type of Qubits in QIO are simply integer references.
newtype Qbit
Qbit :: Int -> Qbit

-- | A rotation is in essence a two-by-two complex valued matrix
type Rotation = (Bool, Bool) -> CC

-- | The underlying data type of a U unitary operation
data U
UReturn :: U
Rot :: Qbit -> Rotation -> U -> U
Swap :: Qbit -> Qbit -> U -> U
Cond :: Qbit -> (Bool -> U) -> U -> U
Ulet :: Bool -> (Qbit -> U) -> U -> U

-- | The underlying data type of a QIO Computation
data QIO a
QReturn :: a -> QIO a
MkQbit :: Bool -> (Qbit -> QIO a) -> QIO a
ApplyU :: U -> (QIO a) -> QIO a
Meas :: Qbit -> (Bool -> QIO a) -> QIO a

-- | Apply the given rotation to the given qubit
rot :: Qbit -> Rotation -> U

-- | Swap the state of the two given qubits
swap :: Qbit -> Qbit -> U

-- | Apply the conditional unitary, depending on the value of the given
--   qubit
cond :: Qbit -> (Bool -> U) -> U

-- | Introduce an Ancilla qubit in the given state, for use in the
--   sub-unitary
ulet :: Bool -> (Qbit -> U) -> U

-- | Returns the inverse (or reverse) of the given unitary operation
urev :: U -> U

-- | Apply a not rotation to the given qubit
unot :: Qbit -> U

-- | Apply a hadamard rotation to the given qubit
uhad :: Qbit -> U

-- | Apply a phase rotation (of the given angle) to the given qubit
uphase :: Qbit -> RR -> U

-- | Initialise a qubit in the given state (adding it to the overall
--   quantum state)
mkQbit :: Bool -> QIO Qbit

-- | Apply the given unitary operation to the current quantum state
applyU :: U -> QIO ()

-- | Measure the given qubit, and return the measurement outcome (note that
--   this operation may affect the overall quantum state, as a measurement
--   is destructive)
measQbit :: Qbit -> QIO Bool

-- | The identity rotation
rid :: Rotation

-- | The not rotation
rnot :: Rotation

-- | The hadamard rotation
rhad :: Rotation

-- | The phase rotation
rphase :: RR -> Rotation

-- | Returns the inverse (or reverse) of the given rotation
rrev :: Rotation -> Rotation

-- | A helper function for the show instance of U
show' :: U -> Int -> Int -> String

-- | A helper function that returns a string of 4x spaces.
spaces :: Int -> String
instance Num Qbit
instance Enum Qbit
instance Eq Qbit
instance Ord Qbit
instance Show U
instance Show Rotation
instance Show Qbit
instance Eq Rotation
instance Monad QIO
instance Monoid U


-- | This module defines a type class for quantum data types, as well as
--   some instances of this class for pairs, lists, and quantum integers
module QIO.Qdata

-- | The <a>Qdata</a> type class defines the operation a quantum datatype
--   must implement.
class Qdata a qa | a -> qa, qa -> a
mkQ :: Qdata a qa => a -> QIO qa
measQ :: Qdata a qa => qa -> QIO a
letU :: Qdata a qa => a -> (qa -> U) -> U
condQ :: Qdata a qa => qa -> (a -> U) -> U

-- | A recursive conditional on a list of quantum data
condQRec :: Qdata a qa => [qa] -> [(a -> U)] -> U

-- | Quantum integers are of a fixed length, which is defined by this
--   constant. Currently, this is set to 4.
qIntSize :: Int

-- | A Quantum integer is a wrapper around a fixed-length list of qubits
newtype QInt
QInt :: [Qbit] -> QInt

-- | Convert an integer to a list of Booleans
int2bits :: Int -> [Bool]

-- | Convert a list of Booleans to an integer
bits2int :: [Bool] -> Int
instance Show QInt
instance Qdata Int QInt
instance Qdata a qa => Qdata [a] [qa]
instance (Qdata a qa, Qdata b qb) => Qdata (a, b) (qa, qb)
instance Qdata Bool Qbit


-- | This module contains the definition of a Type Class that represents a
--   Heap. In the context of QIO, a Heap is the type used to represent a
--   classical basis state. An instance of a Heap is also defined, that
--   makes use of a Map.
module QIO.Heap

-- | The Heap Type Class
class Eq h => Heap h where hswap h x y = update (update h y (fromJust (h ? x))) x (fromJust (h ? y))
initial :: Heap h => h
update :: Heap h => h -> Qbit -> Bool -> h
(?) :: Heap h => h -> Qbit -> Maybe Bool
forget :: Heap h => h -> Qbit -> h
hswap :: Heap h => h -> Qbit -> Qbit -> h

-- | HeapMap is simply a type synonym for a Map from Qubits to Boolean
--   values
type HeapMap = Map Qbit Bool
instance Heap HeapMap


-- | This module defines the functions that can be used run the classical
--   subset of QIO. That is, QIO computations that only use classical
--   unitary operations.
module QIO.QioClass

-- | A classical unitary operation is defined as a function that will
--   update the current classical state.
newtype UnitaryC
U :: (Int -> HeapMap -> HeapMap) -> UnitaryC
unU :: UnitaryC -> Int -> HeapMap -> HeapMap

-- | A single qubit rotation can be converted into the classical unitary
--   type, if it is indeed classical (otherwise an error is thrown).
uRotC :: Qbit -> Rotation -> UnitaryC

-- | A swap operation can be defined in the classical unitary type.
uSwapC :: Qbit -> Qbit -> UnitaryC

-- | A conditional operation can be defined in the classical unitary type.
uCondC :: Qbit -> (Bool -> UnitaryC) -> UnitaryC

-- | A let operation can be defined in the classical unitary type.
uLetC :: Bool -> (Qbit -> UnitaryC) -> UnitaryC

-- | A unitary can be run by converting it into the classical unitary type.
runUC :: U -> UnitaryC

-- | A classical state consists of the next free qubit reference, along
--   with a Heap that represents the overall state of the current qubits in
--   scope.
data StateC
StateC :: Int -> HeapMap -> StateC
fv :: StateC -> Int
heap :: StateC -> HeapMap

-- | An initial state is defined as an empty heap, with 0 set as the next
--   free qubit referece
initialStateC :: StateC

-- | A QIO computation can be converted into a stateful computation, over a
--   state of type <a>StateC</a>.
runQStateC :: QIO a -> State StateC a

-- | We can run a classical QIO computation by converting it into a
--   stateful computation, and evaluating that using the initial state.
runC :: QIO a -> a
instance Monoid UnitaryC


-- | This module defines a class of Vectors over types with Equality, along
--   with an instance of this class using lists of pairs. In the context of
--   QIO, these Vectors are used to hold the amplitudes of various
--   basis-states within a superposition.
module QIO.VecEq

-- | Any type that fulfills this type class is a Vector over types with
--   equality
class VecEq v
vzero :: VecEq v => v x a
(<+>) :: (VecEq v, Eq a, Num x) => v x a -> v x a -> v x a
(<*>) :: (VecEq v, Num x, Eq x) => x -> v x a -> v x a
(<@>) :: (VecEq v, Eq a, Num x) => a -> v x a -> x
fromList :: VecEq v => [(a, x)] -> v x a
toList :: VecEq v => v x a -> [(a, x)]

-- | This type is a wrapper around a list of pairs.
newtype VecEqL x a
VecEqL :: [(a, x)] -> VecEqL x a
unVecEqL :: VecEqL x a -> [(a, x)]

-- | An empty VecEqL is a wrapper around the empty list
vEqZero :: VecEqL x a

-- | A basis state with the given amplitude can be added to a VecEqL by
--   adding the amplitudes if the state is already in the vector, or by
--   inserting the base state if it isn't already in the vector.
add :: (Eq a, Num x) => (a, x) -> VecEqL x a -> VecEqL x a

-- | Combining two vectors is achieved by folding the add operation over
--   the second vector
vEqPlus :: (Eq a, Num x) => VecEqL x a -> VecEqL x a -> VecEqL x a

-- | Scalar multiplcation is achieved by mapping the multiplication over
--   each pair in the vector. Multiplication by 0 is a special case, and
--   will remove all the basis states from the vector.
vEqTimes :: (Num x, Eq x) => x -> VecEqL x a -> VecEqL x a

-- | The amplitude of an element can be found by looking through each
--   element until the matchinf one is found.
vEqAt :: (Eq a, Num x) => a -> VecEqL x a -> x

-- | An EqMonad is a monad that has Return and Bind operations that depend
--   on the type in the monad being a member of the Eq class
class EqMonad m
eqReturn :: (EqMonad m, Eq a) => a -> m a
eqBind :: (EqMonad m, Eq a, Eq b) => m a -> (a -> m b) -> m b

-- | We can define a datatype that holds EqMonad operations, so that it can
--   be defined as a Monad.
data AsMonad m a
Embed :: m a -> AsMonad m a
Return :: a -> AsMonad m a
Bind :: AsMonad m a -> (a -> AsMonad m b) -> AsMonad m b

-- | Given Equality, we can unembed the EqMonad operations from an AsMonad
unEmbed :: Eq a => AsMonad m a -> m a
instance (Show x, Show a) => Show (VecEqL x a)
instance EqMonad m => Monad (AsMonad m)
instance (VecEq v, Num x, Eq x) => EqMonad (v x)
instance VecEq VecEqL


-- | This module defines the functions that can be used to simulate the
--   running of QIO computations.
module QIO.Qio

-- | A <a>Pure</a> state can be thought of as a vector of classical basis
--   states, stored as Heaps, along with complex amplitudes.
type Pure = VecEqL CC HeapMap

-- | The state of a qubit can be updated in a Pure state, by mapping the
--   update operation over each Heap.
updateP :: Pure -> Qbit -> Bool -> Pure

-- | A <a>Unitary</a> can be thought of as an operation on a HeapMap that
--   may produce a Pure state.
newtype Unitary
U :: (Int -> HeapMap -> Pure) -> Unitary
unU :: Unitary -> Int -> HeapMap -> Pure

-- | A function that checks if a given <a>Rotation</a> is in face unitary.
--   Note that this is currently a dummy stub function, and states that any
--   rotation is unitary. (This is only o.k. at the moment as all the
--   rotations defined in the QIO library are unitary, but won't catch
--   un-unitary user-defined Rotations)
unitaryRot :: Rotation -> Bool

-- | Given the four complex numbers that make up a 2-by-2 matrix, we can
--   create a Unitary that applies the rotation to the given qubit.
uMatrix :: Qbit -> (CC, CC, CC, CC) -> Unitary

-- | A rotation can be converted into a <a>Unitary</a>, using the
--   <a>uMatrix</a> function
uRot :: Qbit -> Rotation -> Unitary

-- | A swap operation can be defined as a Unitary
uSwap :: Qbit -> Qbit -> Unitary

-- | A conditional operation can be defined as a Unitary
uCond :: Qbit -> (Bool -> Unitary) -> Unitary

-- | A let operation can be defined as a Unitary
uLet :: Bool -> (Qbit -> Unitary) -> Unitary

-- | Any member of the <a>U</a> type can be "run" by converting it into a
--   Unitary.
runU :: U -> Unitary

-- | A quantum state is a defined as the next free qubit reference, along
--   with the Pure state that represents the overall quantum state
data StateQ
StateQ :: Int -> Pure -> StateQ
free :: StateQ -> Int
pure :: StateQ -> Pure

-- | The initial <a>StateQ</a>
initialStateQ :: StateQ

-- | Given a Pure state, return a sum of all the amplitudes.
pa :: Pure -> RR

-- | A Split, is defined as a probability, along with the two Pure states.
data Split
Split :: RR -> Pure -> Pure -> Split
p :: Split -> RR
ifTrue :: Split -> Pure
ifFalse :: Split -> Pure

-- | Given a Pure state, we can create a Split, by essentially splitting
--   the state into the part where the qubit is True, and the part where
--   the qubit is False. This is how measurements are implemented in QIO.
split :: Pure -> Qbit -> Split

-- | We can extend a Monad into a PMonad if it defines a way of
--   probabilistically merging two computations, based on a given
--   probability.
class Monad m => PMonad m
merge :: PMonad m => RR -> m a -> m a -> m a

-- | The type Prob is defined as a wrapper around Vectors with Real
--   probabilities.
data Prob a
Prob :: Vec RR a -> Prob a
unProb :: Prob a -> Vec RR a

-- | Given a PMonad, a QIO Computation can be converted into a Stateful
--   computation over a quantum state (of type <a>StateQ</a>).
evalWith :: PMonad m => QIO a -> State StateQ (m a)

-- | A QIO computation is evaluated by converting it into a stateful
--   computation and then evaluating that over the initial state.
eval :: PMonad m => QIO a -> m a

-- | Running a QIO computation evaluates it in the IO PMonad
run :: QIO a -> IO a

-- | Simulating a QIO computation evaluates it in the Prob PMonad
sim :: QIO a -> Prob a
instance PMonad Prob
instance Monad Prob
instance Show a => Show (Prob a)
instance PMonad IO
instance Monoid Unitary


-- | This module contains some simple examples of quantum computations
--   written using the Quantum IO Monad.
module QIO.QExamples

-- | Initialise a qubit in the |0&gt; state
q0 :: QIO Qbit

-- | Initialise a qubit in the |1&gt; state
q1 :: QIO Qbit

-- | Initialise a qubit in the |+&gt; state. This is done by applying a
--   Hadamard gate to the |0&gt; state.
qPlus :: QIO Qbit

-- | Initialise a qubit in the |-&gt; state. This is done by applying a
--   Hadamard gate to the |1&gt; state.
qMinus :: QIO Qbit

-- | Create a random Boolean value, by measuring the state |+&gt;
randBit :: QIO Bool

-- | This function can be used to <a>share</a> the state of one qubit, with
--   another newly initialised qubit. This is not the same as
--   <a>cloning</a>, as the two qubits will be in an entangled state.
--   <a>sharing</a> is achieved by simply initialising a new qubit in state
--   |0&gt;, and then applying a controlled-not to that qubit, depending on
--   the state of the given qubit.
share :: Qbit -> QIO Qbit

-- | A Bell state can be created by sharing the |+&gt; state
bell :: QIO (Qbit, Qbit)

-- | This function creates a Bell state, and then measures it. The
--   resulting pair of Booleans will always be in the same state as one
--   another.
test_bell :: QIO (Bool, Bool)

-- | This function initiaslised a qubit in the state corresponding to the
--   given Boolean value. The Hadamard transform (which is self-inverse) is
--   applied to the qubit twice, and then the qubit is measured. This
--   should correspond to the identity function on the given Boolean value.
hadTwice :: Bool -> QIO Bool

-- | A different implementation of <a>hadTwice</a> where QIO is used to
--   apply two unitaries, each of which is a single Hadamard gate, as
--   opposed to a single unitary, which is two Hadamard gates.
hadTwice' :: Bool -> QIO Bool

-- | The operations that Alice must perform in the classic quantum
--   teleportation example.
alice :: Qbit -> Qbit -> QIO (Bool, Bool)

-- | A definition of the Pauli-Z gate.
uZZ :: Qbit -> U

-- | The unitary operations that Bob must perform in the classic quantum
--   teleportation example.
bobsU :: (Bool, Bool) -> Qbit -> U

-- | The overall operations that Bob must perform in the classic quantum
--   teleportation example
bob :: Qbit -> (Bool, Bool) -> QIO Qbit

-- | The overall QIO computation that teleports the state of single qubit
teleportation :: Qbit -> QIO Qbit

-- | A small test function of quantum teleportation, which teleports a bell
--   state, and then measures it.
test_teleport :: QIO (Bool, Bool)

-- | teleports a qubit in the state |1&gt;
teleport_true' :: QIO Qbit

-- | teleports a qubit in the state |1&gt;, and then measures it
teleport_true :: QIO Bool

-- | teleports a qubit in the state |+&gt;
teleport_random' :: QIO Qbit

-- | teleports a qubit in the state |+&gt;, and then measures it.
teleport_random :: QIO Bool

-- | The implementation of Deutsch's algorithm requires a unitary to
--   represent the <a>oracle</a> function.
u :: (Bool -> Bool) -> Qbit -> Qbit -> U

-- | Deutsch's algorithm takes an <a>oracle</a> function, and returns a
--   Boolean that states whether the given function is balanced, or
--   consant.
deutsch :: (Bool -> Bool) -> QIO Bool

-- | A test QIO computation that is infinite in one measurement path. This
--   is a problem if we try to calculate the probability distribution of
--   possible results, as the infinite path will be followed.
problem :: QIO Bool


-- | This module contains QIO unitaries that represent various Arithmetic
--   functions. These are exactly the Arithmetic functions required to
--   implement Shor's algorithm.
module QIO.QArith

-- | A swap operation can be applied to two QInts, by mapping qubit swap
--   operations over the underlying qubits that make up a QInt.
swapQInt :: QInt -> QInt -> U

-- | ifElseQ defines a quantum If statement, whereby depending on the state
--   of the given (control) qubit, one of two unitaries are applied.
ifElseQ :: Qbit -> U -> U -> U

-- | ifQ defines a special case of ifElseQ, where the Else part of the
--   computation is simply the identity.
ifQ :: Qbit -> U -> U

-- | A controlled-not operations, that applies a Not to the second qubit,
--   depending on the state of the first qubit.
cnot :: Qbit -> Qbit -> U

-- | A three-qubit adder.
addBit :: Qbit -> Qbit -> Qbit -> U

-- | Calculates the carry (qu)bit.
carry :: Qbit -> Qbit -> Qbit -> Qbit -> U

-- | uses the <a>addBit</a> and <a>carry</a> unitaries to add the contents
--   of two quantum registers, setting an overflow bit if necessary. This
--   unitary makes use of a letU construct to introduce ancilla bits as
--   necessary.
addBits :: [Qbit] -> [Qbit] -> Qbit -> U

-- | An alternate implementation of <a>addBits</a> that is explicitly given
--   a register of ancilla qubits for all the intermediate <a>carry</a>
--   results.
addBits' :: [Qbit] -> [Qbit] -> [Qbit] -> Qbit -> U

-- | Defines the QIO unitary that adds two QInts, with an overflow qubit
adder :: QInt -> QInt -> Qbit -> U

-- | A small function to test the adder unitary
tadder :: (Int, (Int, Bool)) -> QIO (Int, (Int, Bool))

-- | A small function to test applying the adder unitary in reverse, ie.
--   this defines subtraction.
tRadder :: (Int, (Int, Bool)) -> QIO (Int, (Int, Bool))

-- | A small function to test applying the adder unitary, and then applying
--   the reverse of the adder unitary, which should give the identity
--   function.
tBiAdder :: (Int, (Int, Bool)) -> QIO (Int, (Int, Bool))

-- | This unitary is for modular addition, and is done modulo some fixed
--   classical modulus, given as the first Int argument.
adderMod :: Int -> QInt -> QInt -> U

-- | A small function to test the modular addition unitary.
tadderMod :: Int -> (Int, Int) -> QIO (Int, Int)

-- | This unitary defines modular multiplication, whereby the integer
--   <tt>n</tt> is the the modulus, and the integer <tt>a</tt> is the
--   scalar by which to multiply the quantum integer <tt>x</tt>. The result
--   is added to the quantum integer <tt>y</tt>, ie. if <tt>y</tt> is in
--   state 0 before the operation, then it is left in the sate a*x mod n.
multMod :: Int -> Int -> QInt -> QInt -> U

-- | A small function for testing the modular multiplication unitary. This
--   function initialises <tt>y</tt> as zero, so the output is as expected.
tmultMod :: Int -> Int -> Int -> QIO (Int, Int)

-- | A unitary that adds a single qubit control to modular multiplication
condMultMod :: Qbit -> Int -> Int -> QInt -> QInt -> U

-- | A classical Haskell function that returns the smalles positive inverse
--   of a `mod n (if one exists). That is, the smallest positive integer x,
--   such that x*a <a>mod</a> n equals 1.
inverseMod :: Int -> Int -> Int

-- | The unitary that represents modular exponentiation is constructed in
--   terms of multiple "steps". This function defines those steps.
modExpStep :: Qbit -> Int -> Int -> QInt -> Int -> U

-- | A QIO computation that forms a test of the <a>modExpStep</a> unitary
modExpStept :: Int -> Int -> Int -> Int -> QIO Int

-- | This function defines a unitary that implements modular
--   exponentiation, as required in Shor's algorithm. Given classical
--   arguments n and a, a quantum register containg x, and a quantum
--   register o in state 1, this unitary will leave the quantum register o
--   in the state a^x mod n.
modExp :: Int -> Int -> QInt -> QInt -> U

-- | A QIO computation that forms a test of the modular exponentiation
--   unitary.
modExpt :: Int -> (Int, Int) -> QIO Int


-- | This module implements various functions that return a probabilistic
--   result, defined as unitary operators, and quantum computations.
module QIO.QIORandom

-- | The exponentiated Pauli-X rotation
rX :: RR -> Rotation

-- | The exponentiated Pauli-Y rotation
rY :: RR -> Rotation

-- | Applies a Hadamard rotation to each qubit in the given list of qubits
hadamards :: [Qbit] -> U

-- | returns the highest integer power of 2 that is less than or equal to
--   x\
pow2 :: Int -> Int

-- | A rotation that, given a qubit in state 0, leaves it in a
--   super-position of 0 and 1, such that the probability of measuring as
--   state 0 is ps.
weightedU :: RR -> Qbit -> U

-- | A QIO computation that uses the <a>weightedU</a> unitary, to return a
--   Bool that has a probablity of pf of being False.
weightedBool :: RR -> QIO Bool

-- | removes any leading Falses from a list of booleans
rlf :: [Bool] -> [Bool]

-- | removes any leading Falses from the (big-endian) bit-wise
--   representation of the given Int.
rlf_l :: Int -> [Bool]

-- | returns the number of bits left after calling the <a>flf_l</a>
--   function
rlf_n :: Int -> Int

-- | Given an Int max that is the largest number required to be represented
--   in a quantum register, this function trims the front off the given
--   register, to leave the number of qubits required to represent max.
trim :: Int -> [Qbit] -> [Qbit]

-- | Given an Int max, and a quantum register in the state max, this
--   function defines a unitary operation that will leave the quantum
--   register in state that has equal probability of being measured in any
--   of the states 0 to max.
randomU :: Int -> [Qbit] -> U

-- | A quantum computation that will return a quantum integer in a state
--   that has equal probabilities of being measured in any of the state 0
--   to max.
randomQInt :: Int -> QIO QInt

-- | A quantum computation that will return a quantum integer in a state
--   that has equal probabilities of being measured in any of the state min
--   to max.
randomQIO :: (Int, Int) -> QIO Int

-- | A quantum computation that measures the outcome of <a>randomQInt</a>
randomInt :: Int -> QIO Int

-- | A quantum computation that returns an integer that is equally likely
--   to be any number in the range 0 to x-1
random :: Int -> QIO Int

-- | This function uses a Quantum computation to simulate the roll of a
--   dice
dice :: IO Int

-- | This function simulates the given number of repitions of dice rolls
dice_rolls :: Int -> IO [Int]

-- | Returns the number of occurences of 1 through 6 in the given list of
--   Ints
occs :: [Int] -> (Int, Int, Int, Int, Int, Int)

-- | Returns the number of occurences of 1 through 6 in the given number of
--   rolls of the dice.
probs' :: Int -> IO (Int, Int, Int, Int, Int, Int)

-- | Returns the percentage of occurences of 1 through 6, after the given
--   number of rolls of the dice.
probs :: Int -> IO (RR, RR, RR, RR, RR, RR)


-- | This module provides an implementation of the Quantum Fourier
--   Transform in QIO.
module QIO.Qft

-- | Defines the unitary the represents appliying a Quantum Fourier
--   Transform to the given quantum register.
qft :: [Qbit] -> U

-- | The definition of the QFT unitary makes use of an accumulator, to
--   repeatedly apply smaller QFTs to the tail of the given quantum
--   register.
qftAcu :: [Qbit] -> [Bool] -> [Bool] -> U

-- | The "base" step involved in a QFT is a series of controlled rotations.
qftBase :: [Bool] -> Qbit -> U

-- | The rotation used in the QFT is a phase rotation, parameterised by the
--   angle 1/(2^k)
rotK :: Int -> Qbit -> U

-- | A test of the QFT unitary, over a quantum integer initialised to n.
tryQft :: Int -> QIO Int


-- | This module defines the QIO computation that represents Shor's
--   factorisation algorithm. It makes use of the Arithmetic library, and
--   the Quantum Fourier Transform.
module QIO.Shor

-- | The inverse Quantum Fourier Transform is defined by reversing the QFT
qftI :: QInt -> U

-- | The Hadamard transform can be mapped over the qubits in a Quantum
--   Integer.
hadamardsI :: QInt -> U

-- | The overall "phase-estimation" structure of Shor's algorithm.
shorU :: QInt -> QInt -> Int -> Int -> U

-- | A quantum computation the implementes shor's algorithm, returning the
--   period of the function.
shor :: Int -> Int -> QIO Int

-- | A classical (inefficient) implementation of the period finding
--   subroutine
period :: Int -> Int -> Int

-- | A wrapper for Shor's algorithm, that returns prime factors of n.
factor :: Int -> QIO (Int, Int)

-- | This function simulates the running of a QIO computation, whilst using
--   System.Time functions to time how long the simulation took.
runTime :: QIO a -> IO a

-- | Times the running of various subroutines within the factorisation
--   algorithm.
factorV' :: Int -> IO (Int, Int)

-- | Calls the <a>factorV'</a>, and times the overall factorisation.
factorV :: Int -> IO ()

-- | This function defines a quantum computation that returns a random
--   index, that is used to pick from a list of integers that are co-prime
--   to n.
rand_coprime :: Int -> QIO Int

-- | A different implementation of <a>rand_coprime</a>, that defines a
--   quantum computation that returns a random number between 2 and n, that
--   is then returned if it is co-prime to n.
rand_co' :: Int -> QIO Int

-- | Integer division by 2.
half :: Int -> Int

-- | Reduces a pair of integers, by dividing them by thier gcd, until their
--   gcd is 1.
reduce :: (Int, Int) -> (Int, Int)