BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Matthew Moore (University of Kansas)
DTSTART:20210316T190000Z
DTEND:20210316T200000Z
DTSTAMP:20260423T021728Z
UID:PALS/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/PALS/5/">The
  Hidden Subgroup Problem for universal algebras</a>\nby Matthew Moore (Uni
 versity of Kansas) as part of PALS Panglobal Algebra and Logic Seminar\n\n
 \nAbstract\nThe Hidden Subgroup Problem (HSP) is a computational problem w
 hich includes as\nspecial cases integer factorization\, the discrete logar
 ithm problem\, graph\nisomorphism\, and the shortest vector problem. The c
 elebrated polynomial-time\nquantum algorithms for factorization and the di
 screte logarithm are restricted\nversions of a generic polynomial-time qua
 ntum solution to the HSP for abelian\ngroups\, but despite focused researc
 h no polynomial-time solution for general\ngroups has yet been found. We p
 ropose a generalization of the HSP to include\narbitrary algebraic structu
 res and analyze this new problem on powers of\n2-element algebras. We prov
 e a complete classification of every such power as\nquantum tractable (i.e
 . polynomial-time)\, classically tractable\, quantum\nintractable\, or cla
 ssically intractable. In particular\, we identify a class of\nalgebras for
  which the generalized HSP exhibits super-polynomial speedup on a\nquantum
  computer compared to a classical one.\n
LOCATION:https://researchseminars.org/talk/PALS/5/
END:VEVENT
END:VCALENDAR