Efficient solvability of Hamiltonians and limits on the power of some quantum computational models

Abstract

We consider quantum computational models defined via a Lie-algebraic theory. In these models, specified initial states are acted on by Lie-algebraic quantum gates and the expectation values of Lie algebra elements are measured at the end. We show that these models can be efficiently simulated on a classical computer in time polynomial in the dimension of the algebra, regardless of the dimension of the Hilbert space where the algebra acts. Similar results hold for the computation of the expectation value of operators implemented by a gate-sequence. We introduce a Lie-algebraic notion of generalized mean-field Hamiltonians and show that they are efficiently ("exactly") solvable by means of a Jacobi-like diagonalization method. Our results generalize earlier ones on fermionic linear optics computation and provide insight into the source of the power of the conventional model of quantum computation.

6 pages; no figures

Cited by in corpus (29)

• Barren Plateaus in Variational Quantum Computing
• Matchgates and classical simulation of quantum circuits
• Bond Algebras and Exact Solvability of Hamiltonians: Spin S=1/2 Multilayer Systems and Other Curiosities
• Symmetry Principles in Quantum Systems Theory
• Does provable absence of barren plateaus imply classical simulability?
• Quantum Chaos, Delocalization, and Entanglement in Disordered Heisenberg Models
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Fast-forwarding quantum evolution
• Generalized entanglement as a framework for complex quantum systems: Purity vs delocalization measures
• Efficient classical algorithms for simulating symmetric quantum systems
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension
• Universal measurement-based quantum computation in a one-dimensional architecture enabled by dual-unitary circuits
• Entanglement and Subsystems, Entanglement beyond Subsystems, and All That
• Classically estimating observables of noiseless quantum circuits
• Lie-algebraic classical simulations for quantum computing
• Classical simulation of non-Gaussian fermionic circuits
• Generalized Coherent States as Preferred States of Open Quantum Systems
• Classical Ising model test for quantum circuits
• Automatic and effective discovery of quantum kernels
• How to define quantum mean-field solvable Hamiltonians using Lie algebras
• Efficient simulation of quantum evolution using dynamical coarse-graining
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Quantum circuit synthesis for generalized coherent states
• Quantum Circuits and Spin(3n) Groups
• Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing
• Analyzing the free states of one quantum resource theory as resource states of another
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• A graph-theoretic approach to chaos and complexity in quantum systems
• Efficient classical simulation of cluster state quantum circuits with alternative inputs