Constructing a circuit which performs the transformation $|x,y\rangle \to |x, x + y \bmod 4\rangle$

Question

When faced with exercises like these, I find it hard to know how to construct the circuits due to the amount of input one needs to account for. I have seen the solution provided here however, I don't think I would have been able to solve this exercise my self.

Does anyone have any tips on a systematic way to construct a circuit like this? I start out with a circuit which solves one specific input (for example for $x = |00\rangle, y = |01\rangle$), but after this I get stuck. I appreciate any help!

Answer 1

Here are some strategies.

1. Start from a classical circuit, and do a naive transformation into a quantum circuit (e.g. AND gate becomes Toffoli onto a clean ancilla). Find ways to uncompute intermediate values and other garbage. Then optimize optimize optimize until it's compact. It helps to know a lot of trivial circuit identities when optimizing.

2. Decompose into simpler problems. For example, separate the two-bit addition into two controlled increments then figure out how to do a controlled increment.

3. Get inspiration from algebraic boolean expressions for the output values. For example, if you are incrementing a register $x_0, x_1, x_2, ..., x_k$ then qubit $i$ transitions from $x_i$ to $x_i \oplus \prod_{j<i} x_j$ and this form suggests a simple circuit that you can create.

4. Brute force one output bit at a time. This only works for smaller circuits. Figure out every situation where each bit should be ON, and for each of those cases output a multi-controlled NOT targeting a clean ancilla to represent the output. Then do the same strategy in reverse to uncompute the input. Then optimize optimize optimize.

5. Diagonalize the problem. Is there a simple unitary $U$ that maps your problem's eigenstates to the computational basis states? Apply it, then phase the appropriate states using many-controlled Z rotations, then un-apply $U$. In the case of addition, the operation that does this is the QFT and you won't even need the Z rotations to be controlled.

6. Find a loop invariant that breaks the problem into constant-sized pieces. In the case of adders, the invariant is packaged up into the carry bit that propagates through ripple-carry adders. Can you find an equivalent of a carry bit for your problem?

7. Pay attention to data dependencies. Start by getting the value of qubits with no dependents correct. Then remove those qubits from the dependency graph and iterate. Two-bit addition has a very simple dependency graph, and so this approach works well on it. If the dependency graph has cycles, the problem will be much harder.

8. Apply generic problem solving (i.e. read How to Solve It). For example, get a foothold by dropping constraints. What if you were allowed to get the phases wrong, or to create junk? What if you only have to get some of the qubits correct, and are allowed to trash the others? What if you had more workspace? What if one of the input qubits was promised to be in the 0 state? The 1 state? The + state? What if you only had to do 1 bit addition, or 1-bit-register-into-2-bit-register addition?

Answer 2

For simplicity let's assume $x, y \in \mathbb{N}$, since worrying about two's complement representation for negative numbers is just annoying.

First, this function must be reversible. That means $y$ is restricted to the range $0 \dots 3$, since $(x + 0) \bmod 4 = (x + 4) \bmod 4$, so if we allow $y$ values outside of $0 \dots 3$ we cannot reverse the function (uniquely identify $y$ given the values of $x$ and $(x + y) \bmod 4$). This means the $y$ input can be at most two qbits in size.

We then consider that $(x + y) \bmod 4 = (x \bmod 4) + (y \bmod 4)$. This means that we only have to care about the two least-significant qbits of $x$ when calculating $(x + y) \bmod 4$. Thus, given $n$ input qbits for $x$ and $2$ input qbits for $y$, our circuit will only "touch" the two least-significant qbits of $x$ (probably as input to a CNOT) and leave the other $n-2$ qbits of $x$ alone.

For simplicity, let's build our circuit assuming $n = 2$. We can of course construct our circuit by just calculating the desired action on all $2^4$ possible input values then writing a matrix corresponding to that, but that's boring. Let's simplify it even more; let $x = |ab\rangle$ and $y = |cd\rangle$ where $a,b,c,d \in \{0, 1\}$; $c$ and $d$ are also our output qbits. We have the following observations:

• When $b = d = 1$, we want to flip $c$ (since addition of $b$ and $d$ overflows). This is clearly the action of a Toffoli gate.
• When $b = 1$, we want to flip $d$. For this we use a CNOT.
• When $a = 1$, we want to flip $c$. For this we again use a CNOT.

This means for $n=2$, our circuit is as follows:

For higher values of $n$, we just ignore the $n-2$ most-significant qbits.

In general, problems like these are just that: problems. They require some amount of mathematical trickiness, reasoning, and breaking down the problem to work through. Hopefully when reading the above you can see how each step followed from the last until we can use our intuition to solve the problem. For quantum computing problems specifically, they'll become easier as you learn the valid "moves" you can make around the problem space.

Answer 3

@ahelwer has provided a smart construction, and I will provide a more brute-force method as a complementary for beginners like me. It actually starts out by listing all the possible 16 moves. Let x,y=0,1,2,3, then all the possible moves are

$ x=0, \quad y=(0123)\rightarrow(0123) \\ x=1, \quad y=(0123)\rightarrow(1230) \\ x=2, \quad y=(0123)\rightarrow(2301) \\ x=3, \quad y=(0123)\rightarrow(3012) $

where by arrow we mean $y$ is treated as an output. So if we denote $|xy\rangle\equiv|x\rangle|y\rangle=|ab\rangle\ |cd\rangle$, for $a,b=0,1$, we have

$ |00cd\rangle \rightarrow |00cd\rangle $

and $ |0100\rangle \rightarrow |0101\rangle \\ |0101\rangle \rightarrow |0110\rangle \\ |0110\rangle \rightarrow |0111\rangle \\ |0111\rangle \rightarrow |0100\rangle $

and $ |1000\rangle \rightarrow |1010\rangle \\ |1001\rangle \rightarrow |1011\rangle \\ |1010\rangle \rightarrow |1000\rangle \\ |1011\rangle \rightarrow |1001\rangle $

and $ |1100\rangle \rightarrow |1111\rangle \\ |1101\rangle \rightarrow |1100\rangle \\ |1110\rangle \rightarrow |1101\rangle \\ |1111\rangle \rightarrow |1110\rangle $

which are exactly the rules @ahelwer described. This is not surprised from the perspective of addition of binary numbers. In terms of matrices, the above actions read

$ I_4, \begin{bmatrix} & I_3 \\ 1 \end{bmatrix}, \begin{bmatrix} & I_2 \\ I_2 \end{bmatrix}, \begin{bmatrix} & 1\\ I_3 \end{bmatrix} $

respectively for the above four sectors. Since the matrices acting on different sectors (the big $16\times16$ matrix is block-diagonal), we can construct them separately. In particular, we notice for the $|01\rangle$ sector,

$ \begin{bmatrix} & I_3 \\ 1 \end{bmatrix}=\begin{bmatrix} I_2 & \\ & X \end{bmatrix} \begin{bmatrix} 1 & \\ & X\\ & & 1 \end{bmatrix} \begin{bmatrix} X & \\ & I_2 \end{bmatrix} $

which is CNOT conditioned by the first qubit being zero, followed by SWAP, and followed by CNOT. Similarly for the $|11\rangle$ space, which is just the hermitian conjugate. For $|10\rangle$, it is

$ \begin{bmatrix} & I_2 \\ I_2 \end{bmatrix} = X\otimes I_2 $

Thus the complete circuit is attached below. As we explained above, since the three units (boxed by dashed lines) acting on different subspace, they commute and we can move them in different orders.