How do I add 1+1 using a quantum computer?

Question

This can be seen as the software complement to How does a quantum computer do basic math at the hardware level?

The question was asked by a member of the audience at the 4th network of the Spanish Network on Quantum Information and Quantum Technologies. The context the person gave was: "I'm a materials scientist. You are introducing advanced sophisticated theoretical concepts, but I have trouble picturing the practical operation of a quantum computer for a simple task. If I was using diodes, transistors etc I could easily figure out myself the classical operations I need to run to add 1+1. How would you do that, in detail, on a quantum computer? ".

Answer 1

As per the linked question, the simplest solution is just to get the classical processor to perform such operations if possible. Of course, that may not be possible, so we want to create an adder.

There are two types of single bit adder - the half-adder and the full adder. The half-adder takes the inputs $A$ and $B$ and outputs the 'sum' (XOR operation) $S = A\oplus B$ and the 'carry' (AND operation) $C = A\cdot B$. A full adder also has the 'carry in' $C_{in}$ input and the 'carry out' output $C_{out}$, replacing $C$. This returns $S=A\oplus B\oplus C_{in}$ and $C_{out} = C_{in}\cdot\left(A+B\right) + A\cdot B$.

---

Quantum version of the half-adder

Looking at the CNOT gate on qubit register $A$ controlling register $B$: \begin{align*}\text{CNOT}_{A\rightarrow B}\left|0\right>_A\left|0\right>_B &= \left|0\right>_A\left|0\right>_B \\ \text{CNOT}_{A\rightarrow B}\left|0\right>_A\left|1\right>_B &= \left|0\right>_A\left|1\right>_B \\\text{CNOT}_{A\rightarrow B}\left|1\right>_A\left|0\right>_B &= \left|1\right>_A\left|1\right>_B \\\text{CNOT}_{A\rightarrow B}\left|1\right>_A\left|1\right>_B &= \left|1\right>_A\left|0\right>_B, \\ \end{align*} which immediately gives the output of the $B$ register as $A\oplus B = S$. However, we have yet to compute the carry and the state of the $B$ register has changed so we also need to perform the AND operation. This can be done using the 3-qubit Toffoli (controlled-CNOT/CCNOT) gate. This can be done using registers $A$ and $B$ as control registers and initialising the third register $\left(C\right)$ in state $\left|0\right>$, giving the output of the third register as $A\cdot B = C$. Implementing Toffoli on registers $A$ and $B$ controlling register $C$ followed by CNOT with $A$ controlling $B$ gives the output of register $B$ as the sum and the output of register $C$ as the carry. A quantum circuit diagram of the half-adder is shown in figure 1.

---

Figure 1: Circuit Diagram of a half-adder, consisting of Toffoli followed by CNOT. Input bits are $A$ and $B$, giving the sum $S$ with carry out $C$.

---

Quantum version of the full adder

Shown in figure 2, a simple way of doing this for single bits is by using $4$ qubit registers, here labelled $A$, $B$, $C_{in}$ and $1$, where $1$ starts in state $\left|0\right>$, so the initial state is $\left|A\right>\left|B\right>\left|C_{in}\right>\left|0\right>$:

1. Apply Toffoli using $A$ and $B$ to control $1$: $\left|A\right>\left|B\right>\left|C_{in}\right>\left|A\cdot B\right>$
2. CNOT with $A$ controlling $B$: $\left|A\right>\left|A\oplus B\right>\left|C_{in}\right>\left|A\cdot B\right>$
3. Toffoli with $B$ and $C_{in}$ controlling $1$: $\left|A\right>\left|A\oplus B\right>\left|C_{in}\right>\left|A\cdot B\oplus\left(A\oplus B\right)\cdot C_{in} = C_{out}\right>$
4. CNOT with $B$ controlling $C_{in}$: $\left|A\right>\left|A\oplus B\right>\left|A\oplus B\oplus C_{in} = S\right>\left|C_{out}\right>$

A final step to get back the inputs $A$ and $B$ is to apply a CNOT with register $A$ controlling register $B$, giving the final output state as $$\left|\psi_{out}\right> = \left|A\right>\left|B\right>\left|S\right>\left|C_{out}\right>$$

This gives the output of register $C_{in}$ as the sum and the output of register $2$ as carry out.

Figure 2: Circuit diagram of a full adder. Input bits are $A$ and $B$ along with a carry in $C_{in}$, giving the sum $S$ with carry out $C_{out}$.

---

Quantum version of the ripple carry adder

A simple extension of the full adder is a ripple carry adder, named as it 'ripples' the carry out to become the carry in of the next adder in a series of adders, allowing for arbitrarily-sized (if slow) sums. A quantum version of such an adder can be found e.g. here

---

Actual implementation of a half-adder

For many systems, implementing a Toffoli gate is far from as simple as implementing a single qubit (or even two qubit) gate. This answer gives a way of decomposing Toffoli into multiple smaller gates. However, in real systems, such as IBMQX, there can also be issues on which qubits can be used as targets. As such, a real life implementation on IBMQX2 looks like this:

Figure 3: Implementation of a half-adder on IBMQX2. In addition to decomposing the Toffoli gate into multiple smaller gates, additional gates are required as not all qubit registers can be used as targets. Registers q[0] and q[1] are added to get the sum in q[1] and the carry in q[2]. In this case, the result q[2]q[1] should be 10. Running this on the processor gave the correct result with a probability of 42.8% (although it was still the most likely outcome).

