++ed by:
2 non-PAUSE users

# NAME

``  shor - A short demonstration of Quantum::Entanglement``

# SYNOPSIS

`` ./shor.pl [number to factor (>14)]``

# DESCRIPTION

This program implements Shor's famous algorithm for factoring numbers. A brief overview of the algorithm is given below.

## The important maths

Given a number n which we are trying to factor, and some other number which we have guessed, x, we can say that:

`` x**0 % n == 1 (as x**0 = 1, 1 % n =1)``

There will also be some other number, r such that

`` x**r % n == 1``

or, more specifically,

`` x**(kr) % n ==1``

in other words, the function

`` F(a) = x**a % n``

is periodic with period r.

Now, starting from

`````` x**r = 1 % n

x**(2*r/2) = 1 % n

(x**(r/2))**2 - 1 = 0 % n``````

and, if r is an even number,

`` (x**(r/2) - 1)*(x**(r/2) + 1) = 0 mod n``

or in nice short words, the term on the left is an integer multiple of n. So long as x**(r/2) != +-1, at least one of the two brackets on the left must share a factor with n.

Shor's alorithm provides a way to find the periodicity of the function F and thus a way to calculate two numbers which share a factor with n, it is then easy to use a classical computer to find the GCD and thus a factor of n.

# The steps of the algorithm

## 1. Remove early trivial cases

We have efficient classical methods for finding that 2 is a factor of 26, so we do not need to use this method for this.

## 2. Pick an integer

Chose a number q so that `n**2 <= q <= 2n**2`, this is done on a classical computer. (This is the size we will use for our quantum register.)

## 3. Select at random a number coprime to n

Think of some number less than n so that n and x do not share a common factor (if they do, we already know the answer...).

## 4. Fill a quantum register with integers from 0..q-1

This is where we create our first entangled variable, and is the first non-classical step in this algorithm.

## 5. Calculate F, store in a second register

We now calculate ` F(a) = x**a % n` where a represents the superposition of states in our first register, we store the result of this in our second register.

## 6. Look at register2

We now look at the value of register two and get some value k, this forces register1 into a state which can only collapse into values satisfying the equation

`` x**a % n = k``

The probability amplitudes for the remaining states are now all equal to zero, note that we have not yet looked directly at register1.

## 7. Find period of register1

We now apply a fourier transform to the amplitudes of the states in register1, storing the result as the probability amplitudes for a new state with the values of register1. This causes there to be a high probability that the register will collapse to a value which is some multiple of `q/r`.

## 8. Observe register1

We now observe register1, and use the result to calculate a likely value for r. From this we can easily calculate two numbers, one of which will have a factor in common with n, by applying an efficient classical algoirthm for finding the greatest common denominator, we will be able to find a value which could be a factor of n.

# Things to remember

This algorithm does not claim to produce a factor of our number the first time that it is run, there are various conditions which will cause it to halt mid-way, for instance, the FT step can give a result of 0 which is clearly useless. The algorithm is better than any known classical one because the expectation value of the time required to get a correct answer is still O(n).

This also cannot factor a number which is prime (it being, as it were, prime) and also cannot factor something which is a prime power (25, say).

This code is copyright (c) Alex Gough (alex@rcon.org )2001. This is free software, you may use, modify and redistribute it under the same terms as Perl itself.

# BUGS

This is slow, being run on classical computers, ah well.