⚛️ high-energy theory

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

This paper presents a simplified, Hamiltonian-based quantum algorithm that efficiently prepares character states of the symmetric group using only nearest-neighbor gates with a gate complexity of $\widetilde O(n^{2.5})$ (significantly improving upon the prior $\widetilde O(n^3)$ QFT approach), while also generalizing the method to the quantum character transform and discussing its application to entanglement entropy in conformal field theories.

Original authors: Dikshant Rathore, Leo Zhou

Published 2026-10-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dikshant Rathore, Leo Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of quantum physics, symmetry acts as a powerful organizing principle, much like a master key that unlocks the hidden structure of complex systems. When particles are identical, nature treats them in specific, rigid ways that depend on how they can be swapped or rearranged. Physicists describe these possibilities using mathematical objects called "representations," which categorize the different ways a system can behave under these swaps. To understand the behavior of a system, scientists often need to look at a table of numbers known as a character table. This table connects the different ways particles can be rearranged with the different ways the system can respond. While this table is fundamental to understanding everything from the behavior of gases to the structure of exotic materials, calculating the numbers inside it is notoriously difficult for classical computers, especially as the number of particles grows. The task becomes so complex that it is considered computationally impossible for large systems, creating a bottleneck for simulating nature.

A team of researchers has now developed a new, more efficient way to navigate this complexity using a quantum computer. Instead of trying to calculate individual numbers in the character table one by one, their method prepares a special quantum state that holds an entire column of the table at once. Imagine a library where, instead of reading every book to find a specific fact, you could instantly create a single, glowing summary that contains all the relevant information from a whole section. This is what the new algorithm does: it builds a quantum state where the probability of finding a specific outcome is directly tied to the values in the character table. The researchers achieved this by designing a sequence of controlled movements, driven by a specific type of energy flow, that gently guides the quantum system from a simple starting point to this complex, information-rich state.

The core of their discovery is a mechanism that acts like a ladder. The researchers realized that the mathematical operations needed to build these states have a special property: they can be applied step-by-step, where each step knows exactly how much "effort" is required to move to the next level. By using a single extra helper particle, or "ancilla," they turned these non-standard mathematical operations into smooth, reversible rotations. They then simulated the evolution of this system using two different approaches. The first approach uses a technique called Trotter decomposition, which breaks the complex movement into tiny, manageable steps. This method is particularly well-suited for current and near-future quantum hardware that uses reconfigurable atoms, where the particles can be physically moved to be next to each other. The second approach uses a more advanced mathematical tool called quantum singular value transformation, which provides a rigorous guarantee of efficiency even in the worst-case scenarios.

The results show a significant improvement over previous methods. The older approach, which relied on a complex mathematical transformation known as the quantum Fourier transform, required a number of computational steps that grew very rapidly with the size of the system. The new Hamiltonian-based method, however, requires far fewer steps, scaling much more gently as the system grows. For the most difficult cases, the new algorithm uses a number of steps that grows roughly as the system size to the power of two and a half, a substantial reduction from the previous cubic growth. This efficiency is not just theoretical; the researchers ran numerical simulations on systems with up to forty-eight particles. These simulations revealed that the actual number of steps needed in practice is often even lower than their conservative mathematical estimates, suggesting the method is highly practical.

A crucial part of the study involved understanding when this quantum advantage is truly necessary. Previous theories suggested that certain patterns of particle arrangements would be hard for classical computers to simulate, making them a prime target for quantum speedup. However, the researchers discovered that a specific, highly regular pattern of arrangements—where all the swaps are of the same length—can actually be simulated efficiently by classical computers. This finding refines the boundary of where quantum computers will shine. It suggests that the true advantage lies not in these regular patterns, but in more complex, irregular arrangements where the number of different swap lengths grows with the system size. For these irregular cases, no efficient classical method is known, and the new quantum algorithm offers a clear path forward.

Beyond the mechanics of the algorithm, the researchers demonstrated a practical application for their work in the field of theoretical physics, specifically in studying symmetric orbifold conformal field theories. These are mathematical models used to describe certain types of quantum fields that appear in high-energy physics and string theory. In these models, the presence of specific defects, or topological lines, changes the amount of disorder, or entropy, in the system. The researchers showed that their algorithm could be run in reverse to efficiently estimate this entropy. By measuring the output of their quantum circuit, they could calculate the contribution of these defects to the system's entropy with a precision that improves as the system gets larger. This provides a powerful new tool for physicists to explore the thermodynamic properties of these complex theories, which were previously difficult to compute.

