Skip to main content
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
  • 38.7k
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
5 votes

Status of hidden shift and hidden subgroup problems

Here are some cases where there are polynomial time quantum algorithms for the hidden subgroup problems over non-ableian groups. When the subgroups that are hidden are all normal. This is due to ...
dabacon's user avatar
  • 745
4 votes

What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?

TL;DR: There are a few slightly different ways to cast period-finding as a Hidden Subgroup Problem (HSP). The conceptually simplest formulation uses $G=\mathbb{Z}$, but it is not practical from ...
Adam Zalcman's user avatar
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
2 votes

What is the hidden subgroup in Deutsch-Jozsa?

Thinking about this some more, for the Deutsch-Jozsa problem I don't think the parent group $G$ is $n$ copies of $\mathbb Z_2$, but is rather $\mathbb Z/(2^n\mathbb Z)$. That is, the parent group is ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible