QIO-1.2: The Quantum IO Monad is a library for defining quantum computations in Haskell

Safe HaskellSafe-Infered



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



qftI :: QInt -> USource

The inverse Quantum Fourier Transform is defined by reversing the QFT

hadamardsI :: QInt -> USource

The Hadamard transform can be mapped over the qubits in a Quantum Integer.

shorU :: QInt -> QInt -> Int -> Int -> USource

The overall "phase-estimation" structure of Shor's algorithm.

shor :: Int -> Int -> QIO IntSource

A quantum computation the implementes shor's algorithm, returning the period of the function.

period :: Int -> Int -> IntSource

A classical (inefficient) implementation of the period finding subroutine

factor :: Int -> QIO (Int, Int)Source

A wrapper for Shor's algorithm, that returns prime factors of n.

runTime :: QIO a -> IO aSource

This function simulates the running of a QIO computation, whilst using System.Time functions to time how long the simulation took.

factorV' :: Int -> IO (Int, Int)Source

Times the running of various subroutines within the factorisation algorithm.

factorV :: Int -> IO ()Source

Calls the factorV', and times the overall factorisation.

rand_coprime :: Int -> QIO IntSource

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_co' :: Int -> QIO IntSource

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.

half :: Int -> IntSource

Integer division by 2.

reduce :: (Int, Int) -> (Int, Int)Source

Reduces a pair of integers, by dividing them by thier gcd, until their gcd is 1.