The work also highlights the importance of the hardware on which these algorithms run. The researchers proposed a specific implementation using reconfigurable qubits, such as those found in neutral atom arrays, where the physical positions of the quantum bits can be changed during the computation. This flexibility allows the algorithm to use only the simplest connections between particles, avoiding the need for complex, long-range wiring that often plagues quantum circuits. By combining this hardware flexibility with their efficient algorithm, the team has created a blueprint for a task that could demonstrate a clear quantum advantage on machines that are likely to be available in the near future.

Ultimately, this research represents a shift in how we approach the simulation of symmetry. By moving away from the heavy machinery of the quantum Fourier transform and embracing a more direct, Hamiltonian-based approach, the researchers have opened a new door. They have shown that by carefully understanding the structure of the problem and the specific states the system visits, one can design algorithms that are not only theoretically sound but also remarkably efficient in practice. As quantum hardware continues to evolve, methods like this will be essential for unlocking the secrets of complex quantum systems, turning the abstract mathematics of symmetry into tangible computational power.

Problem Statement

The paper addresses the computational challenge of preparing quantum states corresponding to columns of the character table of the symmetric group $S_n$ . Specifically, for a given cycle type $\nu$ (a partition of $n$ ), the goal is to prepare the character column state:
$|\chi_\nu\rangle := \frac{1}{\sqrt{z_\nu}} \sum_{\lambda \vdash n} \chi_\lambda(\nu) |\lambda\rangle$
where $\chi_\lambda(\nu)$ is the character of the irreducible representation (irrep) $\lambda$ evaluated at the conjugacy class $\nu$ , and $z_\nu$ is the normalization factor.

While evaluating individual character entries is known to be $\#P$ -hard in the worst case, sampling from the probability distribution $P_\nu(\lambda) = |\langle \lambda | \chi_\nu \rangle|^2$ has been proposed as a candidate for quantum advantage. Previous work by Bravyi et al. [1] demonstrated that such sampling could be achieved via the Quantum Fourier Transform (QFT) over $S_n$ , but the best-known implementation of this QFT requires $\tilde{O}(n^3)$ gates and $\tilde{O}(n^{3/2})$ qubits. The authors seek a more efficient, direct method that avoids the full QFT, particularly one suitable for near-term hardware with reconfigurable qubits.

Methodology

The authors propose a Hamiltonian-based algorithm that bypasses the QFT by directly implementing the transfer mechanism required to generate character states.

1. Fermionic Encoding and Transfer Mechanism:
The algorithm relies on the fermionic encoding of $S_n$ characters established by Crichigno and Prakash [11] and Bravyi et al. [1]. In this encoding, the seed state $|1^n 0^n\rangle$ corresponds to the empty partition, and applying a sequence of current operators $J_\nu = J_{\nu_1} \dots J_{\nu_\ell}$ generates the unnormalized character column.
Since $J_s$ (the current operator for cycle length $s$ ) is non-unitary, the authors introduce a transfer mechanism using a single ancilla qubit. They define a Hamiltonian:
$H_s = |1\rangle\langle 0|_a \otimes J_s + |0\rangle\langle 1|_a \otimes J_s^\dagger$
By evolving under $H_s$ for a precise time $t_{s,j} = \pi / (2\sqrt{\zeta})$ , where $\zeta$ is an eigenvalue of $J_s^\dagger J_s$ , the system performs an exact Rabi rotation that maps $|0\rangle_a |\phi\rangle \to |0\rangle_a (J_s |\phi\rangle / \sqrt{\zeta})$ .

2. The Ladder Property:
A critical insight is the ladder property of the current operators. The authors prove that the states visited by the algorithm are eigenvectors of $J_s^\dagger J_s$ with known integer eigenvalues ( $s \cdot j$ for the $j$ -th transfer of length $s$ ). This allows the evolution times to be fixed a priori, enabling deterministic state preparation without post-selection.

3. Two Implementation Strategies:
The paper presents two distinct methods for simulating the Hamiltonian evolution $e^{-iH_s t}$ :

