1
$\begingroup$

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.

From https://github.com/ttlion/ShorAlgQiskit/blob/master/Shor_Sequential_QFT.py

    """ 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[0], 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[0]).c_if(up_classic, j)
        circuit.h(up_reg)
        circuit.measure(up_reg[0], 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[0])

but test runs fail to find the correct factor for small semiprimes like 21 or 33.

$\endgroup$
1
$\begingroup$

The conditional c_if on Qiskit checks a condition on a classical register, not a classical bit. Therefore, up_classic[j] is not valid.

Doing the if at construction time (like on your second case) makes no sense, since up_classic[j] is unknown at that time. Notice that, in the original code, up_classic is set at the end of the loop, with circuit.measure(up_reg[0], up_classic[i]).

| improve this answer | |
$\endgroup$
  • $\begingroup$ The classical register should be initialized to 0s. The first outer for loop should never have a phase shift. Does the conditional need to be done at run time? And, if so, does one need multiple up_classic registers? $\endgroup$ – botsina Nov 22 at 8:26
  • $\begingroup$ Sorry, the full problem is a bit over my head. If you want a conditional on a single bit, then you need to have them in different classical registers (see github.com/Qiskit/qiskit-terra/issues/1160 for further discussion) $\endgroup$ – luciano Nov 22 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.