6
$\begingroup$

There is an excellent answer to How do I add 1+1 using a quantum computer? that shows constructions of the half and full adders. In the answer, there is a source for the QRCA. I have also looked at this presentation.

I am still left with these questions:

  1. What does a truth table for a QRCA look like?

  2. What would a unitary matrix for a QRCA be?

  3. What would a circuit diagram for a QRCA look like? (There is an example of a 6-bit circuit in the arXiv paper)

$\endgroup$
4
  • $\begingroup$ You acknowledge that there's a quantum circuit diagram for a particular size in the paper you're citing. What more are you after regarding quantum circuits? $\endgroup$
    – DaftWullie
    Jun 14, 2018 at 18:33
  • $\begingroup$ Here's the abstract: link.springer.com/chapter/10.1007/978-3-540-85194-3_19 $\endgroup$ Jun 14, 2018 at 18:34
  • $\begingroup$ also, the first two lines of figure 5 effectively define the truth table, from which you can directly derive the unitary matrix. $\endgroup$
    – DaftWullie
    Jun 14, 2018 at 18:36
  • $\begingroup$ Again, apologies. I do not actually know how to derive the matrix from the table (or how to dervive a truth table for a quantum gate). Nor am I able to create circuits (the 6-bit circuit is more complex than a 2 or 3 bit circuit). Obviously very new to logic cicuits & quantum computing! $\endgroup$
    – user820789
    Jun 14, 2018 at 18:52

1 Answer 1

6
$\begingroup$

What does a truth table for a QRCA look like?

You don't want to know. It will be a gigantic complicated table that provides no insight whatsoever. At the very least you need to use boolean algebra instead of a table, but even that will be cumbersome and will require many intermediate values that ultimately are just a less-visual way of describing an addition circuit.

If it helps, here is the set of equations for a simpler operation, an increment operation. The equations define how each output bit can be computed from the input bits:

$o_0 = i_0 \oplus 1$

$o_1 = i_1 \oplus i_0$

$o_2 = i_2 \oplus (i_0 \land i_1)$

$\vdots$

$o_n = i_n \oplus {\Large{\land}}_{k=0}^{n-1} i_k$

What would a unitary matrix for a QRCA be?

It's a permutation matrix.

As a starting point, here is the permutation matrix corresponding to a 2-bit increment:

$$\text{Inc}_2 = \begin{bmatrix} &&&1\\ 1&&&\\ &1&&\\ &&1&\\ \end{bmatrix}$$

and a 3-bit increment:

$$\text{Inc}_3 = \begin{bmatrix} &&&&&&&1\\ 1&&&&&&&\\ &1&&&&&&\\ &&1&&&&&\\ &&&1&&&&\\ &&&&1&&&\\ &&&&&1&&\\ &&&&&&1&\\ \end{bmatrix}$$

I suspect you see the pattern. Just start with an identity matrix and shift it down by 1 (with the bottom row wrapping around to the top). To add 2, instead of adding 1 (i.e. incrementing) you would just shift down by 2 instead of by 1.

In an addition circuit, the amount of shifting depends on the other input. So you end up with a series of sub-matrices with increasingly-shifted diagonals:

$$\text{Add}_2 = \begin{bmatrix} \begin{bmatrix} 1&&&\\ &1&&\\ &&1&\\ &&&1\\ \end{bmatrix} \\& \begin{bmatrix} &&&1\\ 1&&&\\ &1&&\\ &&1&\\ \end{bmatrix} \\&& \begin{bmatrix} &&1&\\ &&&1\\ 1&&&\\ &1&&\\ \end{bmatrix} \\&&& \begin{bmatrix} &1&&\\ &&1&\\ &&&1\\ 1&&&\\ \end{bmatrix} \end{bmatrix}$$

What would a circuit diagram for a QRCA look like?

There are many possible constructions. Here is one that works entirely inline:

addition circuit

You can play with this construction in Quirk.

$\endgroup$
0

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.