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)
The Hadamard transform can be mapped over the qubits in a Quantum Integer.
The overall "phase-estimation" structure of Shor's algorithm.
A quantum computation the implementes shor's algorithm, returning the period of the function.
A classical (inefficient) implementation of the period finding subroutine
A wrapper for Shor's algorithm, that returns prime factors of n.
This function simulates the running of a QIO computation, whilst using System.Time functions to time how long the simulation took.
Times the running of various subroutines within the factorisation algorithm.
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.