Safe Haskell | Safe-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 -> U
- hadamardsI :: QInt -> U
- shorU :: QInt -> QInt -> Int -> Int -> U
- shor :: Int -> Int -> QIO Int
- period :: Int -> Int -> Int
- factor :: Int -> QIO (Int, Int)
- runTime :: QIO a -> IO a
- factorV' :: Int -> IO (Int, Int)
- factorV :: Int -> IO ()
- rand_coprime :: Int -> QIO Int
- rand_co' :: Int -> QIO Int
- half :: Int -> Int
- reduce :: (Int, Int) -> (Int, Int)

# Documentation

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.

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.