Efficient classical algorithms for simulating symmetric quantum systems

Abstract

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.

arXiv comment12 pages, 3 figures

References in corpus (30)

• A Comprehensive Survey on Graph Neural Networks
• Quantum entanglement
• Geometric deep learning: going beyond Euclidean data
• Barren plateaus in quantum neural network training landscapes
• String-net condensation: A physical mechanism for topological phases
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• A rigorous and robust quantum speed-up in supervised machine learning
• Classical simulation of noninteracting-fermion quantum circuits
• Open quantum systems with local and collective incoherent processes: Efficient numerical simulation using permutational invariance
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Exploiting symmetry in variational quantum machine learning
• Theory of overparametrization in quantum neural networks
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Group-Invariant Quantum Machine Learning
• Fast linear algebra is stable
• Deterministic Preparation of Dicke States
• Superradiant and Lasing States in Driven-Dissipative Dicke Models
• Symmetry Principles in Quantum Systems Theory
• Collective processes of an ensemble of spin-1/2 particles
• Fast-forwarding quantum evolution
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• Interpretable Quantum Advantage in Neural Sequence Learning
• Steady-state spin synchronization through the collective motion of trapped ions
• Quantum Schur Sampling Circuits can be Strongly Simulated
• A Practical Quantum Algorithm for the Schur Transform
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations

Cited by in corpus (22)

• Barren Plateaus in Variational Quantum Computing
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Does provable absence of barren plateaus imply classical simulability?
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Provably Trainable Rotationally Equivariant Quantum Machine Learning
• Effects of noise on the overparametrization of quantum neural networks
• Classically estimating observables of noiseless quantum circuits
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Lie-algebraic classical simulations for quantum computing
• Potential and limitations of random Fourier features for dequantizing quantum machine learning
• Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning
• On the universality of $S_n$-equivariant $k$-body gates
• Non-Unitary Quantum Machine Learning
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Splitting and Parallelizing of Quantum Convolutional Neural Networks for Learning Translationally Symmetric Data
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Architectures and random properties of symplectic quantum circuits
• Analyzing the free states of one quantum resource theory as resource states of another
• Exact Many-body Quantum Dynamics in One-Dimensional Baths via Collective Spins
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Equivalence between exponential concentration in quantum machine learning kernels and barren plateaus in variational algorithms