Figure 7-25. Four-qubit inverse QFT? Or QFT?

[simplygreatwork]

To me, that circuit looks like a QFT and not an inverse QFT. Can someone verify this?

[machinelevel]

Funny story about this one; in all of my prior work I had the two mixed up, including in this 2016 SIGGRAPH talk. When we were nearing completion on the book, Nic, Mercedes and I set aside everything else for a day and focused on just making sure that we had QFT and invQFT correct, in the text and in the examples.

I've just gone in and re-verified that the online examples match the text, so Example 7-1 takes these three states...

...applies this circuit...

...and produces these three states...

...which is what a forward QFT should do.

As a result, I'm pretty sure these are labeled correctly, however I'm definitely open to being corrected. I've also found them mixed up in the literature often. In practice (in my day job) if one didn't do what I expect I just try the other. :]

[gregbyrd]

I'm using your book for an undergraduate class this semester, and I'm also confused on this point.

On the one hand: It makes sense to me to go from a phase-encoded signal to a frequency, since that matches with my intuition about the DFT -- from time domain to frequency domain.

On the other hand: Other sources, including Nielsen and Chuang, and the IBM Qiskit textbook define it the other way, with a phase-encoded signal coming out. And their description of Shor's algorithm uses invQFT instead of QFT.

So maybe there are different conventions, and I can live with that. However, Chapter 8 is inconsistent, because it shows an invQFT converting a phase-encoded signal to a frequency in Figure 8-8, and invQFT is used consistently this way throughout the chapter. If I prepare the state shown in Figure 8-8 and run it through invQFT in QCEngine, the result is 6, not 2. But the result using QFT is 2.

The text above Figure 8-8 is also confusing, in my opinion. (It appears that Chapters 11 and 12 are consistent with Chapter 7.)

[machinelevel]

Hi Greg, thanks for getting in touch on this! I'm very glad you're finding the book useful, if I can be of help when it comes to your undergrad class, please don't hesitate to get in touch.

QFT and invQFT are definitely QC's version of "axis-sign issues" in graphics, or "endian issues" in CPU architecture. Happily, one is simply the reverse of the other. Before finalizing the book, the three of us got together and worked through the whole thing, start to finish, making sure it was at least self-consistent, and also (as you mention) consistent with DFT sensibility.

• Regarding Figure 8-8 and the related text, you're absolutely correct of course. We missed one! It's easy to see by running Example 7-1 that the labels in Figure 8-8 should read "QFT", not "invQFT".

I've added this to our Errata page just now with thanks to you for spotting it.

I've also checked the examples in that chapter Example 8-1 and Example 8-2 which both use invQFT(), and they run correctly. So it looks like using invQFT() for phase estimation is consistent with the book's conventions, and it's just Figure 8-8 which is incorrect.

As always, I'm happy to help correct or clarify as needed. Cheers!

[gregbyrd]

Are you sure the examples don't work just because you expect the answer to be 1000 in the case of example 8-1? In that case, it wouldn't matter (I think) whether QFT or invQFT is used because 16-8 = 8. I ran example 8-1 using the T gate instead of H, with the eigenstate of |1>. QFT gives me an answer of 0001, which is what I would expect (1/16), but invQFT gives me an answer of 15.

[gregbyrd]

Correction my recent comment. I did a pi/8 rotation instead of a T gate, which gets 0001 with QFT, which is what I expect.

[machinelevel]

Thanks for this extra info; I'm looking into this a bit more deeply to make sure the corredtion is self-consistent. One thing that's definitely useful is the fact that the examples are implemented in multiple programming languages. For example:

On conventions: When I mentioned the similarity of the QFT/invQFT convention to big/little endianness, I'd forgotten that it's actually more than a similarity: in the Q# implementation of Example 7-1, the little-endian QFT QFTLE() is used, along with a comment about the conventions.

I'll dig into this further; Example 8-2 has an eigenphase of 150° and looks like it's getting the correct result with the current implementation.

Also will be useful to compare to the Q# implementations of 8-1 and 8-2; one of those (8-1) uses the buit-in QuantumPhaseEstimation call, which looks to be big-endian. The other (8-2) calls QFTLE(LittleEndian(phaseRegister));

In any case, I appreciate your feedback on this very much!

[gregbyrd]

I won't keep beating this bush -- thanks for looking into this. It's a confusing issue, for sure. But the signal before going into the invQFT looks like it has a -150 angle, not +150.