Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.05752

An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

Dikshant Rathore, Leo Zhou

quant-phhep-thSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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

Related papers

Classical and Quantum Algorithms for Characters of the Symmetric Group

Sergey B. Bravyi, David Gosset, Vojtěch Havlíček +1 more

Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group S n is a challenging problem known to be #P-hard in the worst case. Here we describe a matrix product state (MPS) algorithm for characters of S n . The algorithm computes an MPS encoding all irreducible characters of a given permutation. It relies on a mapping from characters of S n to quantum spin chains proposed by Crichigno and Prakash. We also provide a simpler derivation of this mapping. 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 S n . 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.

arXiv:2501.12579•PRX Quantum•Jun 25, 2025•8 citations

Quantum Fourier transform for the symmetric group

Carli Bruinsma, Dmitry Grinko, Maris Ozols

Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to $\widetilde{\mathcal{O}}(n^{3.5})$ and circuit depth to $\widetilde{\mathcal{O}}(n^3)$. Moreover, we observe that their construction is not optimal in the choice of transversal elements, so we propose simpler realization of the symmetric group QFT.

quant-pharXiv:2608.28569•Aug 31, 2026•4 citations

Approximate quantum Fourier transform with O(n log(n)) T gates

Yunseong Nam, Yuan Su, Dmitri A Maslov

Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of $$O(n\,{\mathrm{log}}^{2}\,(n))$$ O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

arXiv:1803.04933•npj Quantum Information•Mar 13, 2020•122 citations

Fast quantum algorithms for approximating some irreducible representations of groups

Stephen P. Jordan

We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.

arXiv:0811.0562•Nov 4, 2008•16 citations

Randomized Quantum Singular Value Transformation

Xinzhao Wang, Yuxin Zhang, Hazra, Soumyabrata +3 more

We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.

arXiv:2510.06851•Oct 8, 2025•13 citations

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

Yota Maeda, Hiroshi Yano

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

quant-pharXiv:2608.23929•Aug 26, 2026•0 citations
Consider a quantum state vector proportional to any given column of the character table of the symmetric group (SnS_nSn​), 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 SnS_nSn​ [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)O(n)O(n) gates for the nnn-cycle column, to O~(n1.75)\widetilde O(n^{1.75})O(n1.75) gates near the conjecturally classically hard parameter regime, to provably O~(n2.5)\widetilde O(n^{2.5})O(n2.5) gates in the worst case. In contrast, the QFT subroutine in the prior approach uses O~(n3)\widetilde O(n^3)O(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 SnS_nSn​ using O~(n2.5)\widetilde O(n^{2.5})O(n2.5) gates and O(n)O(n)O(n) qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.
The paper studies preparation of symmetric-group character states, ∣χν⟩=zν−1/2∑λ⊢nχλ(ν)∣λ⟩|\chi_\nu\rangle=z_\nu^{-1/2}\sum_{\lambda\vdash n}\chi^\lambda(\nu)|\lambda\rangle∣χν​⟩=zν−1/2​∑λ⊢n​χλ(ν)∣λ⟩, and their coherent extension, the quantum character transform (QCT). It replaces a previous SnS_nSn​ quantum-Fourier-transform approach with Hamiltonian evolution in a fermionic encoding.
The construction applies current operators JsJ_sJs​ through an ancilla-coupled Hamiltonian. A proved ladder property makes each transfer an exact two-level Rabi rotation with known duration π/(2sj)\pi/(2\sqrt{sj})π/(2sj​), giving deterministic preparation without postselection. Explicit block encodings and QSVT simulation yield a worst-case preparation cost of O~(n5/2)\widetilde O(n^{5/2})O(n5/2) gates and 2n+O(log⁡n)2n+O(\log n)2n+O(logn) qubits for fixed or inverse-polynomial error, compared with O~(n3)\widetilde O(n^3)O(n3) gates for the previous approach’s QFT subroutine. Coherent preparation plus multiplicity-register erasure implements the full QCT in O~(n5/2)\widetilde O(n^{5/2})O(n5/2) gates and O(n)O(n)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 (sm)(s^m)(sm), leading-order state-dependent analysis gives O(n[m3/2+m2/s3/2]/δ)O(n[m^{3/2}+m^2/s^{3/2}]/\delta)O(n[m3/2+m2/s3/2]/δ) gates, or O~(n7/4/δ)\widetilde O(n^{7/4}/\delta)O(n7/4/δ) near the proposed sampling-advantage cycle count. Higher-order remainders are unbounded. Exact simulations through n=48n=48n=48 indicate smaller costs but do not establish asymptotic scaling there.
Classical quotient/Plancherel sampling gives exact O~(n2)\widetilde O(n^2)O(n2) sampling for uniform cycles and n4b+O(1)n^{4b+O(1)}n4b+O(1) for bbb exceptional cycles, excluding these bounded-perturbation families from the proposed sampling advantage. Hardness elsewhere remains conjectural. Inverse QCT also enables an O(n)O(\sqrt n)O(n​)-additive-error estimator of defect entropies in symmetric-orbifold CFTs.
Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group S n is a challenging problem known to be #P-hard in the worst case. Here we describe a matrix product state (MPS) algorithm for characters of S n . The algorithm computes an MPS encoding all irreducible characters of a given permutation. It relies on a mapping from characters of S n to quantum spin chains proposed by Crichigno and Prakash. We also provide a simpler derivation of this mapping. 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 S n . 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.
Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to O~(n3.5)\widetilde{\mathcal{O}}(n^{3.5})O(n3.5) and circuit depth to O~(n3)\widetilde{\mathcal{O}}(n^3)O(n3). Moreover, we observe that their construction is not optimal in the choice of transversal elements, so we propose simpler realization of the symmetric group QFT.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of O(n log2 (n))O(n\,{\mathrm{log}}^{2}\,(n))O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of O(n log (n))O(n\,{\mathrm{log}}\,(n))O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.
We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.
We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.
We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial f(x)=∑j=1sajxuj∈Fq[x1±1,…,xn±1],f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], f(x)=∑j=1s​aj​xuj​∈Fq​[x1±1​,…,xn±1​], let UUU be its augmented support matrix whose columns are (1,uj)(1,u_j)(1,uj​) with rank ρρρ and N(f):=#{x∈(Fq×)n∣f(x)=0}N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}N(f):=#{x∈(Fq×​)n∣f(x)=0} be its torus point count. Our first main result is a quantum algorithm that outputs N^(f)\widehat{N}(f)N(f) satisfying ∣N^(f)−N(f)∣≤εqn+s/2−ρ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} ∣N(f)−N(f)∣≤εqn+s/2−ρ with success probability 1−δ1-δ1−δ. Provided that ρρρ and ∥U∥∞\|U\|_\infty∥U∥∞​ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,log⁡q,1/ε,log⁡(1/δ))\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))poly(n,s,logq,1/ε,log(1/δ)). It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in log⁡q\log qlogq. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes #\##P-hard under randomized polynomial-time Turing reductions when the support matrix UUU varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.