8
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

figure from paper

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

multiplication

$\endgroup$

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.