A new paper introduces a quantum-inspired classical algorithm for an important problem in group representation theory—computing the characters of the symmetric group. The work shows that this problem can be rephrased as simulating (non-unitary) time evolution of a particular quantum spin chain. This means the problem can be tackled using tensor network simulation methods like Matrix Product States. And, surprisingly, the authors find an efficient quantum algorithm for this problem.
The character of a symmetric group representation acts like a fingerprint and gives us a tool to better understand how complicated systems behave. Representation theory is commonly used to analyze systems in research domains like chemistry and quantum field theory. While the proposed classical algorithm is shown to outperform state-of-the-art computer algebra systems such as GAP and SAGE on certain benchmark problems, the authors are excited about the prospect of an efficient quantum algorithm for this problem. The authors hope future work will unlock direct access to quantum amplitudes and their encoded characters of group representations.
Check out the publication for details!
Alex Lukin 