New answers tagged

5 votes
Accepted

Are all quantum algorithms hidden subgroup algorithms?

Currently, I am reviewing some literature on this topic. This is still an open problem if we talk about general Hidden subgroup problem (say, g-HSP), including both abelian and non-abelian cases. An ...
Manish Kumar's user avatar
6 votes
Accepted

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

Here's an $O(n \lg^2 n)$ construction of the QFT based on merging groups of phasing operations into multiplications: You can verify the circuit works in Quirk. The "reverse" gate reverses ...
Craig Gidney's user avatar
  • 35.4k
4 votes

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

I think this is a good question. But the answers might depend on the precise meaning behind "exact" as even Coppersmith's improvement provides an approximate algorithm. For example, Shor ...
Mark Spinelli's user avatar

Top 50 recent answers are included