Answer 2

A new method for computing sums on a quantum computer is introduced. This technique uses the quantum Fourier transform and reduces the number of qubits necessary for addition by removing the need for temporary carry bits.

PDF link for 'addition on a quantum computer', written by Thomas G. Draper, written September 1, 1998, revised: June 15, 2000.

To summarize the above link, addition is performed according to the following circuit diagram (taken from page 6):

To quote the paper (again, page 6):

The quantum addition is performed using a sequence of conditional rotations which are mutually commutative. The structure is very similar to the quantum Fourier transform, but the rotations are conditioned on $n$ external bits.

Answer 3

``If I was using diodes, transistors etc I could easily figure out myself the classical operations I need to run to add 1+1. How would you do that, in detail, on a quantum computer?''

Impressive! I suspect that most people cannot easily figure out themselves how to combine diodes and transistors to implement a classical two-bit adde (though I do not doubt this material scientist can probably do it). ;)

Theoretically, the way you implement a classical adder is pretty similar in a classical and quantum computer: you can do that in both cases by implementing a Toffoli gate! (See @Mithrandir24601's answer.)

But the material scientist probably wants to understand how to implement such an gate (or an equivalence sequence of other quantum gates) on a physical device. There are probably an infinite ways to do that using different quantum technologies, but here are two direct realizations of this gate using trapped ions and superconducting qubits:

1. Realization of the Quantum Toffoli Gate with Trapped Ions, T. Monz, K. Kim, W. Hänsel, M. Riebe, A. S. Villar, P. Schindler, M. Chwalla, M. Hennrich, and R. Blatt, Phys. Rev. Lett. 102, 040501, arXiv:0804.0082.
2. Implementation of a Toffoli gate with superconducting circuits A. Fedorov, L. Steffen, M. Baur, M. P. da Silva & A. Wallraff Nature 481, 170–172, arXiv:1108.3966.

You can also decompose the Toffoli gate as a sequence of single-qubit and CNOT gates. https://media.nature.com/lw926/nature-assets/srep/2016/160802/srep30600/images/srep30600-f5.jpg You can read about how to implement these with photonics, cavity-QED and trapped ions in Nielsen and Chuang.

Answer 4

Parallel computation of the sum of two qubits

I wanted to experience parallel computation of the sum of two qubits, a superposition of 0 and "1 with phase -1" added to 1; and I was inspired by Mithrandir24601's answer. The results are below. I hope my answer is within the context of what was asked. It shows how 1 is added 1, and to 0, at the same time, but whilst both answers are calculated, we can read out the answer to only one of the calculations each time the computation is run. You can see that out of 1000 runs, 417 times we read out the answer "1" (1=0+1), and 380 times and we read out the answer "2" (2=1+1).

(34 times we got nought when the 1 bit was flipped to nought, 54 times we got 0=0+1, 29 times we got 1=1+1, 28 times we got 2=0+1, 42 times we got 3=0+1, and 16 times we got 3=1+1; each of these errors arising no doubt from bit flips, phase flips, or both).

I thought an initial $\pi$ phase (created in the 1st of 3 Hadamard gates) represented a negative digit, but it just represents a positive digit with a -1 phase factor.

A superposition of 0 and "1 with phase -1" in a one qubit register is added to 1 in a two-qubit register. With three qubits, the first two qubits left to right is the sum (or the 3rd and 4th of 5) and the right-most qubit shows whether the ground state (treated as 0) was added or the excited state (1 with an initial phase of -1) was added.

Answer 5

A quantum adder was "programmed" and compared with a transistor-based implementation in Feynman's 1985 "Quantum Mechanical Computers" - one of the earliest papers on quantum computing!

---

In that paper, Feynman initially reviews the classical implementation of a NOT gate and a NAND gate using resistor-transistor logic:

Feynman notes issues with heat dissipation with such circuits (this was a much bigger concern in the mid-80's than it is now).

So Feynman goes on to discuss a reversible circuit to implement a half- and full-adder:

(Note that he uses open bubbles $\circ$ rather than now-standard closed bubbles $\bullet$, and uses X's where most would use a circled-plus $\oplus$.)

Feynman builds a Hamiltonian using a "cursor" to control execution of his program with what we now call the circuit-to-Hamiltonian reduction, whereas now, we'd implement the gates with well-timed electromagnetic pulses (lasers or microwaves, for example).

But many of the ideas that are common and well-known in the field are already present and introduced in this (ancient) paper of Feynman.

Answer 6

This is a great question as it opens a wider discussion on how quantum computing can be used for research by non-quantum computing experts.

My personal belief is that quantum computers will be especially useful for material science and quantum chemistry, in ways we cannot fully grasp at the moment. In order to enable this, we need to allow lower barrier of entrance to quantum computing for domain specialists.

One way to lower this entrance barrier is to enable designing quantum algorithms using high-level functional design programs. Classiq with its built-in Qmod language enables doing exactly this (disclaimer - I'm a Classiq employee). For example, one way to code 1+1 into quantum computer with Classiq is:

qfunc main(output x: qnum, output y:qnum){
  prepare_int<1>(y);
  x=y+1;
}

Then, the Classiq synthesis engine (compiler) generates a concrete quantum circuit that implements this algorithm. The beauty is that most algorithms have several circuit-level implementations (sometime plenty of different implementations). Even for the regular adder (adding 1+1) there are several different implementations.

The concrete circuit implementation of the above code is:

And can be viewed interactively: