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

QIO.Shor

Description

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

Synopsis

# Documentation

qftI :: QInt -> U Source #

The inverse Quantum Fourier Transform is defined by reversing the QFT

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

shorU :: QInt -> QInt -> Int -> Int -> U Source #

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

shor :: Int -> Int -> QIO Int Source #

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

period :: Int -> Int -> Int Source #

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 a Source #

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.

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.

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.

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.