Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a novel, more efficient Hamiltonian-based quantum algorithm for preparing character states of the symmetric group $S_n$, outperforming a prior quantum Fourier transform (QFT) approach in gate complexity. The new method achieves gate counts ranging from $O(n)$ to $\widetilde O(n^{2.5})$ depending on the target column, significantly lower than the $\widetilde O(n^3)$ of the QFT method. This work also extends to an efficient quantum character transform and has potential applications in quantum field theory.
A simpler, Hamiltonian-based quantum algorithm prepares $S_n$ character states with up to $O(n)$ gates, drastically improving on prior $\widetilde O(n^3)$ QFT methods.
Consider a quantum state vector proportional to any given column of the character table of the symmetric group ($S_n$), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over $S_n$ [arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as $O(n)$ gates for the $n$-cycle column, to $\widetilde O(n^{1.75})$ gates near the conjecturally classically hard parameter regime, to provably $\widetilde O(n^{2.5})$ gates in the worst case. In contrast, the QFT subroutine in the prior approach uses $\widetilde O(n^3)$ gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over $S_n$ using $\widetilde O(n^{2.5})$ gates and $O(n)$ qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.