Classical and Quantum Algorithms for Characters of the Symmetric Group

Add to your list(s) Download to your calendar using vCal

• Louis Schatzki (University of Illinois Urbana-Champaign)
• Thursday 13 March 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room FW11.

If you have a question about this talk, please contact Tom Gur.

Characters of irreducible representations are ubiquitous in group theory yet prove challenging to compute. Here we describe a Matrix Product 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 result by presenting a poly(n) size quantum circuit that prepares the corresponding 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). This reduction applies to any sampling problem with a certain granularity structure and may be of independent interest. Joint work with Sergey Bravyi, David Gosset, and Vojtech Havlicek.

This talk is part of the Quantum Computing Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room FW11
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Quantum Computing Seminar
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.