arXiv:2610.05752
An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group
Dikshant Rathore, Leo Zhou
Abstract
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.
AI Summary
The paper studies preparation of symmetric-group character states, $|\chi_\nu\rangle=z_\nu^{-1/2}\sum_{\lambda\vdash n}\chi^\lambda(\nu)|\lambda\rangle$, and their coherent extension, the quantum character transform (QCT). It replaces a previous $S_n$ quantum-Fourier-transform approach with Hamiltonian evolution in a fermionic encoding. The construction applies current operators $J_s$ through an ancilla-coupled Hamiltonian. A proved ladder property makes each transfer an exact two-level Rabi rotation with known duration $\pi/(2\sqrt{sj})$, giving deterministic preparation without postselection. Explicit block encodings and QSVT simulation yield a worst-case preparation cost of $\widetilde O(n^{5/2})$ gates and $2n+O(\log n)$ qubits for fixed or inverse-polynomial error, compared with $\widetilde O(n^3)$ gates for the previous approach’s QFT subroutine. Coherent preparation plus multiplicity-register erasure implements the full QCT in $\widetilde O(n^{5/2})$ gates and $O(n)$ qubits; erasure uses phase estimation and singular-value amplification. A separate Trotter implementation uses nearest-neighbor gates with reconfigurable qubits. For uniform cycle types $(s^m)$, leading-order state-dependent analysis gives $O(n[m^{3/2}+m^2/s^{3/2}]/\delta)$ gates, or $\widetilde O(n^{7/4}/\delta)$ near the proposed sampling-advantage cycle count. Higher-order remainders are unbounded. Exact simulations through $n=48$ indicate smaller costs but do not establish asymptotic scaling there. Classical quotient/Plancherel sampling gives exact $\widetilde O(n^2)$ sampling for uniform cycles and $n^{4b+O(1)}$ for $b$ exceptional cycles, excluding these bounded-perturbation families from the proposed sampling advantage. Hardness elsewhere remains conjectural. Inverse QCT also enables an $O(\sqrt n)$-additive-error estimator of defect entropies in symmetric-orbifold CFTs.
and to code the numerical simulations of the Trotterized CSP circuit for uniform cycle types and their perturbations (Section~\ref{sec:numerics}).
Error found: The abstract describes its leading-order Trotter gate-count estimates as sufficient for a fixed target state error, although the unbounded higher-order remainder prevents those estimates from certifying the full error.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 54 pages, 8 figures