7X+T      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  Safe-InferedA Vector over types x and a is a wrapper around list of  pairs of a and x. -An empty Vector is defined as the empty list The " probability"1 of an object in a Vector, is the sum of all the , probabilities associated with that object. EA Vector can be multiplied by a scalar, by mapping the multiplcation & over each probability in the vector. 4Two Vectors can be added, using list concatenation. 8Vectors, over Numeric types, can be defined as a Monad. None.The underlying data type of a QIO Computation 2The underlying data type of a U unitary operation <A rotation is in essence a two-by-two complex valued matrix 9The type of Qubits in QIO are simply integer references. IFor Complex numbers, we use the built in Complex numbers, over our Real  number type (i.e. Double) 9For Real numbers, we simply use the built in Double type <The amplitude of a complex number is the magnitude squared. ,Apply the given rotation to the given qubit 'Swap the state of the two given qubits IApply the conditional unitary, depending on the value of the given qubit JIntroduce an Ancilla qubit in the given state, for use in the sub-unitary @Returns the inverse (or reverse) of the given unitary operation (Apply a not rotation to the given qubit -Apply a hadamard rotation to the given qubit ?Apply a phase rotation (of the given angle) to the given qubit OInitialise a qubit in the given state (adding it to the overall quantum state) !?Apply the given unitary operation to the current quantum state "LMeasure the given qubit, and return the measurement outcome (note that this R operation may affect the overall quantum state, as a measurement is destructive) #The identity rotation $The not rotation %The hadamard rotation &The phase rotation '7Returns the inverse (or reverse) of the given rotation (-A helper function for the show instance of U ),A helper function that returns a string of 4x spaces. -We can display a representation of a unitary 7We can display the matrix representation of a rotation !We can display a qubit reference (Rotations can be compared for equality. / They are equal if the define the same matrix. The QIO type forms a Monad  The type U forms a Monoid )  !"#$%&'()#  !"#$%&'()#    !"#$%&'()    !"#$%&'() Safe-Infered *DA Quantum integer is a wrapper around a fixed-length list of qubits ,The ,E type class defines the operation a quantum datatype must implement. 12A recursive conditional on a list of quantum data 2KQuantum integers are of a fixed length, which is defined by this constant.  Currently, this is set to 4. 3)Convert an integer to a list of Booleans 4)Convert a list of Booleans to an integer Jquantum integers form a quantum data type, relating them to the classical  Haskell Int type. 3A list of quantum data is also a quantum data type <A pair of quantum data types is itself a quantum data type. PThe lowest-level instance of Qdata is the relation between Booleans and Qubits. *+,-./01234 *+,-./01234 ,-./012*+34 *+,-./01234 Safe-Infered5IHeapMap is simply a type synonym for a Map from Qubits to Boolean values 6The Heap Type Class 7 define an 7 (i.e. empty) Heap 88@ the value of a Qubit within the Heap to the given Boolen value 9?Lookup the value of the given Qubit in the Heap (if it exists) :%remove the given Qubit from the Heap ;;Swap the values associated with two Qubits within the Heap JA HeapMap is an instance of the Heap type class, where the Heap functions / can make use of the underlying Map functions. 56789:;56789:;6789:;556789:; Safe-Infered <IA classical state consists of the next free qubit reference, along with J a Heap that represents the overall state of the current qubits in scope. @AA classical unitary operation is defined as a function that will % update the current classical state. CKA single qubit rotation can be converted into the classical unitary type, ; if it is indeed classical (otherwise an error is thrown). D?A swap operation can be defined in the classical unitary type. EFA conditional operation can be defined in the classical unitary type. F>A let operation can be defined in the classical unitary type. GGA unitary can be run by converting it into the classical unitary type. HFAn initial state is defined as an empty heap, with 0 set as the next  free qubit referece IEA QIO computation can be converted into a stateful computation, over  a state of type StateC. JHWe can run a classical QIO computation by converting it into a stateful ; computation, and evaluating that using the initial state. *The classical unitary type forms a Monoid <=>?@ABCDEFGHIJ<=>?@ABCDEFGHIJ@ABCDEFG<=>?HIJ <=>?@ABCDEFGHIJ Safe-InferedKGWe can define a datatype that holds EqMonad operations, so that it can  be defined as a Monad. OIAn EqMonad is a monad that has Return and Bind operations that depend on 6 the type in the monad being a member of the Eq class R/This type is a wrapper around a list of pairs. ULAny type that fulfills this type class is a Vector over types with equality V An empty instance of the vector WTwo Vectors can be combined X'A Vector can be multiplied by a scalar Y1The amplitude of a given element can be accessed Z/The vector can be created from a list of pairs [1The cevtor can be converted into a list of pairs \3An empty VecEqL is a wrapper around the empty list ]JA basis state with the given amplitude can be added to a VecEqL by adding K the amplitudes if the state is already in the vector, or by inserting the  base state if it isn't already in the vector. ^DCombining two vectors is achieved by folding the add operation over  the second vector _DScalar multiplcation is achieved by mapping the multiplication over J each pair in the vector. Multiplication by 0 is a special case, and will . remove all the basis states from the vector. `IThe amplitude of an element can be found by looking through each element " until the matchinf one is found. aFGiven Equality, we can unembed the EqMonad operations from an AsMonad 5We can define an AsMonad over an EqMonad, as a Monad Any VecEq over v, along with a Numeric tpye x is an EqMonad. )VecEqL is an instance of the VecEq class KLMNOPQRSTUVWXYZ[\]^_`aKLMNOPQRSTUVWXYZ[\]^_`aUVWXYZ[RST\]^_`OPQKNMLa KNMLOPQRSTUVWXYZ[\]^_`a Safe-InferedbNThe type Prob is defined as a wrapper around Vectors with Real probabilities. eMWe can extend a Monad into a PMonad if it defines a way of probabilistically 9 merging two computations, based on a given probability. gGA Split, is defined as a probability, along with the two Pure states. lNA quantum state is a defined as the next free qubit reference, along with the 6 Pure state that represents the overall quantum state pA UnitaryA can be thought of as an operation on a HeapMap that may produce  a Pure state. sA PureG state can be thought of as a vector of classical basis states, stored * as Heaps, along with complex amplitudes. tKThe state of a qubit can be updated in a Pure state, by mapping the update  operation over each Heap. u"A function that checks if a given Rotation is in face unitary. Note that J this is currently a dummy stub function, and states that any rotation is O 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) vKGiven the four complex numbers that make up a 2-by-2 matrix, we can create 9 a Unitary that applies the rotation to the given qubit. w#A rotation can be converted into a Unitary , using the v function x-A swap operation can be defined as a Unitary y4A conditional operation can be defined as a Unitary z,A let operation can be defined as a Unitary {Any member of the U type can be "run"" by converting it into a Unitary. | The initial l }8Given a Pure state, return a sum of all the amplitudes. ~HGiven a Pure state, we can create a Split, by essentially splitting the N state into the part where the qubit is True, and the part where the qubit is 9 False. This is how measurements are implemented in QIO. OGiven a PMonad, a QIO Computation can be converted into a Stateful computation  over a quantum state (of type l). LA QIO computation is evaluated by converting it into a stateful computation 2 and then evaluating that over the initial state. 8Running a QIO computation evaluates it in the IO PMonad =Simulating a QIO computation evaluates it in the Prob PMonad OProb is also a PMonad, where the result of both computations are combined into  a probability distribution. Prob forms a Monad FWe can show a probability distribution by filtering out elements with  a zero probability. HIO forms a PMonad, using the random number generator to pick one of the  "merged"! computations probabilistically.  The Unitary type forms a Monoid &bcdefghijklmnopqrstuvwxyz{|}~!bcdefghijklmnopqrstuvwxyz{|}~!stpqruvwxyz{lmno|}ghijk~efbcdbcdefghijklmnopqrstuvwxyz{|}~ Safe-Infered$Initialise a qubit in the |0> state $Initialise a qubit in the |1> state IInitialise a qubit in the |+> state. This is done by applying a Hadamard  gate to the |0> state. IInitialise a qubit in the |-> state. This is done by applying a Hadamard  gate to the |1> state. ;Create a random Boolean value, by measuring the state |+> This function can be used to share& the state of one qubit, with another 2 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 N a new qubit in state |0>, and then applying a controlled-not to that qubit, , depending on the state of the given qubit. 5A Bell state can be created by sharing the |+> state MThis function creates a Bell state, and then measures it. The resulting pair > of Booleans will always be in the same state as one another. KThis function initiaslised a qubit in the state corresponding to the given M Boolean value. The Hadamard transform (which is self-inverse) is applied to L the qubit twice, and then the qubit is measured. This should correspond to 3 the identity function on the given Boolean value. A different implementation of  where QIO is used to apply two L unitaries, each of which is a single Hadamard gate, as opposed to a single ( unitary, which is two Hadamard gates. LThe operations that Alice must perform in the classic quantum teleportation  example. "A definition of the Pauli-Z gate. DThe unitary operations that Bob must perform in the classic quantum  teleportation example. DThe overall operations that Bob must perform in the classic quantum  teleportation example EThe overall QIO computation that teleports the state of single qubit BA small test function of quantum teleportation, which teleports a # bell state, and then measures it. #teleports a qubit in the state |1> 9teleports a qubit in the state |1>, and then measures it #teleports a qubit in the state |+> :teleports a qubit in the state |+>, and then measures it. The implementation of Deutsch',s algorithm requires a unitary to represent  the oracle function. Deutsch's algorithm takes an oracle! function, and returns a Boolean A that states whether the given function is balanced, or consant. IA test QIO computation that is infinite in one measurement path. This is K a problem if we try to calculate the probability distribution of possible 1 results, as the infinite path will be followed.   Safe-InferedOA swap operation can be applied to two QInts, by mapping qubit swap operations 1 over the underlying qubits that make up a QInt. JifElseQ defines a quantum If statement, whereby depending on the state of > the given (control) qubit, one of two unitaries are applied. NifQ defines a special case of ifElseQ, where the Else part of the computation  is simply the identity. FA controlled-not operations, that applies a Not to the second qubit, , depending on the state of the first qubit. A three-qubit adder. Calculates the carry (qu)bit.  uses the  and . unitaries to add the contents of two quantum N registers, setting an overflow bit if necessary. This unitary makes use of a 8 letU construct to introduce ancilla bits as necessary. An alternate implementation of  that is explicitly given 7 a register of ancilla qubits for all the intermediate  results. EDefines the QIO unitary that adds two QInts, with an overflow qubit +A small function to test the adder unitary DA small function to test applying the adder unitary in reverse, ie.  this defines subtraction. GA small function to test applying the adder unitary, and then applying L the reverse of the adder unitary, which should give the identity function. DThis unitary is for modular addition, and is done modulo some fixed 5 classical modulus, given as the first Int argument. 7A small function to test the modular addition unitary. AThis unitary defines modular multiplication, whereby the integer n is the  the modulus, and the integer a0 is the scalar by which to multiply the quantum  integer x-. The result is added to the quantum integer y , ie. if y is in F state 0 before the operation, then it is left in the sate a*x mod n. OA small function for testing the modular multiplication unitary. This function  initialises y( as zero, so the output is as expected. EA unitary that adds a single qubit control to modular multiplication GA classical Haskell function that returns the smalles positive inverse  of a `mod n 8(if one exists). That is, the smallest positive integer  x, such that x*a  n  equals 1. KThe unitary that represents modular exponentiation is constructed in terms  of multiple "steps"%. This function defines those steps. +A QIO computation that forms a test of the  unitary KThis 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. KA QIO computation that forms a test of the modular exponentiation unitary.   Safe-Infered#The exponentiated Pauli-X rotation #The exponentiated Pauli-Y rotation FApplies a Hadamard rotation to each qubit in the given list of qubits Ereturns the highest integer power of 2 that is less than or equal to x\ LA 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.  A QIO computation that uses the  weightedU unitary, to return a Bool that  has a probablity of pf of being False. 3removes any leading Falses from a list of booleans Iremoves any leading Falses from the (big-endian) bit-wise representation  of the given Int. 2returns the number of bits left after calling the flf_l function  Given an Int max 9that is the largest number required to be represented in N a quantum register, this function trims the front off the given register, to 2 leave the number of qubits required to represent max.  Given an Int max,% and a quantum register in the state max, this function P defines a unitary operation that will leave the quantum register in state that C has equal probability of being measured in any of the states 0 to max. IA quantum computation that will return a quantum integer in a state that D has equal probabilities of being measured in any of the state 0 to max. IA 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. 3A quantum computation that measures the outcome of  randomQInt KA quantum computation that returns an integer that is equally likely to be  any number in the range 0 to x-1 HThis function uses a Quantum computation to simulate the roll of a dice DThis function simulates the given number of repitions of dice rolls JReturns the number of occurences of 1 through 6 in the given list of Ints GReturns the number of occurences of 1 through 6 in the given number of  rolls of the dice. LReturns the percentage of occurences of 1 through 6, after the given number  of rolls of the dice.   Safe-InferedIDefines the unitary the represents appliying a Quantum Fourier Transform  to the given quantum register. MThe definition of the QFT unitary makes use of an accumulator, to repeatedly ? apply smaller QFTs to the tail of the given quantum register. The "base"= step involved in a QFT is a series of controlled rotations. HThe rotation used in the QFT is a phase rotation, parameterised by the  angle 1/(2^k) AA test of the QFT unitary, over a quantum integer initialised to n.   Safe-Infered FThe inverse Quantum Fourier Transform is defined by reversing the QFT KThe Hadamard transform can be mapped over the qubits in a Quantum Integer.  The overall "phase-estimation" structure of Shor' s algorithm. *A quantum computation the implementes shor'"s algorithm, returning the period  of the function. KA classical (inefficient) implementation of the period finding subroutine A wrapper for Shor'+s algorithm, that returns prime factors of n. GThis function simulates the running of a QIO computation, whilst using = System.Time functions to time how long the simulation took. MTimes the running of various subroutines within the factorisation algorithm.  Calls the ', and times the overall factorisation. NThis 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. A different implementation of  rand_coprime, that defines a quantum 8 computation that returns a random number between 2 and n, that is then  returned if it is co-prime to n. Integer division by 2. <Reduces a pair of integers, by dividing them by thier gcd,  until their gcd is 1.    !"#$%&'()*+,-./01234556789:;<=>?@ABCDEFFGHIJKLMNOPQRSTUVWXYZZ[\]^_`abcdefghiijklmmnopqqrstJuvwxyz{|}~ QIO-1.2QIO.Vec QIO.QioSyn QIO.QdataQIO.Heap QIO.QioClass QIO.VecEqQIO.Qio QIO.QExamples QIO.QArith QIO.QIORandomQIO.QftQIO.ShorVecunVecempty<@@><**><++>QIOMeasApplyUMkQbitQReturnUUletCondSwapRotUReturnRotationQbitCCRRamprotswapconduleturevunotuhaduphasemkQbitapplyUmeasQbitridrnotrhadrphaserrevshow'spacesQIntQdatamkQmeasQletUcondQcondQRecqIntSizeint2bitsbits2intHeapMapHeapinitialupdate?forgethswapStateCfvheapUnitaryCunUuRotCuSwapCuCondCuLetCrunUC initialStateC runQStateCrunCAsMonadBindReturnEmbedEqMonadeqReturneqBindVecEqLunVecEqLVecEqvzero<+><*><@>fromListtoListvEqZeroaddvEqPlusvEqTimesvEqAtunEmbedProbunProbPMonadmergeSplitpifTrueifFalseStateQfreepureUnitaryPureupdateP unitaryRotuMatrixuRotuSwapuConduLetrunU initialStateQpasplitevalWithevalrunsimq0q1qPlusqMinusrandBitsharebell test_bellhadTwice hadTwice'aliceuZZbobsUbob teleportation test_teleportteleport_true' teleport_trueteleport_random'teleport_randomudeutschproblemswapQIntifElseQifQcnotaddBitcarryaddBitsaddBits'addertaddertRaddertBiAdderadderMod tadderModmultModtmultMod condMultMod inverseMod modExpStep modExpSteptmodExpmodExptrXrY hadamardspow2 weightedU weightedBoolrlfrlf_lrlf_ntrimrandomU randomQInt randomQIO randomIntrandomdice dice_rollsoccsprobs'probsqftqftAcuqftBaserotKtryQftqftI hadamardsIshorUshorperiodfactorrunTimefactorV'factorV rand_coprimerand_co'halfreduce $fMonadVec$fShowU $fShow(->) $fShowQbit$fEq(->) $fMonadQIO $fMonoidU$fQdataIntQInt $fQdata[][] $fQdata(,)(,)$fQdataBoolQbit $fHeapMap$fMonoidUnitaryC$fMonadAsMonad $fEqMonadv $fVecEqVecEqL $fPMonadProb $fMonadProb $fShowProb $fPMonadIO$fMonoidUnitarybaseGHC.Realmod