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


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

-- | Vectors, over Numeric types, can be defined as a Monad.
instance (GHC.Show.Show x, GHC.Show.Show a) => GHC.Show.Show (QIO.Vec.Vec x a)
instance GHC.Num.Num n => GHC.Base.Functor (QIO.Vec.Vec n)
instance GHC.Num.Num n => GHC.Base.Applicative (QIO.Vec.Vec n)
instance GHC.Num.Num n => GHC.Base.Monad (QIO.Vec.Vec n)


-- | This module defines the Syntax of the Quantum IO Monad, which is an
--   embedded language for writing quantum computations. It is an
--   alternative definition using the approach of defining F-Algebras.
module QIO.QioSynAlt

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

-- | We can display a qubit reference

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

-- | We can display the matrix representation of a rotation

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

-- | Rotations can be compared for equality. They are equal if the define
--   the same matrix.

-- | The non-recursive data type definition of a unitary operation
data UFunctor u
UReturn :: UFunctor u
Rot :: Qbit -> Rotation -> u -> UFunctor u
Swap :: Qbit -> Qbit -> u -> UFunctor u
Cond :: Qbit -> (Bool -> u) -> u -> UFunctor u
Ulet :: Bool -> (Qbit -> u) -> u -> UFunctor u

-- | In order to define an F-Algebra, <a>UFunctor</a> must be a functor.

-- | The fix point type construtor.
newtype Fix f
Fx :: (f (Fix f)) -> Fix f

-- | We can define the inverse of Fx
unFix :: Fix f -> f (Fix f)

-- | We fix the non-recursice data-type in order to get our type <a>U</a>
--   of unitary operations.
type U = Fix UFunctor

-- | The type of an F-Algebra.
type Algebra f a = f a -> a

-- | The type of the initial algebra for UFunctor
type UInitialAlgebra = Algebra UFunctor U

-- | We can now define the initial algebra for U
uInitialAlgebra :: UInitialAlgebra

-- | We can use a catamorphism to abstract evaluation over a given algebra
cata :: Functor f => Algebra f a -> Fix f -> a

-- | The type <a>U</a> forms a Monoid.

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

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

-- | Returns the inverse (or reverse) of the given unitary operation, using
--   an F-Algebra
urev :: U -> U

-- | We can display a representation of a unitary, using an F-Algebra

-- | The non-recursive data type definition of a QIO computation
data QIOFunctor a q
QReturn :: a -> QIOFunctor a q
MkQbit :: Bool -> (Qbit -> q) -> QIOFunctor a q
ApplyU :: U -> q -> QIOFunctor a q
Meas :: Qbit -> (Bool -> q) -> QIOFunctor a q

-- | In order to define an F-Algebra, <tt>UF</tt> must be a functor.

-- | We fix the non-recursice data-type in order to get our type <a>U</a>
--   of unitary operations.
type QIOprim a = Fix (QIOFunctor a)

-- | The type of the initial algebra for UFunctor
type QIOInitialAlgebra a = Algebra (QIOFunctor a) (QIOprim a)

-- | We can now define the initial algebra for U
qioInitialAlgebra :: QIOInitialAlgebra a

-- | The <a>QIO</a> type forms a Monad, by wrapping <a>QIOprim</a>
data QIO a
Apply :: (Fix (QIOFunctor a)) -> QIO a

-- | We can remove the wrapper.
primQIO :: QIO a -> QIOprim a

-- | The wrapper type <tt>ApplyFix</tt> forms a Monad

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

-- | We can show a QIO computation, using an F-Algebra

-- | We can count the number of each primitive operation using an F-Algebra
count :: QIO a -> (Int, Int, Int)
toffoli :: Qbit -> Qbit -> Qbit -> U
and :: Bool -> Bool -> QIO Bool
instance GHC.Classes.Ord QIO.QioSynAlt.Qbit
instance GHC.Classes.Eq QIO.QioSynAlt.Qbit
instance GHC.Enum.Enum QIO.QioSynAlt.Qbit
instance GHC.Num.Num QIO.QioSynAlt.Qbit
instance GHC.Show.Show QIO.QioSynAlt.Qbit
instance GHC.Show.Show QIO.QioSynAlt.Rotation
instance GHC.Classes.Eq QIO.QioSynAlt.Rotation
instance GHC.Base.Functor QIO.QioSynAlt.UFunctor
instance GHC.Base.Monoid QIO.QioSynAlt.U
instance GHC.Show.Show QIO.QioSynAlt.U
instance GHC.Base.Functor (QIO.QioSynAlt.QIOFunctor a)
instance GHC.Base.Functor QIO.QioSynAlt.QIO
instance GHC.Base.Applicative QIO.QioSynAlt.QIO
instance GHC.Base.Monad QIO.QioSynAlt.QIO
instance GHC.Show.Show a => GHC.Show.Show (QIO.QioSynAlt.QIO a)


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

