gJW6;      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : SafeA 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 listmThe "probability" of an object in a Vector, is the sum of all the probabilities associated with that object.jA Vector can be multiplied by a scalar, by mapping the multiplcation over each probability in the vector.3Two Vectors can be added, using list concatenation.7Vectors, over Numeric types, can be defined as a Monad.     None9;I- The QIO! type forms a Monad, by wrapping  ,The type of the initial algebra for UFunctor<We fix the non-recursice data-type in order to get our type  of unitary operations.;The non-recursive data type definition of a QIO computation,The type of the initial algebra for UFunctorThe type of an F-Algebra.<We fix the non-recursice data-type in order to get our type  of unitary operations.The fix point type construtor.=The non-recursive data type definition of a unitary operation;A rotation is in essence a two-by-two complex valued matrix 8The type of Qubits in QIO are simply integer references."cFor Complex numbers, we use the built in Complex numbers, over our Real number type (i.e. Double)#8For Real numbers, we simply use the built in Double type$;The amplitude of a complex number is the magnitude squared.%The identity rotation&The not rotation'The hadamard rotation(The phase rotation)6Returns the inverse (or reverse) of the given rotation*We can define the inverse of Fx++We can now define the initial algebra for U,FWe can use a catamorphism to abstract evaluation over a given algebra-+Apply the given rotation to the given qubit.&Swap the state of the two given qubits/HApply the conditional unitary, depending on the value of the given qubit0IIntroduce an Ancilla qubit in the given state, for use in the sub-unitary1'Apply a not rotation to the given qubit2,Apply a hadamard rotation to the given qubit3>Apply a phase rotation (of the given angle) to the given qubit4TReturns the inverse (or reverse) of the given unitary operation, using an F-Algebra5+We can now define the initial algebra for U6We can remove the wrapper.7NInitialise a qubit in the given state (adding it to the overall quantum state)8>Apply the given unitary operation to the current quantum state9Measure the given qubit, and return the measurement outcome (note that this operation may affect the overall quantum state, as a measurement is destructive):FWe can count the number of each primitive operation using an F-Algebra=1We can show a QIO computation, using an F-Algebra>The wrapper type ApplyFix forms a MonadA!In order to define an F-Algebra, UF must be a functor.B@We can display a representation of a unitary, using an F-AlgebraC The type U forms a Monoid. D!In order to define an F-Algebra,  must be a functor.EVRotations can be compared for equality. They are equal if the define the same matrix.F6We can display the matrix representation of a rotationG We can display a qubit reference=  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFG2  !"#$%&'()*+,-./0123456789:;<=#"$ !GF%&'()ED*+,C-./01234BA 5 6@?>789=:;<1   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGNone9;IL-The underlying data type of a QIO ComputationQ1The underlying data type of a U unitary operationW;A rotation is in essence a two-by-two complex valued matrixX8The type of Qubits in QIO are simply integer references.ZcFor Complex numbers, we use the built in Complex numbers, over our Real number type (i.e. Double)[8For 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_HApply the conditional unitary, depending on the value of the given qubit`IIntroduce an Ancilla qubit in the given state, for use in the sub-unitarya?Returns the inverse (or reverse) of the given unitary operationb'Apply a not rotation to the given qubitc,Apply a hadamard rotation to the given qubitd>Apply a phase rotation (of the given angle) to the given qubiteNInitialise a qubit in the given state (adding it to the overall quantum state)f>Apply the given unitary operation to the current quantum stategMeasure the given qubit, and return the measurement outcome (note that this operation may affect the overall quantum state, as a measurement is destructive)hThe identity rotationiThe not rotationjThe hadamard rotationkThe phase rotationl6Returns the inverse (or reverse) of the given rotationm,A helper function for the show instance of Un5A helper function that returns a string of 4x spaces.o,We can display a representation of a unitaryp6We can display the matrix representation of a rotationq We can display a qubit referencerVRotations can be compared for equality. They are equal if the define the same matrix.sThe QIO type forms a Monadv The type U forms a Monoid +LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv#LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn+[Z\XYWQRSTUVLMNOPv]^_`abcdutsefghijklrqpomn!LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvNone<=? {CA Quantum integer is a wrapper around a fixed-length list of qubits}The }D type class defines the operation a quantum datatype must implement.1A recursive conditional on a list of quantum datahQuantum integers are of a fixed length, which is defined by this constant. Currently, this is set to 4.(Convert an integer to a list of Booleans(Convert a list of Booleans to an integer\quantum integers form a quantum data type, relating them to the classical Haskell Int type.2A list of quantum data is also a quantum data type;A pair of quantum data types is itself a quantum data type.OThe lowest-level instance of Qdata is the relation between Booleans and Qubits.{|}~ {|}~}~{| {|}~None9;HHeapMap is simply a type synonym for a Map from Qubits to Boolean valuesThe Heap Type Class define an  (i.e. empty) Heap? the value of a Qubit within the Heap to the given Boolen value>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 HeapxA HeapMap is an instance of the Heap type class, where the Heap functions can make use of the underlying Map functions.None 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.eA classical unitary operation is defined as a function that will update the current classical state.A single qubit rotation can be converted into the classical unitary type, if it is indeed classical (otherwise an error is thrown).>A swap operation can be defined in the classical unitary type.EA conditional operation can be defined in the classical unitary type.=A let operation can be defined in the classical unitary type.FA unitary can be run by converting it into the classical unitary type.ZAn initial state is defined as an empty heap, with 0 set as the next free qubit refereceVA QIO computation can be converted into a stateful computation, over a state of type StateC.We 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 None%&9;_We can define a datatype that holds EqMonad operations, so that it can be defined as a Monad. ~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.This type is a wrapper around a list of pairs.KAny type that fulfills this type class is a Vector over types with equalityAn empty instance of the vectorTwo Vectors can be combined&A Vector can be multiplied by a scalar0The amplitude of a given element can be accessed.The vector can be created from a list of pairs0The cevtor can be converted into a list of pairs2An empty VecEqL is a wrapper around the empty listA 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.VCombining two vectors is achieved by folding the add operation over the second vectorScalar 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.jThe amplitude of an element can be found by looking through each element until the matchinf one is found.EGiven Equality, we can unembed the EqMonad operations from an AsMonad4We 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 classNoneMThe type Prob is defined as a wrapper around Vectors with Real probabilities.We can extend a Monad into a PMonad if it defines a way of probabilistically merging two computations, based on a given probability.FA Split, is defined as a probability, along with the two Pure states. A quantum state is a defined as the next free qubit reference, along with the Pure state that represents the overall quantum stateA UnitaryO can be thought of as an operation on a HeapMap that may produce a Pure state.A Purep state can be thought of as a vector of classical basis states, stored as Heaps, along with complex amplitudes.eThe state of a qubit can be updated in a Pure state, by mapping the update operation over each Heap."A function that checks if a given Rotation 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)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.#A rotation can be converted into a Unitary , using the  function,A swap operation can be defined as a Unitary3A conditional operation can be defined as a Unitary+A let operation can be defined as a UnitaryAny member of the U3 type can be "run" by converting it into a Unitary. The initial 7Given a Pure state, return a sum of all the amplitudes.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.nGiven a PMonad, a QIO Computation can be converted into a Stateful computation over a quantum state (of type ).}A QIO computation is evaluated by converting it into a stateful computation and then evaluating that over the initial state.7Running a QIO computation evaluates it in the IO PMonad<Simulating a QIO computation evaluates it in the Prob PMonadkProb is also a PMonad, where the result of both computations are combined into a probability distribution.Prob forms a MonadZWe can show a probability distribution by filtering out elements with a zero probability.qIO forms a PMonad, using the random number generator to pick one of the "merged" computations probabilistically.The Unitary type forms a Monoid(!( None#Initialise a qubit in the |0> state#Initialise a qubit in the |1> statedInitialise a qubit in the |+> state. This is done by applying a Hadamard gate to the |0> state. `Initialise 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 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>, and then applying a controlled-not to that qubit, depending on the state of the given qubit.4A Bell state can be created by sharing the |+> stateThis function creates a Bell state, and then measures it. The resulting pair of Booleans will always be in the same state as one another.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.A different implementation of  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. UThe operations that Alice must perform in the classic quantum teleportation example.!A definition of the Pauli-Z gate.[The unitary operations that Bob must perform in the classic quantum teleportation example.ZThe overall operations that Bob must perform in the classic quantum teleportation exampleDThe overall QIO computation that teleports the state of single qubitdA small test function of quantum teleportation, which teleports a bell state, and then measures it."teleports a qubit in the state |1>8teleports a qubit in the state |1>, and then measures it"teleports a qubit in the state |+>9teleports a qubit in the state |+>, and then measures it.aThe implementation of Deutsch's algorithm requires a unitary to represent the "oracle" function.Deutsch's algorithm takes an "oracle" function, and returns a Boolean that states whether the given function is balanced, or consant.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. NoneA swap operation can be applied to two QInts, by mapping qubit swap operations over the underlying qubits that make up a QInt.ifElseQ defines a quantum If statement, whereby depending on the state of the given (control) qubit, one of two unitaries are applied.fifQ defines a special case of ifElseQ, where the Else part of the computation is simply the identity.qA 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 registers, setting an overflow bit if necessary. This unitary makes use of a letU construct to introduce ancilla bits as necessary.An alternate implementation of Q that is explicitly given a register of ancilla qubits for all the intermediate  results.DDefines the QIO unitary that adds two QInts, with an overflow qubit *A small function to test the adder unitary ^A small function to test applying the adder unitary in reverse, ie. this defines subtraction. A small function to test applying the adder unitary, and then applying the reverse of the adder unitary, which should give the identity function. xThis unitary is for modular addition, and is done modulo some fixed classical modulus, given as the first Int argument. 6A small function to test the modular addition unitary. AThis unitary defines modular multiplication, whereby the integer n& is the the modulus, and the integer a9 is the scalar by which to multiply the quantum integer x-. The result is added to the quantum integer y , ie. if yM is in state 0 before the operation, then it is left in the sate a*x mod n.\A small function for testing the modular multiplication unitary. This function initialises y' as zero, so the output is as expected.DA unitary that adds a single qubit control to modular multiplicationA 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 ; n equals 1. The 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  unitaryThis 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.JA QIO computation that forms a test of the modular exponentiation unitary.                     None"The exponentiated Pauli-X rotation"The exponentiated Pauli-Y rotationEApplies a Hadamard rotation to each qubit in the given list of qubitsGreturns the highest integer power of 2 that is less than or equal to x\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.rA QIO computation that uses the "weightedU" unitary, to return a Bool that has a probablity of pf of being False.2removes any leading Falses from a list of booleans[removes any leading Falses from the (big-endian) bit-wise representation of the given Int.Breturns the number of bits left after calling the "flf_l" functionGiven 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.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. 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.!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."?A quantum computation that measures the outcome of "randomQInt"#lA quantum computation that returns an integer that is equally likely to be any number in the range 0 to x-1$GThis function uses a Quantum computation to simulate the roll of a dice%CThis function simulates the given number of repitions of dice rolls&IReturns the number of occurences of 1 through 6 in the given list of Ints'ZReturns the number of occurences of 1 through 6 in the given number of rolls of the dice.(bReturns the percentage of occurences of 1 through 6, after the given number of rolls of the dice. !"#$%&'( !"#$%&'( !"#$%&'( !"#$%&'( None)hDefines the unitary the represents appliying a Quantum Fourier Transform to the given quantum register.*The definition of the QFT unitary makes use of an accumulator, to repeatedly apply smaller QFTs to the tail of the given quantum register.+FThe "base" step involved in a QFT is a series of controlled rotations.,VThe rotation used in the QFT is a phase rotation, parameterised by the angle 1/(2^k)-CA test of the QFT unitary, over a quantum integer initialised to n.)*+,-)*+,-)*+,-)*+,- None .EThe inverse Quantum Fourier Transform is defined by reversing the QFT/JThe Hadamard transform can be mapped over the qubits in a Quantum Integer.0=The overall "phase-estimation" structure of Shor's algorithm.1^A quantum computation the implementes shor's algorithm, returning the period of the function.2JA classical (inefficient) implementation of the period finding subroutine 3@A wrapper for Shor's algorithm, that returns prime factors of n.4This function simulates the running of a QIO computation, whilst using System.Time functions to time how long the simulation took.5LTimes the running of various subroutines within the factorisation algorithm.6 Calls the 5&, and times the overall factorisation.7This 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.8A 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.9Integer division by 2.:RReduces a pair of integers, by dividing them by thier gcd, until their gcd is 1. ./0123456789: ./0123456789: ./0123456789: ./0123456789:< !"#$%&'()*+,--./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVW #'()*+,--./09:;<@=>?CDE12345XYZRSQJKL[TUVW\\]^_`abcdefghijklmnopqrsstuv#wxyz{|}~#w                   QIO-1.3-1eKkI0ghl3b2AYYzatWGbbQIO.Vec QIO.QioSynAlt QIO.QioSyn QIO.QdataQIO.Heap QIO.QioClass QIO.VecEqQIO.Qio QIO.QExamples QIO.QArith QIO.QIORandomQIO.QftQIO.ShorVecunVecempty<@@><**><++> $fMonadVec$fApplicativeVec $fFunctorVec $fShowVecQIOApplyQIOInitialAlgebraQIOprim QIOFunctorQReturnMkQbitApplyUMeasUInitialAlgebraAlgebraUFixFxUFunctorUReturnRotSwapCondUletRotationQbitCCRRampridrnotrhadrphaserrevunFixuInitialAlgebracatarotswapconduletunotuhaduphaseurevqioInitialAlgebraprimQIOmkQbitapplyUmeasQbitcounttoffoliand $fShowQIO $fMonadQIO$fApplicativeQIO $fFunctorQIO$fFunctorQIOFunctor $fShowFix $fMonoidFix$fFunctorUFunctor$fEq(->) $fShow(->) $fShowQbit $fNumQbit $fEnumQbit$fEqQbit $fOrdQbitshow'spaces$fShowU $fMonoidUQIntQdatamkQmeasQletUcondQcondQRecqIntSizeint2bitsbits2int$fQdataIntQInt $fQdata[][] $fQdata(,)(,)$fQdataBoolQbit $fShowQIntHeapMapHeapinitialupdate?forgethswap $fHeapMapStateCfvheapUnitaryCunUuRotCuSwapCuCondCuLetCrunUC initialStateC runQStateCrunC$fMonoidUnitaryCAsMonadEmbedReturnBindEqMonadeqReturneqBindVecEqLunVecEqLVecEqvzero<+><.><@>fromListtoListvEqZeroaddvEqPlusvEqTimesvEqAtunEmbed$fMonadAsMonad$fApplicativeAsMonad$fFunctorAsMonad $fEqMonadv $fVecEqVecEqL $fShowVecEqLProbunProbPMonadmergeSplitpifTrueifFalseStateQfree pureStateUnitaryPureupdateP unitaryRotuMatrixuRotuSwapuConduLetrunU initialStateQpasplitevalWithevalrunsim $fPMonadProb $fMonadProb$fApplicativeProb $fFunctorProb $fShowProb $fPMonadIO$fMonoidUnitaryq0q1qPlusqMinusrandBitsharebell 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'halfreducebaseGHC.Realmod