# Addition on a quantum computer

From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers.

For a simple arithmetic operation such as a+b+c+d where a,b,c,d are each 10 bits and assuming the result of the operation does not exceed 10 bits then 3*10*3=90 qubits are required for this operation?

With 90 qubits then 2^90 simultaneous operations are possible ?, yet for integer addition it means can just add 4 ints where each int and its result does not exceed 10 bits ?

• 1. I don't see anywhere in the paper a claim that 3n bits are required for addition. It just states that the particular method mentioned requires 3n bits. 2. You seem to have basic misunderstanding about quantum computation. If you have not read a textbook on the topic you should start there, e.g. Quantum Computation and Quantum Information. 3. Your last question is really off-topic here, please also check out our help center. You might want to check out our sister site Computer Science which has a broader scope. – Kaveh Jul 21 '16 at 4:05

## 1 Answer

The algorithm from that paper runs inline with no extra ancilla bits. If the input number and the affected number use up $t$ bits altogether, then it runs in $t$ bits.

3n qubits are required to add two n bit numbers?

If each number is $n$ bits large, and you want a separate output then there are $3n$ bits involved. $n$ for the first input, $n$ for the second input, and $n$ for the output. Obviously.

For a simple arithmetic operation such as a+b+c+d where a,b,c,d are each 10 bits and assuming the result of the operation does not exceed 10 bits then 3*10*3=90 qubits are required for this operation?

No, you only need 50 bits. 10 for a, 10 for b, 10 for c, 10 for d, and 10 for the output. If you're willing to overwrite one of the inputs with the output then you can do it with 40 bits.

With 90 qubits then 2^90 simultaneous operations are possible? Yet for integer addition it means can just add 4 ints where each int and its result does not exceed 10 bits?

Nothing is stopping you from applying the addition circuit to inputs that are in superposition (I assume that's what you mean by "simultaneous").

The paper's circuit

Basically they take advantage of the fact that, after you've Fourier-transformed a value, incrementing corresponds to applying a phase gradient. So for each input bit that's on they apply a corresponding phase gradient. It's quite compact:

You can toy with this circuit in Quirk.

Overall the circuit has $O(n)$ depth, but $O(n^2)$ gates. There are also inline addition circuits that use only $O(n)$ gates, but they have worse constant factors on the depth and aren't quite as nice.

Other circuits

If you're willing to allow ancilla bits, then there are much more compact constructions that work both classically and quantumly. There's ones with $O(\log n)$ depth, or this very succinct one by VanRentergem that only uses one ancilla: