1

Technically, Babai's (2016) (classical) quasi-polynomial algorithm can be counted as a quantum algorithm with a runtime of $\textrm{2}^{(\textrm{log(n)}^{c})}$. [Side remark: There is a claim that c=3 is sufficient, Helfgott (2017)]

Query: What is the best-known (quantum) algorithm that tries to formulate the problem as an instance of a hidden subgroup problem over a symmetry group?

Remark: I am aware of the best-known result till 2008 through this review paper by Childs et. al.

I am not aware of the latest developments in this area. I want to confirm if Babai's algorithm (or its improvements) is the asymptotically fastest known ''quantum'' algorithm or not. By improvement, I mean optimizing Babai's algorithmic framework with classical or quantum (say, Grover) techniques.

Thanks!

108_mk
  • 883
  • 1
  • 6
  • 20

0 Answers0