# Is it possible to implement an in-place multiplication quantum circuit?

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$$

• 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. Commented Jun 1, 2022 at 9:32
• 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? Commented Jun 1, 2022 at 23:33

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$$.

• 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. Commented Jun 3, 2022 at 4:39

I have modified a quantum-quantum multiplication operator to do what you're looking for.

for i in range(length(\phi_1)):
output_subregister = \phi_{12}[i:i+length(\phi_1)+1]
if \phi_1[i] == 1:
output_subregister += \phi2


We can start from this quantum-quantum multiplier, which pseudocode is given above. Adding $$\phi_2$$ to a subset of qubits in $$\phi_{12}$$ like such, will successively add $$2^{i-1}\phi_2$$ to the register $$\phi_{12}$$, controlled by the $$i^{th}$$ qubit in register $$\phi_1$$. For those unfamiliar, this is because the product $$\phi_1 \phi_2$$ can be decomposed into the sum $$\phi_2(2^0\phi_{11} + 2^1\phi_{12} + ... 2^{n-1}\phi_{1n}$$), where $$\phi_{1i} \in \{0,1\}$$ is the state of the $$i^{th}$$ qubit in $$\phi_1$$. This produces the state $$|a,b,0\rangle \rightarrow |a,b,ab\rangle$$.

Example implementations of the addition operation are described in these two papers: https://arxiv.org/pdf/quant-ph/0008033 or https://arxiv.org/pdf/quant-ph/9511018. Note the +1 qubit in the output_subregister - that is to account for the fact that an addition of two $$n$$-bit numbers might potentially produce a $$(n+1)$$-bit result.

To uncompute the control qubit $$\phi_{1i}$$ at the $$i^{th}$$ step of the iteration, we can utilize two observations:

1. At the start of the iteration step (before adding $$\phi_2$$), output_subregister will always store a value less than $$\phi_2$$. This can be verified by noticing that the current cumulative sum in the entire $$\phi_{12}$$ register will be $$\phi_2(2^0 + 2^1 + ... 2^{i-1})$$. The value in the subregister will be a right bit-shift of this value by $$i$$ bits, which will be $$\leq\phi_2(2^{-i} + 2^{-i+1} + ... 2^{-1})$$.
2. When subtracting a $$b$$ from $$a$$ using an inversion of either of the two examples of the quantum adders described above (using negative angles in https://arxiv.org/pdf/quant-ph/0008033, reversing the order of all gates in https://arxiv.org/pdf/quant-ph/9511018), an underflow will occur when $$b>a$$. This is indicated by the most significant $$(n+1)$$ qubit in the output register being in the $$|1\rangle$$ state.

Considering these two, we can subtract $$\phi_2$$ from the subregister of $$\phi_{12}$$ to "test" whether the control qubit $$\phi_{1i}$$ was in the $$|1\rangle$$ state. If $$\phi_{1i}$$ was in the $$|1\rangle$$ state, $$\phi_2$$ would have been previously added to the output subregister, and subtracting $$\phi_2$$ at this step would leave the value positive. Whereas if $$\phi_{1i}$$ was in the $$|0\rangle$$ state, subtracting $$\phi_2$$ would cause an underflow and result in the most significant $$(n+1)$$ qubit in the result subregister to be $$|1\rangle$$. We can use this qubit to control a CNOT applied on the control qubit, to set it to $$|0\rangle$$ if it was previously $$|1\rangle$$. This effectively erases the value stored in $$\phi_1$$ as we proceed along in calculating the product $$\phi_1 \phi_2$$. This produces the state $$|a,b,0\rangle \rightarrow |0,b,ab\rangle$$. We can very well swap the first and third register to get the state you want.

for i in range(length(\phi_1)):
output_subregister = \phi_{12}[i:i+length(\phi_1)+1]
if \phi_1[i] == 1:
output_subregister += \phi2
output_subregister -= \phi2
if output_subregister[-1] == 0:  #indicates an underflow from the previous subtraction
#Occurs only if \phi2 was added, which means \phi_1[i] == 1
\phi_1[i] = NOT \phi_1[i]
output_subregister += \phi2


We can trace the states throughout one step of the iteration and verify it is indeed what we want for both possible values of the control qubit in superposition.

I don't know how to do it without ancillary registers, but here's a version with two extra registers. It uses one extra register to temporarily compute the multiplicative inverse, and the other to do the let c = a*b then del a = c*inv(b) then move c to a out-of-place-to-inplace dance.

def do_inplace_multiply(dst: quint, factor: quint) -> None:
n = len(dst)
assert factor[0]  # must be odd

# let tmp = dst*factor
tmp = quint(0, len=n)
for k in range(n):
if dst[k]:
tmp += factor << k

# let inv_factor = pow(factor, -1, 2**n)
inv_factor = quint(1, len=n)
for k in range(n):
if inv_factor[k]:
inv_factor -= (factor >> 1) << (k + 1)

# swap tmp, dst
tmp ^= dst
dst ^= tmp
tmp ^= dst

# del tmp = inv_factor*dst
for k in range(n):
if dst[k]:
tmp -= inv_factor << k
assert int(tmp) == 0
del tmp

# del inv_factor = pow(factor, -1, 2**n)
for k in range(n)[::-1]:
if inv_factor[k]:
inv_factor += (factor >> 1) << (k + 1)
assert int(inv_factor) == 1
del inv_factor


This is the "quint" class, which is really just storing it classically for testing purposes:

class quint:
"""A mutable fixed-width integer with some reversible operations."""
def __init__(self, v: int, len: int):
self.v = v
self.n = len
def __int__(self):
return int(self.v)
self.v += int(other)
self.v &= (1 << self.n) - 1
return self
def __ixor__(self, other):
self.v ^= int(other)
self.v &= (1 << self.n) - 1
return self
def __isub__(self, other):
self.v -= int(other)
self.v &= (1 << self.n) - 1
return self
def __getitem__(self, item: int) -> bool:
if isinstance(item, int):
return bool((self.v >> item) & 1)
raise NotImplementedError(f'{item=}')
def __lshift__(self, other: int) -> int:
return self.v << other
def __rshift__(self, other: int) -> int:
return self.v >> other
def __len__(self) -> int:
return self.n


Testing it:

n = 10
for a in range(30):
for b in range(1, 20, 2):
dst = quint(a, len=n)
factor = quint(b, len=n)
do_inplace_multiply(dst, factor)
assert int(factor) == b
assert int(dst) == a * b % 2**n
print("PASS")