QIO.Shor

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

Documentation

qftI :: QInt -> U

The inverse Quantum Fourier Transform is defined by reversing the QFT

hadamardsI :: QInt -> U

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

shorU :: QInt -> QInt -> Int -> Int -> U

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

shor :: Int -> Int -> QIO Int

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

period :: Int -> Int -> Int

A classical (inefficient) implementation of the period finding subroutine

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

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

runTime :: QIO a -> IO a

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)

Times the running of various subroutines within the factorisation algorithm.

factorV :: Int -> IO ()

Calls the factorV', and times the overall factorisation.

rand_coprime :: Int -> QIO Int

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

half :: Int -> Int

Integer division by 2.

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

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