0
$\begingroup$

Shor's algorithm is said to solve the hidden subgroup problem for finite Abelian groups, of which factoring and the discrete logarithm problem for integers belong to. Apparently the HSP for finite Abelian groups can be extracted from generalized quaternions even though they aren't commutative, at least according to this thesis: The Hidden Subgroup Problem for Generalized Quaternions[1].

Does the HSP for finite Abelian groups apply to many normed division algebras, even non-commutative or non-associative ones?

Related to a question I asked on math.stackexchange.com: Does Shor's algorithm work for noncommutitive or nonassociative algebras?[2]

http://acumen.lib.ua.edu/content/u0015/0000001/0000118/u0015_0000001_0000118.pdf https://math.stackexchange.com/questions/754134/does-shors-algorithm-work-for-noncommutitive-or-nonassociative-algebras

Improve this question
$\endgroup$
3
  • $\begingroup$ Shor's algorithm works with groups, not algebras. $\endgroup$
    – Chris Godsil
    Commented Apr 19, 2014 at 12:50
  • $\begingroup$ Are you saying that you can't use it to factor or solve discrete log in non-associative unique factorization domains like the 'Cayley integers' of the octonions, or is that just a comment that I'm abusing terms with the wrong definitions? I thought Shor's algorithm wouldn't apply to quaternions since it supposedly works on finite Abelian groups, but Julia Upton demonstrates that you can apply it to quaternions by (somehow) extracting an Abelian subgroup of quaternions and then applying Shor's algorithm. $\endgroup$
    – dezakin
    Commented Apr 19, 2014 at 17:30
  • $\begingroup$ Upton's thesis looks at generalized quaternion groups, which are a class of groups that are close to abelian. I do not think that the quaternion algebra as such plays a role. $\endgroup$
    – Chris Godsil
    Commented Apr 19, 2014 at 19:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .