BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Classical and Quantum Algorithms for Characters of the Symmetric G
 roup - Louis Schatzki (University of Illinois Urbana-Champaign)
DTSTART:20250313T140000Z
DTEND:20250313T150000Z
UID:TALK228598@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Characters of irreducible representations are ubiquitous in gr
 oup theory yet prove challenging to compute. Here we describe a Matrix Pro
 duct State (MPS) algorithm for characters of Sn building on a mapping from
  characters of Sn to quantum spin chains proposed by Crichigno and Prakash
  (of which we also provide a simplified derivation). We complement this re
 sult by presenting a poly(n) size quantum circuit that prepares the corres
 ponding MPS obtaining an efficient quantum algorithm for certain sampling 
 problems based on characters of Sn. To assess classical hardness of these 
 problems we present a general reduction from strong simulation (computing 
 a given probability) to weak simulation (sampling with a small error). Thi
 s reduction applies to any sampling problem with a certain granularity str
 ucture and may be of independent interest. Joint work with Sergey Bravyi\,
  David Gosset\, and Vojtech Havlicek.
LOCATION:Computer Laboratory\, William Gates Building\, Room FW11
END:VEVENT
END:VCALENDAR