<p>Here is a 2018 paper that uses phase gradient states and adders to optimize the T-count of the approximate QFT: <a href="https://arxiv.org/abs/1803.04933" rel="nofollow noreferrer">"Approximate Quantum Fourier Transform with O(nlog(n)) T gates" by Nam et al.</a></p>

<p><em>(The careful reader may notice that the question precedes the paper by two years! That's because the question actually led to the paper, though indirectly. I mentioned the phase gradient operation as an application of efficient adders in <a href="https://quantum-journal.org/papers/q-2018-06-18-74/" rel="nofollow noreferrer">this paper</a>, Nam et al saw that, independently realized it would useful for the approximate QFT, and here we are full circle. Oh, and of course Kitaev scooped everyone by over ten years. He mentions the adding-into-phase-gradient technique in a <a href="https://rads.stackoverflow.com/amzn/click/0821832298" rel="nofollow noreferrer">textbook from 2002</a> [page 133].)</em></p>

CC BY-SA 4.0
2018-07-06T05:54:03.243Z
2018-07-09T01:25:47.197Z
2018-07-09T01:25:47.197Z
Craig Gidney
<p>I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers on this general idea (or improvements thereof).</p>

<p>I don't even know the technical name for this technique, so even that information would be useful.</p>

<hr>

<p>An example QFT circuit showing the phasing-by-subtraction that I'm talking about (<a href="http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%5D%2C%5B%22Counting6%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22rev2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C%22sub3%22%5D%2C%5B1%2C1%2C1%2C1%2C%22H%22%2C1%2C%22rev2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22rev2%22%2C1%2C%22rev3%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22sub5%22%5D%2C%5B1%2C1%2C1%2C%22H%22%2C%22rev2%22%2C1%2C%22rev3%22%5D%2C%5B1%2C1%2C1%2C%22rev3%22%2C1%2C1%2C%22rev4%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C%22sub7%22%5D%2C%5B1%2C1%2C%22H%22%2C%22rev3%22%2C1%2C1%2C%22rev4%22%5D%2C%5B1%2C1%2C%22rev4%22%2C1%2C1%2C1%2C%22rev5%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22sub9%22%5D%2C%5B1%2C%22H%22%2C%22rev4%22%2C1%2C1%2C1%2C%22rev5%22%5D%2C%5B1%2C%22rev5%22%2C1%2C1%2C1%2C1%2C%22rev6%22%5D%2C%5B%22%E2%80%A2%22%2C%22sub11%22%5D%2C%5B%22H%22%2C%22rev5%22%2C1%2C1%2C1%2C1%2C%22rev6%22%5D%2C%5B%22rev6%22%5D%2C%5B%22Amps6%22%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%5D%7D" rel="nofollow noreferrer">and the equivalent circuit in Quirk, where numbers have opposite endian-ness so lots of reversing is required</a>):</p>

<p><a href="https://i.sstatic.net/Tv9rv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Tv9rv.png" alt="QFT from gradient kickback"></a></p>

<p>Note that the above isn't quite as optimized as what I have in mind. In particular, when you break the subtractions down into H/CX/T gates you find that they start by undoing work the last subtraction ended with. This lets you save half of the T gates.</p>

CC BY-SA 3.0
2016-08-16T01:57:43.750Z
What are the controlled a / b-=a gates?  Haven't seen that notation before.
Ross Duncan
CC BY-SA 3.0
2016-08-16T02:31:21.060Z
It means treat the 'a' qubits as a little-endian number, and subtract them into the 'b' qubits (also little-endian).
Craig Gidney
CC BY-SA 3.0
2016-08-17T11:59:12.793Z
Thanks!  Sorry I don't have anything useful to contribute to the question!
Ross Duncan
<quantum-computing>
Papers on using resource states to implement QFT efficiently
Craig Gidney
# Papers on using resource states to implement QFT efficiently

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

I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers on this general idea (or improvements thereof).

I don't even know the technical name for this technique, so even that information would be useful.

---

An example QFT circuit showing the phasing-by-subtraction that I'm talking about ([and the equivalent circuit in Quirk, where numbers have opposite endian-ness so lots of reversing is required](http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%5D%2C%5B%22Counting6%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22rev2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C%22sub3%22%5D%2C%5B1%2C1%2C1%2C1%2C%22H%22%2C1%2C%22rev2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22rev2%22%2C1%2C%22rev3%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22sub5%22%5D%2C%5B1%2C1%2C1%2C%22H%22%2C%22rev2%22%2C1%2C%22rev3%22%5D%2C%5B1%2C1%2C1%2C%22rev3%22%2C1%2C1%2C%22rev4%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C%22sub7%22%5D%2C%5B1%2C1%2C%22H%22%2C%22rev3%22%2C1%2C1%2C%22rev4%22%5D%2C%5B1%2C1%2C%22rev4%22%2C1%2C1%2C1%2C%22rev5%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22sub9%22%5D%2C%5B1%2C%22H%22%2C%22rev4%22%2C1%2C1%2C1%2C%22rev5%22%5D%2C%5B1%2C%22rev5%22%2C1%2C1%2C1%2C1%2C%22rev6%22%5D%2C%5B%22%E2%80%A2%22%2C%22sub11%22%5D%2C%5B%22H%22%2C%22rev5%22%2C1%2C1%2C1%2C1%2C%22rev6%22%5D%2C%5B%22rev6%22%5D%2C%5B%22Amps6%22%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%2C%5B%5D%5D%7D)):

[![QFT from gradient kickback](https://i.sstatic.net/Tv9rv.png)](https://i.sstatic.net/Tv9rv.png)

Note that the above isn't quite as optimized as what I have in mind. In particular, when you break the subtractions down into H/CX/T gates you find that they start by undoing work the last subtraction ended with. This lets you save half of the T gates.

**Tags:** quantum-computing

> **Comments:**
> **username_1**: What are the controlled a / b-=a gates?  Haven't seen that notation before.  
> **username_0**: It means treat the 'a' qubits as a little-endian number, and subtract them into the 'b' qubits (also little-endian).  
> **username_1**: Thanks!  Sorry I don't have anything useful to contribute to the question!  

---

## 1 answers

### Answer by username_0 on 2018-07-06. Score: 4 | Accepted answer

Here is a 2018 paper that uses phase gradient states and adders to optimize the T-count of the approximate QFT: ["Approximate Quantum Fourier Transform with O(nlog(n)) T gates" by Nam et al.](https://arxiv.org/abs/1803.04933)

*(The careful reader may notice that the question precedes the paper by two years! That's because the question actually led to the paper, though indirectly. I mentioned the phase gradient operation as an application of efficient adders in [this paper](https://quantum-journal.org/papers/q-2018-06-18-74/), Nam et al saw that, independently realized it would useful for the approximate QFT, and here we are full circle. Oh, and of course Kitaev scooped everyone by over ten years. He mentions the adding-into-phase-gradient technique in a [textbook from 2002](https://rads.stackoverflow.com/amzn/click/0821832298) [page 133].)*


---