-- | The type <a>U</a> forms a Monoid

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

-- | The <a>QIO</a> type forms a Monad

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

-- | Rotations can be compared for equality. They are equal if the define
--   the same matrix.

-- | We can display a qubit reference

-- | We can display the matrix representation of a rotation

-- | We can display a representation of a unitary

-- | 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 GHC.Classes.Ord QIO.QioSyn.Qbit
instance GHC.Classes.Eq QIO.QioSyn.Qbit
instance GHC.Enum.Enum QIO.QioSyn.Qbit
instance GHC.Num.Num QIO.QioSyn.Qbit
instance GHC.Base.Monoid QIO.QioSyn.U
instance GHC.Base.Functor QIO.QioSyn.QIO
instance GHC.Base.Applicative QIO.QioSyn.QIO
instance GHC.Base.Monad QIO.QioSyn.QIO
instance GHC.Classes.Eq QIO.QioSyn.Rotation
instance GHC.Show.Show QIO.QioSyn.Qbit
instance GHC.Show.Show QIO.QioSyn.Rotation
instance GHC.Show.Show QIO.QioSyn.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

-- | The lowest-level instance of Qdata is the relation between Booleans
--   and Qubits.

-- | A pair of quantum data types is itself a quantum data type.

-- | A list of quantum data is also a quantum data type

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

-- | quantum integers form a quantum data type, relating them to the
--   classical Haskell Int type.
instance GHC.Show.Show QIO.Qdata.QInt
instance QIO.Qdata.Qdata GHC.Types.Bool QIO.QioSyn.Qbit
instance (QIO.Qdata.Qdata a qa, QIO.Qdata.Qdata b qb) => QIO.Qdata.Qdata (a, b) (qa, qb)
instance QIO.Qdata.Qdata a qa => QIO.Qdata.Qdata [a] [qa]
instance QIO.Qdata.Qdata GHC.Types.Int QIO.Qdata.QInt


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

-- | define an <a>initial</a> (i.e. empty) Heap
initial :: Heap h => h

-- | <a>update</a> the value of a Qubit within the Heap to the given Boolen
--   value
update :: Heap h => h -> Qbit -> Bool -> h

-- | Lookup the value of the given Qubit in the Heap (if it exists)
(?) :: Heap h => h -> Qbit -> Maybe Bool

-- | remove the given Qubit from the Heap
forget :: Heap h => h -> Qbit -> h

-- | Swap the values associated with two Qubits within the Heap
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

-- | A HeapMap is an instance of the Heap type class, where the Heap
--   functions can make use of the underlying Map functions.
instance QIO.Heap.Heap QIO.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

-- | The classical unitary type forms a Monoid

-- | 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 GHC.Base.Monoid QIO.QioClass.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

-- | An empty instance of the vector
vzero :: VecEq v => v x a

-- | Two Vectors can be combined
(<+>) :: (VecEq v, Eq a, Num x) => v x a -> v x a -> v x a

-- | A Vector can be multiplied by a scalar
(<.>) :: (VecEq v, Num x, Eq x) => x -> v x a -> v x a

-- | The amplitude of a given element can be accessed
(<@>) :: (VecEq v, Eq a, Num x) => a -> v x a -> x

-- | The vector can be created from a list of pairs
fromList :: VecEq v => [(a, x)] -> v x a

-- | The cevtor can be converted into a list of pairs
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

-- | VecEqL is an instance of the VecEq class

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

-- | Any VecEq over v, along with a Numeric tpye x is an EqMonad.

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

-- | We can define an AsMonad over an EqMonad, as a Monad

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


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

-- | The Unitary type forms a Monoid

-- | 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
[pureState] :: 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 -> Split
[p] :: Split -> RR
[ifTrue, 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

-- | IO forms a PMonad, using the random number generator to pick one of
--   the "merged" computations probabilistically.

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

-- | We can show a probability distribution by filtering out elements with
--   a zero probability.

-- | Prob forms a Monad

-- | Prob is also a PMonad, where the result of both computations are
--   combined into a probability distribution.

-- | 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 GHC.Base.Monoid QIO.Qio.Unitary
instance QIO.Qio.PMonad GHC.Types.IO
instance GHC.Show.Show a => GHC.Show.Show (QIO.Qio.Prob a)
instance GHC.Base.Functor QIO.Qio.Prob
instance GHC.Base.Applicative QIO.Qio.Prob
instance GHC.Base.Monad QIO.Qio.Prob
instance QIO.Qio.PMonad QIO.Qio.Prob


-- | 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 "share" the state of one qubit, with
--   another newly initialised qubit. This is not the same as "cloning", as
--   the two qubits will be in an entangled state. "sharing" 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 "oracle" function.
u :: (Bool -> Bool) -> Qbit -> Qbit -> U

-- | Deutsch's algorithm takes an "oracle" 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 "weightedU" 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 "flf_l" 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 "randomQInt"
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 "rand_coprime", 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)