4

I'm reading the paper Quantum Networks for Elementary Arithmetic Operations (arXiv) by Vedral, Barenco, and Ekert. In section IIIA, they define a quantum adder circuit that sends $$ |a,b\rangle\rightarrow |a,a+b\rangle $$ where $a$, $b$ are $n$-bit binary integers, and the $b$ register has an extra qubit initialized to $|0\rangle$ to receive possible carries.

At the end of that section, they write:

If we reverse the action of the above network (i.e. if we apply each gate of the network in the reversed order) with the input $(a, b)$, the output will produce $(a, a − b)$ when $a ≥ b$. When $a < b$, the output is $(a, 2^{n+1} − (b − a))$, where $n + 1$ is the size of the second register.

Question: Is there an easy way to show this is true?

My interpretation of this section is that if $U$ is the unitary defined by the quantum circuit which sends $U|a,b\rangle=|a,a+b\rangle$, then the reversed action of the network gives $U^\dagger$ (since the network is made entirely out of Hermitian gates $CX$ and $CCX$). Then the reverse network acting on $|a,b\rangle$ with $a<b$ should give $$ U^\dagger|a,b\rangle = U^\dagger U|a,b-a\rangle = |a,b-a\rangle $$ which is not what they claim. So another way to phrase my question: Where is the above reasoning going wrong?

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
Jahan Claes
  • 1,092
  • 6
  • 13

1 Answers1

3

The paper's statement has it essentially backwards, the output will be $(a, b - a)$ when $a \leq b$ and will be $(a, 2^{n + 1} - (a - b))$ if $a > b$. The reasoning for $a < b$ in the question is correct and also works for the $a = b$ case since $b - a$ remains non-negative.

For completeness of the other case, the reasoning for $a > b$ leading to that result is that applying the non-reversed circuit $U$ on an input that already has the extra $b$ carry qubit initialized to $|1\rangle$ (as all $2^{n + 1} - (a - b)$ will since $a - b$ cannot exceed $2^n$) results in the addition excluding the carry going through normally but the extra |$1\rangle$ becoming a $|0\rangle$ rather than vice-versa (for in the implementation in Figure 2 the change to the carry is done by CCXs and has no outside effect). $2^{n + 1} - (a - b) + a$ ostensibly results in $2^{n + 1} + b$ but the implementation with the carry causes $2^n$ to be subtracted twice in that case (since rather than adding the carry value of $2^n$ it was subtracted, so it is subtracted for both having not been added and having been subtracted) so it results in $|a, b\rangle$ and thus $U|a, b\rangle = U^{\dagger}U|a, 2^{n + 1} - (a - b)\rangle = |a, 2^{n + 1} - (a - b)\rangle$ under the assumption that $a - b$ is positive.

Joseph Geipel
  • 1,241
  • 1
  • 6
  • 6