<p>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.</p>

<blockquote>
  <p>3n qubits are required to add two n bit numbers?</p>
</blockquote>

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

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

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

<p><strong>The paper's circuit</strong></p>

<p>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:</p>

<p><a href="https://i.sstatic.net/5ukBG.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5ukBG.png" alt="Fourier addition circuit"></a></p>

<p>You can toy with <a href="http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B1%2C1%2C1%2C1%2C%22QFT4%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C1%2C1%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C%22QFT%E2%80%A04%22%5D%5D%7D" rel="nofollow noreferrer">this circuit in Quirk</a>.</p>

<p>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.</p>

<p><strong>Other circuits</strong></p>

<p>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 <a href="http://ftp.qucis.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_UNCONVENTIONAL_COMPUTING/VOLUME_1_Issue_4/RENTERGEM.pdf" rel="nofollow noreferrer">this very succinct one by VanRentergem</a> that only uses one ancilla:</p>

<p><a href="https://i.sstatic.net/CfU9N.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CfU9N.jpg" alt="Adder circuit"></a></p>

CC BY-SA 3.0
2016-07-20T15:20:01.083Z
"Basically they take advantage of the fact that, after you've Fourier-transformed a value, incrementing corresponds to applying a phase gradient." what is a phase gradient ? closest I found is this paper which references them multiple times but does not explain their meaning http://topex.ucsd.edu/SAR/stacking/text.pdf
blue-sky
CC BY-SA 3.0
2016-07-20T15:27:44.913Z
@blue-sky It just that means that you apply a phase factor that depends on the binary number represented by some bits in a simple way. For example, the [Cooley-Tukey FFT algorithm has a loop that phases the values in an array by $\left(e^{\tau i /n}\right)^k$](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Pseudocode) where $k$ is the index of the value.
Craig Gidney
CC BY-SA 3.0
2016-07-20T14:53:02.907Z
2016-07-20T15:13:53.657Z
2016-07-20T15:13:53.657Z
Craig Gidney
<p>From reading <a href="https://arxiv.org/pdf/quant-ph/0008033v1.pdf" rel="nofollow">https://arxiv.org/pdf/quant-ph/0008033v1.pdf</a> 3n qubits are required to add two n bit numbers.</p>

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

<p>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 ? </p>

CC BY-SA 3.0
2016-07-21T04:05:03.920Z
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](https://books.google.ca/books?id=-s4DEy7o-a0C). 3. Your last question is really off-topic here, please also check out our [help/on-topic]. You might want to check out our sister site [cs.se] which has a broader scope.
Kaveh
<quantum-computing><quantum-information>
Addition on a quantum computer
blue-sky
# Addition on a quantum computer

(Asked by: username_0 on 2016-07-20)

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 ?

**Tags:** quantum-computing, quantum-information

> **Comments:**
> **username_1**: 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](https://books.google.ca/books?id=-s4DEy7o-a0C). 3. Your last question is really off-topic here, please also check out our [help/on-topic]. You might want to check out our sister site [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_2 on 2016-07-20. Score: 1 | Accepted 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:

[![Fourier addition circuit](https://i.sstatic.net/5ukBG.png)](https://i.sstatic.net/5ukBG.png)

You can toy with [this circuit in Quirk](http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B1%2C1%2C1%2C1%2C%22QFT4%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C1%2C1%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C%22QFT%E2%80%A04%22%5D%5D%7D).

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](http://ftp.qucis.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_UNCONVENTIONAL_COMPUTING/VOLUME_1_Issue_4/RENTERGEM.pdf) that only uses one ancilla:

[![Adder circuit](https://i.sstatic.net/CfU9N.jpg)](https://i.sstatic.net/CfU9N.jpg)

> **Comments:**
> **username_0**: "Basically they take advantage of the fact that, after you've Fourier-transformed a value, incrementing corresponds to applying a phase gradient." what is a phase gradient ? closest I found is this paper which references them multiple times but does not explain their meaning http://topex.ucsd.edu/SAR/stacking/text.pdf  
> **username_2**: @username_0 It just that means that you apply a phase factor that depends on the binary number represented by some bits in a simple way. For example, the [Cooley-Tukey FFT algorithm has a loop that phases the values in an array by $\left(e^{\tau i /n}\right)^k$](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Pseudocode) where $k$ is the index of the value.  

---

