This problem was originally introduced by Aaronson and Kuperberg in 2007 in their seminal paper that gave a *quantum* oracle separating QMA vs QCMA. Coming up with a classical oracle to do the same has attracted a lot of attention from folks over the years.

John gave an epic 2.5 hour whiteboard talk today about the proof, and the ideas used are quite dazzling: Noether's theorem, recording oracles, bosons, ...

Following *this* reference in turn yields basically a version of the iterative QPE.

Thanks for the reference. I took a closer look at this paper, and first of all it is beautifully written. Second of all I noticed that it mentions off-hand "Also, it should be noted that the QFT, and its inverse, can be implemented in the fault tolerant ‘semiclassical’ way (Griffiths & Niu).

I do phase estimation without QFT in my undergrad course. youtu.be/CMqPutlG59c?...

It's just Hadamard test plus binary search.

Best wishes, Eric.

This is great! Do you know of a good reference for comparing the pros/cons of the QFT version versus the single-ancilla qubit version (complexity, why you would use one versus another)? Patrick Rall's paper alludes to the tradeoffs, but it doesn't give as much detail as I would like.

By Kitaev's algorithm, do you mean the one without QFT?

Is there any reason to teach QFT at all in an intro to quantum computing class? From Patrick Rall's paper on phase estimation, it seems potentially superfluous (arxiv.org/pdf/2103.09717).

But last week I covered the "poor man's" version of phase estimation, which only uses a single ancilla qubit. I am now wondering, why do we need the QFT anyways? Googling around, it seems like in many cases we don't! Is there any reason to QFT-based phase estimation?

Congrats Clement!

Congratulations Lauritz!

The music totally sounds Haar random!