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

$\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$ Commented 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
    Commented Jun 1, 2022 at 23:33

3 Answers 3

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

$\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
    Commented Jun 3, 2022 at 4:39
2
$\begingroup$

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

Quantum-quantum multiplier

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

Quantum-quantum in-place multiplier

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. enter image description here

$\endgroup$
0
$\begingroup$

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)
    def __iadd__(self, other):
        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")
$\endgroup$

Your Answer

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

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