I'm trying to simplify the inner for loop of this implementation of the Mosca-Ekert semi-classical variant of Shor's algorithm. The inner for loop should have only linear length, but this implementation is exponential.
""" Cycle to create the Sequential QFT, measuring qubits and applying the right gates according to measurements """ for i in range(0, 2*n): """reset the top qubit to 0 if the previous measurement was 1""" circuit.x(up_reg).c_if(c_aux, 1) circuit.h(up_reg) cMULTmodN(circuit, up_reg, down_reg, aux, a**(2**(2*n-1-i)), N, n) """cycle through all possible values of the classical register and apply the corresponding conditional phase shift""" for j in range(0, 2**i): """the phase shift is applied if the value of the classical register matches j exactly""" circuit.u1(getAngle(j, i), up_reg).c_if(up_classic, j) circuit.h(up_reg) circuit.measure(up_reg, up_classic[i])
The obvious way of using
c_if(up_classic[j],j) doesn't work. I've tried using an if statement as in
for j in range(0, i): """the phase shift is applied if the value of the classical register matches j exactly""" if up_classic[j]: circuit.u1(getAngle(2**j,i), up_reg)
but test runs fail to find the correct factor for small semiprimes like 21 or 33.