5
$\begingroup$

I am trying to understand the toffoli operation for the quantum adder below: (especially for the second toffoli gate) but I am stuck in understanding the calculation to get the correct outputs.

enter image description here

The carry bits and sum bits are defined as of below: enter image description here

enter image description here

For the 2nd Toffoli gate, I cant seem to understand how to get a2⊕c2. I calculated their inputs up till the 2nd toffoli gate to be:

Input:
$b_1 \oplus a_1$,
$a_1 \oplus c_1$,
$a_1 \oplus a_2$

By definition of the toffoli gate, my outputs should be:
$b_1 \oplus a_1$,
$a_1 \oplus c_1$,
$(a_2 \oplus a_1) \oplus [(b_1 \oplus a_1)(a_1 \oplus c_1)]$

But after expanding the result and summarizing it: $$(a_2 \oplus a_1) \oplus [(b_1 \oplus a_1)(a_1 \oplus c_1)] = (a_2 \oplus a_1) \oplus (b_1a_1 \oplus b_1c_1 \oplus a_1a_1 \oplus a_1c_1)$$

i cant seem to equate it to $(a_2 \oplus c_2)$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You were on the right track and almost got it!

First we use the definition of the carry bits that you have given to define:

$c_2 = a_1b_1 \oplus b_1c_1 \oplus a_1c_1$

Now we can actually continue from where you left off! Imma take your last step as the LHS of the equation and continue from there:

$$\begin{align*} (a_2 \oplus a_1) \oplus (b_1a_1 \oplus b_1c_1 \oplus a_1a_1 \oplus a_1c_1) &= a_2 \oplus a_1 \oplus a_1a_1 \oplus \underbrace{(b_1a_1 \oplus b_1c_1 \oplus a_1c_1)}_{c_2} \\ & = a_2 \oplus c_2 \oplus (a_1 \oplus a_1a_1) \end{align*}$$ where throughout I have freely changed the order of the terms thanks to the commutative property that $x \oplus y = y \oplus x$. So now we almost have what we want, but we have this extra pesky $(a_1 \oplus a_1a_1)$ term. However we notice that if $a_1 = 0$, that term becomes zero in a fairly straightforward way. But also if $a_1 = 1$ then we see that $a_1a_1 = 1$ and therefore $a_1 \oplus a_1a_1 = 0$. And since $a_1$ can only equal either $0$ or $1$, we have shown that $(a_1 \oplus a_1a_1)$ is always $0$. So coming back to our equation we have

$$\begin{align*} (a_2 \oplus a_1) \oplus (b_1a_1 \oplus b_1c_1 \oplus a_1a_1 \oplus a_1c_1) & = a_2 \oplus c_2 \oplus \underbrace{(a_1 \oplus a_1a_1)}_{0} \\ &= a_2 \oplus c_2 \end{align*}$$

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Oh my... i have spend days trying to figure out because i wasn't very clear about properties of qubits using ⊕. Do you have any recommendation on where to read up on more properties regarding tensor products and ⊕ <- I think this doesnt refer to our classical direct sum. $\endgroup$
    – Michael Hung
    Mar 30, 2021 at 11:09
  • $\begingroup$ $\oplus$ and $\otimes$ operators are not specific to quantum and you can think of their properties exactly the same way that you use them classically :) this is because you aren't acting on the qubits when you use those operators but on the basis states E.g. if $|\psi\rangle = a|0\rangle + b|1\rangle$ and $x$ denotes a classical bit of 1 or 0, it doesn't make sense to perform an operation that does $|\psi\rangle|x\rangle \rightarrow |\psi \oplus x \rangle|x\rangle$ but it can make sense to do $|\psi\rangle|x\rangle \rightarrow a|0 \oplus x \rangle|x\rangle + b|1 \oplus x \rangle|x\rangle$ $\endgroup$
    – sheesymcdeezy
    Mar 30, 2021 at 11:26
  • $\begingroup$ @MichaelHung A useful insight is to realize that because the circuit is reversible and only has classical operations, you don't need to worry at all about the fact that it's quantum in order to make it correct. Also, (ab + bc + ca) mod 2 = majority_vote(a, b, c). Although, looking at your circuit, it's not reversible because it leaves the bottom bit uncleared. $\endgroup$
    – Craig Gidney
    Mar 30, 2021 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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