1
$\begingroup$

How can a reversible multiplication quantum circuit be implemented? By "reversible" I mean one that performs a *= b on the inputs a and b of the multiplication. In this case, it is reversible because the inverse operation a /= b exists. I believe the multiplication requires some ancilla bits, but it needs to be able to be reset to |0> by uncomputation after multiplication.

My explanation may have been insufficient, so I will write it in more detail. The multiplier circuit I am trying to build is one that calculates the product for input registers a and b and sets it in register a. Namely,

$|a\rangle|b\rangle \rightarrow |a\times b\rangle |b\rangle$

The necessary ancilla bits must be able to be set back to $|0\rangle$ by uncomputation.

$|a\rangle|b\rangle|00\dots0\rangle_a \rightarrow |a\times b\rangle |b\rangle|00\dots0\rangle_a$

Thank you in advance for your comments and advice.

Improve this question
$\endgroup$
2
  • $\begingroup$ This may not be the full state-of-the-art, but if you look at the relevant parts of Appendix A and Appendix B of this paper arxiv.org/abs/1805.12445 you will have an explanation of a nice reversible implementation of multiplication on a quantum computer. $\endgroup$
    – sheesymcdeezy
    Jun 1, 2022 at 9:32
  • 1
    $\begingroup$ Thanks for the reference! If I understand correctly, the implementation described in that paper requires a separate register to output the product. The circuit I want to know is a *= b i.e. the product of a * b is set to a (my explanation was lacking, sorry). Is this possible? $\endgroup$
    – yasuhito
    Jun 1, 2022 at 23:33

1 Answer 1

Reset to default
1
$\begingroup$

Generally, any classical computation can be turned into a reversible computation using enough ancilla bits. This is also true for the quantum case.

Specifically, the $AND$ gate can be built using the $CCNOT$ (Toffoli) gate. Adding the $NOT$ gate, which is already reversible, and we have a (classical) universal set of gates using $NAND$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you! I added a description to my question, and I can't come up with a good digital circuit for a case like $|a\rangle|b\rangle \rightarrow |a\times b\rangle|b\rangle$ where the product is output to the input register. $\endgroup$
    – yasuhito
    Jun 3, 2022 at 4:39

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.