BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Matthew Moore (U of Kansas)
DTSTART:20210311T190000Z
DTEND:20210311T200000Z
DTSTAMP:20260423T035751Z
UID:OLS/47
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/OLS/47/">The
  Hidden Subgroup Problem for Universal Algebras</a>\nby Matthew Moore (U o
 f Kansas) as part of Online logic seminar\n\n\nAbstract\nThe Hidden Subgro
 up Problem (HSP) is a computational problem which includes as\nspecial cas
 es integer factorization\, the discrete logarithm problem\, graph\nisomorp
 hism\, and the shortest vector problem. The celebrated polynomial-time\nqu
 antum algorithms for factorization and the discrete logarithm are restrict
 ed\nversions of a generic polynomial-time quantum solution to the HSP for\
 n<i>abelian</i> groups\, but despite focused research no polynomial-time s
 olution\nfor general groups has yet been found. We propose a generalizatio
 n of the HSP to\ninclude <i>arbitrary</i> algebraic structures and analyze
  this new problem on\npowers of 2-element algebras. We prove a complete cl
 assification of every such\npower as quantum tractable (i.e. polynomial-ti
 me)\, classically tractable\,\nquantum intractable\, or classically intrac
 table. In particular\, we identify a\nclass of algebras for which the gene
 ralized HSP exhibits super-polynomial\nspeedup on a quantum computer compa
 red to a classical one.\n
LOCATION:https://researchseminars.org/talk/OLS/47/
END:VEVENT
END:VCALENDAR