Commits

Jeffrino committed 69c83d5

qft

  • Participants
  • Parent commits 1ad933f

Comments (0)

Files changed (1)

 
 public class Shor
 {
-	public static void main(String[] args) throws MultiplyMatrixException
-	{
-		// Initialise variables n, q, x and rng
-		int n = Integer.valueOf(args[0]);
-		int q = 2;
-		int x;
+    public static void main(String[] args) throws MultiplyMatrixException
+    {
+        // Initialise variables n, q, x and rng
+        int n = Integer.valueOf(args[0]);
+        int q = 2;
+        int x;
 
-		// Used to select the value of x.
-		Random rng = new Random();
-		// Save Hadamard for use later.
-		Gate h = new Hadamard();
-		// Later, we add 1 each loop, so we cache this value so we don't instantiate each time.
-		final Complex constant = new Complex(1,0);
-		// Declare quantum registers that are to be used for Shor's Algorithm
-		QubitRegister inState,outState;
-		
-		int[] moddedExponents;
-		// Entangled is used twice in separate parts of program.
-		Complex[] entangled;
-		int value_position; // This... kind of makes sense.
+        // Used to select the value of x.
+        Random rng = new Random();
+        // Save Hadamard for use later.
+        Gate h = new Hadamard();
+        // Later, we add 1 each loop, so we cache this value so we don't instantiate each time.
+        final Complex constant = new Complex(1,0);
+        // Declare quantum registers that are to be used for Shor's Algorithm
+        QubitRegister inState,outState;
+        
+        int[] moddedExponents;
+        // Entangled is used twice in separate parts of program.
+        Complex[] entangled;
+        int value_position; // This... kind of makes sense.
 
-		// Find power of 2 that lies between n^2 and 2*n^2
-		while(q < n*n)
-			q *= 2;
-		// Making inverse discrete quantum fourier transform gate, same size as the register.
-		Gate iqft = new InverseQFT(q);
+        // Find power of 2 that lies between n^2 and 2*n^2
+        while(q < n*n)
+            q *= 2;
+        // Making inverse discrete quantum fourier transform gate, same size as the register.
+        Gate qft = new QFT(q);
 
-		//Create an array of complex numbers large enough to represent q in a register
-		entangled = new Complex[(int)Math.pow(2,findRegisterSize(n))];
-		// control variables - either we're done or we're taking too long.
-		boolean done = false, fail = false;
-		// Tracking our iterations.
-		int count = 0;
+        //Create an array of complex numbers large enough to represent q in a register
+        entangled = new Complex[(int)Math.pow(2,findRegisterSize(n))];
+        // control variables - either we're done or we're taking too long.
+        boolean done = false, fail = false;
+        // Tracking our iterations.
+        int count = 0;
 
-		while (!done)
-		{
-			// Generate a random x between 1 and n.
-			// It cannot be 1 or have a gcd of 1 with n (because then it's a factor).
-			x = rng.nextInt(n);
-			while((gcd(x,n) != 1) || (x <= 1))
-				x = rng.nextInt(n);
-			// An array of x^(0..q) mod n.
-			moddedExponents = new int[q];
-			// Adding to this before the break statement.
-			count++;
-			if (count > 20)
-			{
-				fail = true;
-				break;
-			}
+        while (!done)
+        {
+        	count++;
+            if (count > 20)
+            {
+                fail = true;
+                break;
+            }
+            // Generate a random x between 1 and n.
+            // It cannot be 1 or have a gcd of 1 with n (because then it's a factor).
+            x = rng.nextInt(n);
+            while((gcd(x,n) != 1) || (x <= 1))
+                x = rng.nextInt(n);
+            // An array of x^(0..q) mod n.
+            moddedExponents = new int[q];
+            // Adding to this before the break statement.
 
-			// the array used for entangling later is initially set to zero all over.
-			for(int i = 0; i < entangled.length; ++i)
-				entangled[i] = new Complex(0,0);
 
-			// Here We take the x^i mod n. moddedExponents[i] is assigned this while the entangled register's moddedExponent position
-			// is increased. This represents an increase in probability amplitude.
-			for(int i = 0; i < q; i++)
-			{
-				value_position = modularPower(x, i, n);
-				moddedExponents[i] = value_position;
-				entangled[value_position].addToMe(constant);
-			}
+            // the array used for entangling later is initially set to zero all over.
+            for(int i = 0; i < entangled.length; ++i)
+                entangled[i] = new Complex(0,0);
 
-			// After this we form the register from the complex array but it will need to be normalised.
-			outState = new QubitRegister(entangled);
-			outState.normalise();
+            // Here We take the x^i mod n. moddedExponents[i] is assigned this while the entangled register's moddedExponent position
+            // is increased. This represents an increase in probability amplitude.
+            for(int i = 0; i < q; i++)
+            {
+                value_position = modularPower(x, i, n);
+                moddedExponents[i] = value_position;
+                entangled[value_position].addToMe(constant);
+            }
 
-			// We now repurpose entangled, it is no longer needed for its previous purpose.
-			entangled = new Complex[q];
-			// Observing the output register to allow us to collapse the in register, see next comment.
-			int k = outState.observe();
-			// In a quantum computer, this register would automatically collapse into the correct state.
-			// However, because this is a simulation, we must do it manually.
-			for(int i = 0; i < q; ++i)
-				if(moddedExponents[i] == k)
-					entangled[i] = new Complex(1,0);
-				else
-					entangled[i] = new Complex();
-			inState = new QubitRegister(entangled);
-			inState.normalise();
-	
-			// This will hopefully transform the register into a particular value...
-			inState = inState.multiply(iqft);
-			
-			// ...the observed value should be a multiple of a number formed from the period.
-			int multiple = inState.observe();
-			
-			// Occasionally it's not, this means we must start again because the register collapsed into the "wrong" state.
-			// Or that our choice of x was not 'good' enough - such is randomness.
-			if(multiple < 1)
-				continue;
+            // After this we form the register from the complex array but it will need to be normalised.
+            outState = new QubitRegister(entangled);
+            outState.normalise();
 
-			// c is this multiple divided by q from the beginning of the program, we now want the rational approximation to this.
-			double c = (double)multiple/(double)q;
+            // We now repurpose entangled, it is no longer needed for its previous purpose.
+            entangled = new Complex[q];
+            // Observing the output register to allow us to collapse the in register, see next comment.
+            int k = outState.observe();
+            // In a quantum computer, this register would automatically collapse into the correct state.
+            // However, because this is a simulation, we must do it manually.
+            for(int i = 0; i < q; ++i)
+                if(moddedExponents[i] == k)
+                    entangled[i] = new Complex(1,0);
+                else
+                    entangled[i] = new Complex();
+            inState = new QubitRegister(entangled);
+            inState.normalise();
+    
+            // This will hopefully transform the register into a particular value...
+            inState = inState.multiply(qft);
+            
+            // ...the observed value should be a multiple of a number formed from the period.
+            int multiple = inState.observe();
+            
+            // Occasionally it's not, this means we must start again because the register collapsed into the "wrong" state.
+            // Or that our choice of x was not 'good' enough - such is randomness.
+            if(multiple < 1)
+                continue;
 
-			// So we get it from this function.
-			int bestDenominator = findDenominator(c,q);
-			// If the denominator isn't even, it won't work. However, if twice this value is still less than q, we can use
-			// twice the approximation instead.
-			if(bestDenominator % 2 == 0)
-				if(bestDenominator*2 < q)
-					bestDenominator *= 2;
-				else
-					continue;
+            // c is this multiple divided by q from the beginning of the program, we now want the rational approximation to this.
+            double c = (double)multiple/(double)q;
 
-			// There are two roots formed from this expression; the GCD of each with n is calculated. Hopefully, we have
-			// some nontrivial ones! OTOH the program can return 1 and n.
-			int expd = modularPower(x, bestDenominator/2, n);
-			int a = (expd + 1) % n;
-			int b = (expd + n - 1) % n;
-			System.out.println(gcd(n,a));
-			System.out.println(gcd(n,b));
-			done = true;
-		}
-		if (fail)
-			System.out.println("Algorithm failed!");
-			
-		System.exit(0);
-	}
+            // So we get it from this function.
+            int bestDenominator = findDenominator(c,q);
+            // If the denominator isn't even, it won't work. However, if twice this value is still less than q, we can use
+            // twice the approximation instead.
+            if(bestDenominator % 2 == 0)
+                if(bestDenominator*2 < q)
+                    bestDenominator *= 2;
+                else
+                    continue;
+
+            // There are two roots formed from this expression; the GCD of each with n is calculated. Hopefully, we have
+            // some nontrivial ones! OTOH the program can return 1 and n.
+            int expd = modularPower(x, bestDenominator/2, n);
+            int a = (expd + 1) % n;
+            int b = (expd + n - 1) % n;
+            System.out.println(gcd(n,a));
+            System.out.println(gcd(n,b));
+            done = true;
+        }
+        if (fail)
+            System.out.println("Algorithm failed!");
+            
+        System.exit(0);
+    }
 
 /* From this point on in the file there are only utility functions that
  * would only obfuscate if in the main body of code.*/
 
-	// Recursively calculates the greatest common divisor of ints a and b.
-	public static int gcd(int a, int b)
-	{
-		if(b == 0)
-			return a;
-		else
-			return gcd(b, a % b);
-	}
+    // Recursively calculates the greatest common divisor of ints a and b.
+    public static int gcd(int a, int b)
+    {
+        if(b == 0)
+            return a;
+        else
+            return gcd(b, a % b);
+    }
 
-	// Calculates a^b mod n, taking the modulus throughout the calculation such that the intermediate values probably
-	// won't overflow. If they were that large the VM would run out of memory before getting to this stage anyway.
-	public static int modularPower(int a, int b, int n)
-	{
-		int rtn = 1;
-		for(int i = 0; i < b; ++i)
-		{
-			rtn *= a;
-			rtn %= n;
-		}
-		return rtn;
-	}
+    // Calculates a^b mod n, taking the modulus throughout the calculation such that the intermediate values probably
+    // won't overflow. If they were that large the VM would run out of memory before getting to this stage anyway.
+    public static int modularPower(int a, int b, int n)
+    {
+        int rtn = 1;
+        for(int i = 0; i < b; ++i)
+        {
+            rtn *= a;
+            rtn %= n;
+        }
+        return rtn;
+    }
 
-	// If we had a register holding a value n, what is its minimum size?
-	public static int findRegisterSize(int n)
-	{
-		int size = 0;
-		while(n != 0)
-		{
-			n /= 2;
-			size++;
-		}
-		return size;
-	}
+    // If we had a register holding a value n, what is its minimum size?
+    public static int findRegisterSize(int n)
+    {
+        int size = 0;
+        while(n != 0)
+        {
+            n /= 2;
+            size++;
+        }
+        return size;
+    }
 
-	// Finds the closest rational approximation to c where the denominator is less than maxQ.
-	// Uses method of continued fractions.
-	public static int findDenominator(double c, int maxQ)
-	{
-		double z, y = c;
-		int q0 = 0;
-		int q1 = 1;
-		int q2 = 0;
-		while(true)
-		{
-			z = y - Math.floor(y);
-			if (z < 0.5 /(maxQ*maxQ))
-				return q1;
-			if (z != 0)
-				y = 1 / z;
-			else
-				return q1;
-			q2 = (int)Math.floor(y)*q1 + q0;
-			if (q2 >= maxQ)
-				return q1;
-			q0 = q1;
-			q1 = q2;
-		}
-	}
+    // Finds the closest rational approximation to c where the denominator is less than maxQ.
+    // Uses method of continued fractions.
+    public static int findDenominator(double c, int maxQ)
+    {
+        double z, y = c;
+        int q0 = 0;
+        int q1 = 1;
+        int q2 = 0;
+        while(true)
+        {
+            z = y - Math.floor(y);
+            if (z < 0.5 /(maxQ*maxQ))
+                return q1;
+            if (z != 0)
+                y = 1 / z;
+            else
+                return q1;
+            q2 = (int)Math.floor(y)*q1 + q0;
+            if (q2 >= maxQ)
+                return q1;
+            q0 = q1;
+            q1 = q2;
+        }
+    }
 }
-