Trotter Decomposition with Reconfigurable Qubits:
- The Hamiltonian $H_s$ is decomposed into nearest-neighbor terms by reordering fermionic modes via a permutation $P_s$ that groups sites by residue modulo $s$ .
- Using the fast fermionic permutation protocol for reconfigurable qubits (e.g., neutral atom arrays) from Maskara et al. [16], the permutation $P_s$ is implemented with $O(n)$ gates in constant depth.
- The evolution is simulated via first-order Trotterization. The authors perform a state-dependent error analysis, showing that the commutator errors are significantly smaller on the specific states visited by the algorithm than the worst-case operator-norm bounds suggest.
Quantum Singular Value Transformation (QSVT):
- To provide a rigorous worst-case bound, the authors construct a block-encoding of $H_s$ using Pauli strings.
- They apply QSVT to simulate the evolution with logarithmic dependence on the inverse error $1/\delta$ .
- This approach is extended to the Quantum Character Transform (QCT), which coherently maps superpositions of cycle types to superpositions of character states. The QCT involves "erasing" the cycle type registers after the transfer steps using phase estimation on the operator $N_s = J_s J_s^\dagger / s$ , amplified via singular value amplification to reduce gate costs.

Key Contributions and Results

1. Improved Gate Complexity:

QSVT-based CSP: The authors prove that Character State Preparation (CSP) for any cycle type can be achieved with $\tilde{O}(n^{5/2})$ gates and $O(n)$ qubits. This improves upon the $\tilde{O}(n^3)$ gate count of the QFT-based approach.
Quantum Character Transform (QCT): They provide the first explicit polynomial gate bound for the full QCT over general $S_n$ , also scaling as $\tilde{O}(n^{5/2})$ with $O(n)$ qubits.

2. State-Dependent Trotter Bounds:

For uniform cycle types $\nu = (s^m)$ , the authors derive a leading-order state-dependent Trotter error bound.
In the regime proposed for quantum advantage ( $m = \Theta(\sqrt{n}/\log n)$ ), the estimated sufficient gate count is $\tilde{O}(n^{7/4}/\delta)$ .
Numerical simulations up to $n=48$ suggest that the actual gate counts required are even lower than these analytical bounds, scaling roughly as $n^{1.2}$ to $n^{1.5}$ for various cycle types, indicating the analytical bounds are conservative.

3. Classical Complexity Analysis:

The paper challenges the assumption that all cycle types in the "granularity regime" (where Bravyi et al. argue for quantum advantage) are classically hard.
They present exact classical sampling algorithms for uniform cycles ( $\nu = (s^m)$ ) and almost-uniform cycles (perturbations of uniform cycles by a constant number of exceptional cycles).
These classical samplers run in expected time $\tilde{O}(n^2)$ for uniform cycles and $n^{4b+O(1)}$ for almost-uniform cycles with $b$ exceptional cycles. This implies that quantum advantage in this regime requires cycle types where the number of exceptional cycles grows with $n$ .

4. Application to CFTs:

The inverse QCT is applied to estimate the defect entropy in symmetric orbifold Conformal Field Theories (CFTs). By measuring the output of the inverse QCT, one can sample cycle types $\nu$ with probability proportional to the weights in the defect entropy formula. The authors show this allows for an efficient estimation of the entropy with additive error $O(\sqrt{n})$ , which becomes a vanishing relative error for generic irreps where the entropy scales as $\Theta(n)$ .

Significance and Claims

The paper claims to provide a simpler and more efficient alternative to the QFT-based approach for accessing symmetric group characters. By leveraging Hamiltonian evolution and the specific algebraic structure of the current operators (the ladder property), the authors achieve a provable reduction in gate complexity from $\tilde{O}(n^3)$ to $\tilde{O}(n^{5/2})$ .

The significance is twofold:

Theoretical: It establishes the first explicit polynomial bound for the QCT over general $S_n$ and refines the understanding of the classical hardness landscape, showing that uniform cycles (a key candidate regime) are classically tractable.
Practical: The Trotter-based implementation is explicitly designed for reconfigurable qubit architectures (like neutral atom arrays), utilizing nearest-neighbor gates and fast permutations. The numerical benchmarks suggest this approach is a viable candidate for realizing near-term quantum advantage, provided the cycle types chosen involve a growing number of exceptional cycles to ensure classical hardness.

The authors remain modest regarding the Trotter bounds, noting that their rigorous worst-case bounds are likely loose overestimates compared to the empirical performance observed in simulations, and that the full error analysis beyond the leading order remains an open question.

Problem Statement

Methodology

Key Contributions and Results

Significance and Claims

More like this