QIO.QArith

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

Documentation

swapQInt :: QInt -> QInt -> U

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

ifElseQ :: Qbit -> U -> U -> U

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

ifQ :: Qbit -> U -> U

ifQ defines a special case of ifElseQ, where the Else part of the computation is simply the identity.

cnot :: Qbit -> Qbit -> U

A controlled-not operations, that applies a Not to the second qubit, depending on the state of the first qubit.

addBit :: Qbit -> Qbit -> Qbit -> U

A three-qubit adder.

carry :: Qbit -> Qbit -> Qbit -> Qbit -> U

Calculates the carry (qu)bit.

addBits :: [Qbit] -> [Qbit] -> Qbit -> U

uses the addBit and carry 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] -> Qbit -> U

An alternate implementation of addBits that is explicitly given a register of ancilla qubits for all the intermediate carry results.

adder :: QInt -> QInt -> Qbit -> U

Defines the QIO unitary that adds two QInts, with an overflow qubit

tadder :: (Int, (Int, Bool)) -> QIO (Int, (Int, Bool))

A small function to test the adder unitary

tRadder :: (Int, (Int, Bool)) -> QIO (Int, (Int, Bool))

A small function to test applying the adder unitary in reverse, ie. this defines subtraction.

tBiAdder :: (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.

adderMod :: Int -> QInt -> QInt -> U

This unitary is for modular addition, and is done modulo some fixed classical modulus, given as the first Int argument.

tadderMod :: Int -> (Int, Int) -> QIO (Int, Int)

A small function to test the modular addition unitary.

multMod :: Int -> Int -> QInt -> QInt -> U

This unitary defines modular multiplication, whereby the integer n is the the modulus, and the integer a 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 state 0 before the operation, then it is left in the sate a*x mod n.

tmultMod :: Int -> Int -> Int -> QIO (Int, Int)

A small function for testing the modular multiplication unitary. This function initialises y as zero, so the output is as expected.

condMultMod :: Qbit -> Int -> Int -> QInt -> QInt -> U

A unitary that adds a single qubit control to modular multiplication

inverseMod :: Int -> Int -> Int

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 mod n equals 1.

modExpStep :: Qbit -> Int -> Int -> QInt -> Int -> U

The unitary that represents modular exponentiation is constructed in terms of multiple "steps". This function defines those steps.

modExpStept :: Int -> Int -> Int -> Int -> QIO Int

A QIO computation that forms a test of the modExpStep unitary

modExp :: Int -> Int -> QInt -> QInt -> U

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.

modExpt :: Int -> (Int, Int) -> QIO Int

A QIO computation that forms a test of the modular exponentiation unitary.