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):

QFT from gradient kickback

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.

  • What are the controlled a / b-=a gates? Haven't seen that notation before. – Ross Duncan Aug 16 '16 at 1:57
  • It means treat the 'a' qubits as a little-endian number, and subtract them into the 'b' qubits (also little-endian). – Craig Gidney Aug 16 '16 at 2:31
  • Thanks! Sorry I don't have anything useful to contribute to the question! – Ross Duncan Aug 17 '16 at 11:59
up vote 3 down vote accepted

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.

(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, 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 [page 133].)

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.