Commits

Duncan McBain  committed 98ea026

comments for shor

  • Participants
  • Parent commits ab7b7f3

Comments (0)

Files changed (2)

 numbers. They are extended to form Qubits and Gates which will happily multiply
 and form tensor products. Who knows, they might even produce the right answer.
 There is also an implementation of Grover's Algorithm, which is invoked by 
-java Grover listsize element
+java Grover listsize element [-g]
+and shor's alogorithm
+java Shor N
 		boolean done = false, fail = false;
 		// Tracking our iterations.
 		int count = 0;
-		// First random x, will be refined in the loop if necessary.
+
 		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;
 			}
+
+			// 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);
 				entangled[value_position].addToMe(constant);
 			}
 
+			// After this we form the register from the complex array but it will need to be normalised.
 			outState = new QubitRegister(entangled);
 			outState.normalise();
 
+			// 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.
 			inState = new QubitRegister(entangled);
 			inState.normalise();
 
-			// Making inverse discrete quantum fourier transform, same size as the register.
+			// Making inverse discrete quantum fourier transform gate, same size as the register.
 			Gate iqft = new InverseQFT(inState.getLength());
 
 			// This will hopefully transform the register into a particular value...
 			// ...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 choose another x / start again because the register collapsed into the "wrong" state.
+			// 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;
-				
+
 			// 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;
-			
+
 			// So we get it from this function.
 			int bestDenominator = findDenominator(c,q);
-			// If the denominator isn't even, it probably won't work. There are ways around this, but...
+			// 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);
 			System.out.println(gcd(n,a));
 			System.out.println(gcd(n,b));
 			done = true;
-			
 		}
 		if (fail)
 			System.out.println("Algorithm failed!");
 		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;