How to prevent future loops using a control qubit?

Question

I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|y\rangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?

Answer 1

You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.

In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:

for index, qubit in enumerate(input1):
  if qubit:
    output += input2 << index