Commits

committed 98ea026

• Participants
• Parent commits ab7b7f3

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`

File Shor.java

` 		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;`