In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.
Understanding which subclasses of quantum circuits are efficiently classically simulable is fundamental to delineating the boundary between classical and quantum computation. In this context, it is well known that certain tasks based on permutation-equivariant unitaries-i.e.,
n-qubit circuits whose action commutes with the qubit-permuting representation of the symmetric group
Sn-can be simulated in polynomial time. However, existing approaches scale as
O(n7), and can rapidly become prohibitively expensive. In this work, we introduce a practical algorithm for simulating
Sn-equivariant circuits under the assumption that the gate generators are at most
k-local, with
k∈O(1). The resulting method runs in
O(nω+1) time for constant depth, where
ω is the matrix multiplication exponent, significantly lowering the polynomial degree compared to existing techniques. Finally, we numerically validate this scaling by simulating the dynamical evolution of the Lipkin-Meshkov-Glick model, and show that for
n=512 spins, a standard laptop can compute the concurrence of the evolved state in under two minutes.
In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.
This thesis presents an efficient quantum algorithm and explicit circuits for generating eigenstates of arbitrary SU(2) and SU(3) representations. These include a wide variety of highly entangled states. The algorithm uses Schur transform that rotates the input computational basis states to the output Schur basis states with resources polynomial in number of qudits n. Using the fact that quantum logic is reversible, we accomplish the desired result using the inverse Schur transform. The algorithm can be easily generalized to any arbitrary higher groups.
The efficient simulation of complex quantum systems remains a central challenge due to the exponential growth of Hilbert space with system size. Tensor network methods have long been established as powerful approximation schemes, and their efficiency can be further enhanced by incorporating physics-informed priors. A prominent example is symmetry: recent progress on
U(1)-symmetric tensor networks, accelerated on GPUs and scaled to supercomputers, shows how conserved charges induce block-sparse structures that reduce computational cost and enable larger simulations. The same principle extends to general symmetries, inspiring equivariant neural networks in machine learning and guiding symmetry-preserving ansätze in variational quantum algorithms. Beyond symmetry, physics-informed design also includes strategies such as hybrid tensor networks and parallel sequential circuits, which pursue efficiency from complementary principles. This Perspective argues that physics-informed tensor networks, grounded in both symmetry and beyond-symmetry insights, provide unifying strategies for scalable approaches in quantum simulation, computation, and machine learning.
Many quantum algorithms can be represented in a form of a classical circuit positioned between quantum Fourier transformations. Motivated by the search for new quantum algorithms, we turn to circuits where the latter transformation is replaced by the SU(2) quantum Schur transform---a global transformation which maps the computational basis to a basis defined by angular momenta. We show that the output distributions of these circuits can be approximately classically sampled in polynomial time if they are sufficiently close to being sparse, thus isolating a regime in which they could lead to algorithms with exponential computational advantages. Our paper is primarily motivated by a conjecture that underpinned the hardness of permutational quantum computing, a restricted quantum computational model that has the above circuit structure in one of its computationally interesting regimes. The conjecture stated that approximating transition amplitudes of permutational quantum computing model to inverse-polynomial precision on a classical computer is computationally hard in this case. We disprove the extended version of this conjecture---even in the case when the hardness of approximation originated from a difficulty of finding the large elements in the output probability distributions. Finally, we present some evidence that output of the above permutational quantum computing circuits could be efficiently approximately sampled from on a classical computer.
The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of
n copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost
O(2n) per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in
n and the inverse additive-error, for input states formed by products of
n four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.