An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group
Abstract
Consider a quantum state vector proportional to any given column of the character table of the symmetric group (Sn), 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 Sn [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 Õ(n1.75) gates near the conjecturally classically hard parameter regime, to provably Õ(n2.5) gates in the worst case. In contrast, the QFT subroutine in the prior approach uses Õ(n3) 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 Sn using Õ(n2.5) gates and O(n) qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.
Related
- Efficient Quantum Simulation of Linearized Vlasov--Poisson Dynamics Using Trotter and THRIFT Hamiltonian Simulation Methods
- Efficient Quantum Circuits for Electronic Hamiltonian Simulation without Pauli Expansion
- Efficient Quantum Algorithm for Mixed-State Quantum Geometry
- Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation
- Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
BibTeX
@misc{rathore2026efficient,
title = {{An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group}},
author = {Dikshant Rathore and Leo Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05752},
eprint = {2610.05752},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05752},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group
AU - Dikshant Rathore
AU - Leo Zhou
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05752
UR - https://arxiv.org/abs/2610.05752
AB - 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 Õ(n^1.75) gates near the conjecturally classically hard parameter regime, to provably Õ(n^2.5) gates in the worst case. In contrast, the QFT subroutine in the prior approach uses Õ(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 Õ(n^2.5) gates and O(n) qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.
ER -